回溯法,图的着色.doc

用回溯算法解决问题的一般步骤为:
一、定义一个解空间,它包含问题的解。
二、利用适于搜索的方法组织解空间。
三、利用深度优先法搜索解空间。
四、利用限界函数避免移动到不可能产生解的子空间。
问题的解空间通常是在搜索问题的解的过程中动态产生的,这是回溯算法的一个重要特性。
回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时,总是先判断该结点是否肯定不包含问题的解。如果肯定不包含,则跳过对以该结点为根的子树的系统搜索,逐层向其祖先结点回溯。否则,进入该子树,继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时,只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法,它适用于解一些组合数较大的问题.
递归回溯:由于回溯法是对解空间的深度优先搜索,因此在一般情况下可用递归函数来实现回溯法如下:
procedure try(i:integer);
var
begin
if i>n then 输出结果
else for j:=下界 to 上界 do
begin
x:=h[j];
if 可行{满足限界函数和约束条件} then begin 置值;try(i+1); end;
end;
end;
说明:
i是递归深度;
n是深度控制,即解空间树的的高度;
可行性判断有两方面的内容:不满约束条件则剪去相应子树;若限界函数越界,也剪去相应子树;两者均满足则进入下一层;
搜索:全面访问所有可能的情况,分为两种:不考虑给定问题的特有性质,按事先顶好的顺序,依次运用规则,即盲目搜索的方法;另一种则考虑问题给定的特有性质,选用合适的规则,提高搜索的效率,即启发式的搜索。
回溯即是较简单、较常用的搜索策略。
基本思路:若已有满足约束条件的部分解,不妨设为(x1,x2,x3,……xi),I<n,则添加x(i+1)属于s(i+2),检查(x1,x2,……,xi,x(i+1))是否满足条件,满足了就继续添加x(i+2)、s(i+2),若所有的x(i+1)属于s(i+1)都不能得到部分解,就去掉xi,回溯到(xi,x2,……x(i-1)),添加那些未考察过的x1属于s1,看其是否满足约束条件,为此反复进行,直至得到解或证明无解。
回溯的设计
.

【例1】从1到X这X个数字中选出N个,排成一列,相邻两数不能相同,求所有可能的排法。每个数可以选用零次、一次或多次。例如,当N=3、X=3时,排法有12种:121、123、131、132、212、213、231、232、312、313、321、323。
【分析】以N=3,X=3为例,这个问题的每个解可分为三个部分:第一位,第二位,第三位。先写第一位,第一位可选1、2或3,根据从小到大的顺序,我们选1;那么,为了保证相邻两数不同,第二位就只能选2或3了,我们选2;最后,第三位可以选1或3,我们选1;这样就得到了第一个解"121"。然后,将第三位变为3,就得到了