回溯法,图着色.doc

回溯法,图的着色1回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。用回溯算法解决问题的一般步骤为:一、定义一个解空间,它包含问题的解。二、利用适于搜索的方法组织解空间。三、利用深度优先法搜索解空间。四、利用限界函数避免移动到不可能产生解的子空间。问题的解空间通常是在搜索问题的解的过程中动态产生的,这是回溯算法的一个重要特性。回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时,总是先判断该结点是否肯定不包含问题的解。如果肯定不包含,则跳过对以该结点为根的子树的系统搜索,逐层向其祖先结点回溯。否则,进入该子树,继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时,只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法,:由于回溯法是对解空间的深度优先搜索,因此在一般情况下可用递归函数来实现回溯法如下:proceduretry(i:integer);varbeginifi>nthen输出结果elseforj:=下界to上界dobeginx:=h[j];if可行{满足限界函数和约束条件}thenbegin置值;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,就得到了第二个解"123"。此时,第三位已经不能再取其他值