首页 > Python算法 > 分治算法 阅读数:20

分治算法的基本思想

分治算法的主要思想是将原问题分成若干个子问题,解决这些子问题再最终合并出原问题的答案。在计算过程中,子问题会被递归地分解成更小的子问题,直到子问题满足边界条件。最后,算法会层层递回原问题的答案。

分治算法的原理可以用二叉树表示。如图 1 所示,假设给定的问题不能够被直接解决,这时,我们可以尝试将原问题分成相互独立的两个子问题。
分治算法
图 1:分治算法

如果能将这两个子问题解决,那我们就离原问题的解不远了。如果子问题仍然复杂,我们就继续分解,直到子问题满足边界条件,小到可以直接得出答案为止。得到最小子问题的解后,我们往上递归,将子问题的解层层合并,最终获得原问题的解。

实际上,我们不一定每一次都将原问题分成两个子问题。根据问题的需要,我们可以将原问题分成 k 个子问题,k>1。

需要注意的是,因为我们利用递归算法,所以需要保证子问题与原问题的结构和性质相同。也就是说,子问题和原问题问的是同一个问题,只不过子问题的规模较小。比如,排列 10 个数和排列 5 个数是两个结构和性质相同的问题,但是后者比前者的规模要小。

在之前的章节中讲到的归并排序是分治算法的代表性应用之一,让我们简略回顾归并排序并且通过它理解分治算法的原理。我们即将升序排序以下数组:[10,6,2,9,5,1,12,4,0,4,1,2,1,3,2,9]。

如图 2 所示,我们将原问题分成了两个子问题,分别是排序 [10,6,2,9,5,1,12,4] 和排序 [0,4,1,2,1,3,2,9]。也就是说,我们将数组一分为二,分成了两个长度减半的数组。这样做的理由是,如果我们将两个子数组排序完毕,就可以通过双指针的方法不费事地将原数组排序。
归并排序
图 2:归并排序

利用同样的逻辑,我们将子数组也一分为二。在之前的章节中提到,停止递归的条件是数组的长度。一旦子数组长度为一,我们就停止递归,将数组直接输出。在那之后,我们会通过双指针的方法得到排序完毕的、长度为二的子数组。得到长度为二的子数组后,我们会通过双指针的方法得到排序完毕的、长度为四的子数组,以此类推,直到得到原问题的解。

最后,我们总结分治算法的三个步骤:
  1. 将原问题分解成若干个性质相同的、相互独立的子问题;
  2. 递归地解决各子问题,直到子问题小到可以直接被解决;
  3. 逐层合并子问题的解,得到原问题的解。

判断一个问题能否用分治算法解决时,首先看原问题能否被分解成更小的子问题。如果可以,再看子问题的结构和性质是否与原问题一样。如果一样,那么问题很有可能能够用分治算法解决。