第13章 回溯法.ppt

第13章回溯法
上海第二工业大学温敬和
******@it.
2008年4月27日
1
引言
3着色问题
8皇后问题
一般回溯方法
分枝限界法(略)
2
引言
寻找一个问题解时,一个直观的方法是:列出所有候选解,然后依次检查每一个。在检查完部分或全部候选解,便可得出该问题或者有解、或者没有解,这就是所谓的穷举法。
在理论上,这种方法似乎是可行的,但是在实际应用中很少使用这种方法。这是因为候选解的数量非常大,通常是指数级的,甚至是阶乘级的,即便采用最快的计算机,也只能解决规模很小的问题。
因此需要一种系统化的检查候选解的方法,借助这种方法,将搜索空间减少到最低程度。这种系统并且有组织的搜索方法,称为回溯法。在本章中先讨论图的三着色问题的回溯法解,然后再讨论8皇后问题的回溯法解。
3
图的三着色问题
给出一个无向图G=(V,E),需用三种颜色之一为图中的每个结点着色,三种颜色分别用1、2、3来表示。若没有二个邻接结点有相同的颜色,则称着色是合法的。只要有二个邻接结点颜色相同,则称着色是不合法的。
具有n个结点的图的一种着色,可用向量(c1,c2,...cn)来表示,0≤Ci≤3,i表示结点号,0表示没有着色。
例如,(1,2,2,1,3)表示一个有5个结点的图的着色。其中结点1的着色为1,结点2的着色为2,……,结点5的着色为1。
(1)、(1,2)、(1,2,2)、(1,2,2,1)是不完全着色,称为求解过程中的部分解。
4
○
○○○
○○○○○○○○○

.......
........
3着色的搜索树
一个具有n个结点的图的着色有3n种可能(合法的和非法的),可用一棵完全三叉树来表示,称为搜索树。在这棵树中,从根结点到叶结点的每一条路径代表一种着色方案。
结点1着色
结点2着色
结点n着色
5
回溯法是通过每次增加一个结点来寻求解。
如果从根结点到当前结点的路径长度等于结点数n,并且是一个合法着色,则过程停止(除非要求获得多个解)。
如果这条路径小于n,并且相应的部分着色是合法的,那么就生成现结点的子结点,并将该子结点标记为现结点。
如果对应的路径不是部分解,那么现结点标记为死结点,并生成对应于另一种颜色的新结点。如果所有的三种颜色都试过且没有成功,就回溯到父结点,改变父结点的颜色。
依次类推,直至有解或无解。
若回溯到根结点,所有的三种颜色都试过且没有成功,说明问题无解。
6
①
②③
④⑤
○

○

● ○

● ○

○

● ● ○
当生成第2个结点时,发现(1,1)不是部分解,因此该结点被标记为死结点。然后指派颜色2,经检查(1,2)是部分解。
当生成第3个结点时,发现(1,2,1)不是部分解,因此该结点被标记为死结点。然后指派颜色2,经检查(1,2,2)是部分解。
……
无向图G
第2个结点
第3个结点
第4个结点
第5个结点
根结点
第1个结点
C1=1
C2=2
C3=2
C4=1
C5=3
●表示死结点
7
输入:无向图G=(V,E)
输出:图的结点3着色向量c[1..n],0≤c[j] ≤3(1≤j≤n)。
1. c[1..n]←0 //c[1..n]为全局量
2. GraphColorRec(1)
过程
0. procedure GraphColorRec(k)
1. for color←1 to 3
2. c[k]←color
3. if c为合法着色 then //部分解或解
4. if k<n then //部分解
5. GraphColorRec(k+1) //进入下一个结点
6. else //是解
7. output c[1..n] and exit
8. end if
9. end if
10. end for
11. end procedure
3-ColorRec(递归解Page219)
现为结点k着色,说明c[1..k-1]是合法着色。着色合法与否,只要检查与k邻接的结点的着色即可。这样可从结点1扫描至结点k-1,此时需使用邻接矩阵。
8
①
②③
④⑤
c[1]=1√
GraphColorRec(2)
c[2]=1×
c[2]=2√
GraphColorRec(3)
c[3]=1×
c[3]=2√
GraphColorRec(4)
c[4]=1√
GraphColorRec(5)
c[5]=1×
c[5]=2×
c[5]=3√
GraphColorRec(5)
输出解并退出
1
2
2
1
3
k=1
color=1
k=2