首页 > 代码库 > 分治法-汉诺塔问题

分治法-汉诺塔问题

一 基本概念

分治法,顾名思义分而治之的意思,就是把一个复杂的问题分成两个或很多其它的同样或相似的子问题,再把子问题分成更小的子问题……直到最后子问题能够简单的直接求解,原问题的解即子问题的解的合并


基本思想及策略

  分治法的设计思想是:将一个难以直接解决的大问题,切割成一些规模较小的同样问题,以便各个击破,分而治之。

  分治策略是:对于一个规模为n的问题,若该问题能够easy地解决(比方说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式同样,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这样的算法设计策略叫做分治法。

  假设原问题可切割成k个子问题,1<k≤n,且这些子问题都可解并可利用这些子问题的解求出原问题的解,那么这样的分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这样的情况下,重复应用分治手段,能够使子问题与原问题类型一致而其规模却不断缩小,终于使子问题缩小到非常easy直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟,常常同一时候应用在算法设计之中,并由此产生很多高效算法。

三、分治法特征

    分治法所能解决的问题一般具有下面几个特征:

    1)该问题的规模缩小到一定的程度就能够easy地解决

    2)该问题能够分解为若干个规模较小的同样问题,即该问题具有最优子结构性质

    3)利用该问题分解出的子问题的解能够合并为该问题的解

    4)该问题所分解出的各个子问题是相互独立的,即子问题之间不包括公共的子问题

第一条特征是绝大多数问题都能够满足的,由于问题的计算复杂性通常是随着问题规模的添加?而添加?;

第二条特征是应用分治法的前提它也是大多数问题能够满足的,此特征反映了递归思想的应用;、

第三条特征是关键,是否能利用分治法全然取决于问题是否具有第三条特征,假设具备了第一条和第二条特征,而不具备第三条特征,则能够考虑用贪心法或动态规划法

第四条特征涉及到分治法的效率,假设各子问题是不独立的则分治法要做很多不必要的工作,反复地解公共的子问题,此时尽管可用分治法,但一般用动态规划法较好

四、基本步骤

分治法在每一层递归上都有三个步骤:

    1分解:将原问题分解为若干个规模较小,相互独立,与原问题形式同样的子问题;

    2解决:若子问题规模较小而easy被解决则直接解,否则递归地解各个子问题

    3合并:将各个子问题的解合并为原问题的解。

它的一般的算法设计模式例如以下:

    Divide-and-Conquer(P)

    1.if |P|≤n0

    2.then return(ADHOC(P))

    3.P分解为较小的子问题P1,P2 ,...,Pk

    4.for i←1 to k

    5.do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi

    6.T ← MERGE(y1,y2,...,yk) △ 合并子问题

    7.return(T)

   当中|P|表示问题P的规模;n0为一阈值,表示当问题P的规模不超过n0时,问题已easy直接解出,不必再继续分解。ADHOC(P)是该分治法中的基本子算法,用于直接解小规模的问题P。因此,当P的规模不超过n0时直接用算法ADHOC(P)求解。算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法,用于将P的子问题P1,P2 ,...,Pk的对应的解y1,y2,...,yk合并为P的解。


五、分治法的复杂性分析

   一个分治法将规模为n的问题分成k个规模为nm的子问题去解。设分解阀值n0=1,且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用mergek个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间,则有:

 Tn=k T(n/m)+f(n)

    通过迭代法求得方程的解:

   递归方程及其解仅仅给出n等于m的方幂时T(n)的值,可是假设觉得T(n)足够平滑,那么由n等于m的方幂时T(n)的值能够预计T(n)的增长速度。通常假定T(n)是单调上升的,从而当         mi≤n<mi+1时,T(mi)≤T(n)<T(mi+1)



六、根据分治法设计程序时的思维过程


   实际上就是类似于数学归纳法,找到解决本问题的求解方程公式,然后依据方程公式设计递归程序。

1、一定是先找到最小问题规模时的求解方法

2、然后考虑随着问题规模增大时的求解方法

3、找到求解的递归函数式后(各种规模或因子),设计递归程序就可以。


七 分治法解决汉诺塔问题事例

对于n个盘子的汉诺塔问题,总有3根柱子,当前全部n个盘子都在柱子a上,那么怎样通过柱子b将全部盘子挪到柱子c上?

对于n=1,好吧,从a到c没有问题;

假设n>1,能够考虑为a有两个盘子一个是最以下的盘子,一个是上面的n-1个盘子(n-1个盘子看作一个总体),那么问题就是首先将n-1个盘子挪到b柱子上,然后把最以下的盘子放到c柱子上;

剩下的问题就是怎样将n-1个盘子由b挪到c上。

非常明显,我们採用数学归纳法找到了解决方式。


代码1 汉诺塔实现代码

using System;

namespace hannoi
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			hannoi (4, ‘a‘, ‘b‘, ‘c‘);
		}

		/// <summary>
		/// n个盘,由a经由b放置在c
		/// </summary>
		/// <param name="n">盘子总数</param>
		/// <param name="a">n个盘子当前所在的柱子.</param>
		/// <param name="b">可中转的柱子.</param>
		/// <param name="c">n个盘子终于要放置的柱子.</param>
		static void hannoi(int n, char a, char b, char c)
		{
			//仅仅剩下一个盘子,那就由a直接到c
			if (n == 1) {
				Console.WriteLine (a.ToString() + "->" + c.ToString());
				return;
			}

			//递归n-1个盘子,由a放置到b
			hannoi (n - 1, a, c, b);
			//a上剩下的一个盘子,由a拿到c,输出出来
			Console.WriteLine (a.ToString() + "->" + c.ToString());
			//b上有n-1个盘子,将这n-1个盘子递归放到c上
			hannoi (n - 1, b, a, c);
		}
	}


}


执行结果:


八 经常使用的分治法算法

(1)二分搜索

(2)大整数乘法
 (3)Strassen矩阵乘法
(4)棋盘覆盖
(5)合并排序
(6)高速排序
(7)线性时间选择
(8)最接近点对问题
(9)循环赛日程表
(10)汉诺塔

注:參考文章:http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741370.html