分治算法——汉诺塔问题

分治算法——汉诺塔问题

一、分治算法概念       “分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。         这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换) 。

        任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。

问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。

而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。 二、分治法的设计思想         将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

三、分治策略         对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。 四、分治法实现步骤 ①分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；②解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；③合并：将各个子问题的解合并为原问题的解。

什么是分治算法？

分治法就是将一个复杂的问题分成多个相对简单的独立问题进行求解，并且综合所有简单问题的解可以组成这个复杂问题的解。例如快速排序算法就是一个分治法的例子。

即将一个大的无序序列排序成有序序列，等于将两个无序的子序列排序成有序，且两个子序列之间满足一个序列的元素普遍大于另一个序列中的元素。

最通俗、简单的分治算法思想

分治算法的基本思想是将一个计算复杂的问题分为规模较小，计算简单的小问题求解 ，然后综合各个小问题，而得到最终问题的答案。分治算法的执行过程如下： ♦对于一个规模为N的问题，若该问题可以容易地解决（比如说规模N较小），则直接解决，否则执行下面的步骤。

♦将该分解为M个规模较小的子问题，这些子问题互相独立，并且与原问题形式相同。

♦递归地解这些子问题。 ♦然后，将各子问题的解合并得到原问题的解。 问：一个袋子里有30个硬币，其中一枚是假币，并且假币和真币一模一样，肉眼很难分辨，目前只知道假币比真币重量轻一点。请问如何区分出假币呢? 可以采用递归分治的思想来求解这个问题： ♦首先为每个银币编号，然后可以将所有的银币等分为两分，放在天平的两边。

这样就将区分30个硬币的问题，变为区别两堆硬币的问题。 ♦因为假银币的分量较轻，因此天平较轻的一侧中一定包含假银币。 ♦再将较轻的一侧中的硬银币等分为两分，重复上述的做法。

♦直到剩下2枚硬银币，可用天平直接找出假银币来。

分治算法几个经典例子

分治法，字面意思是“分而治之”，就是把一个复杂的1问题分成两个或多个相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并，这个思想是很多高效算法的基础。 图一 例如排序算法(快速排序，归并排序)，傅里叶变换(快速傅里叶变换)等。

分治法的基本思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治算法

算法步骤：1 ：从左上角起，给棋盘编号（1，1），（1，2），。（8，8），计为集合qp。

tracks记录走过的每个点. （可以想象为坐标（x,y））2：设起点为（1，1），记为 当前位置 cp，3：搜索所有可走的下一步，根据“马行日”的走步规则，可行的点的坐标是x坐标加减1，y坐标加减2，或是x加减2，y加减1； （例如起点（1，1），可计算出（1+1，1+2），（1+1，1-2），（1-1，1+2），（1-1，1-2），（1+2，1+1），（1+2，1-1），（1-2，1+1），（1-2，1-1） 共8个点）， 如果没有搜到可行点，程序结束。4：判断计算出的点是否在棋盘内，即是否在集合qp中；判断点是否已经走过，即是否在集合tracts中，不在才是合法的点。（在上面的举例起点（1，1），则合法的下一步是（2，3）和 （3，2））5：将前一步的位置记录到集合tracts中，即tracts.add（cp）；选择一个可行点，cp=所选择点的坐标。

6：如果tracts里的点个数等于63，退出程序，否则回到步骤3继续执行。