科技名词

分治

Divide and Conquer

定义：逐次把一个复杂的问题分成多个相同或相似的子问题，直到最后子问题可以简单地直接求解，原问题的解即为子问题的解的合并。

学科：计算机科学技术_理论计算机科学_算法设计与分析

相关名词：问题 递归 合并 解

【延伸阅读】

分治算法是一种常见的解决问题的策略，其基本思想是将复杂的问题分解成几个简单的子问题，然后递归求解各个子问题，从而寻求原问题解的算法。利用分治算法求解问题一般包括三个主要步骤：

1.分解：将原问题分解为若干个相互独立、规模较小且与原问题形式相同的一系列子问题。

2.解决：如果子问题规模小到可以直接被解决则直接解，否则需要递归地求解各个子问题。

3.合并：将各个子问题的解合并成原问题的解。

对于一个规模为n的问题，运用分治算法求解的策略是：如果该问题可以容易地解决（比如规模n较小），则直接解决；否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解决这些子问题，然后将各个子问题的解合并得到原问题的解。

根据分治算法的分割原则，应把原问题分为多少个子问题才较合适，每个子问题是否规模相同或怎样才为适当，这些问题都很难予以肯定回答。但人们从大量实践中发现，在用分治算法设计算法时，最好使子问题的规模大致相同，即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。

分治不仅是一类常用的计算机算法，在日常生活中也会常常用它去解决具体的问题。《孙子兵法》就曾有“倍则分之”的战略，意思就是把强大的敌人进行分割，寻求在局部兵力对比的优势以创造制胜机会，这与分治算法有异曲同工之妙。

（延伸阅读作者：西华师范大学数学与信息学院 李斌斌博士）