资源描述：
《第 5 章 艰苦卓绝》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第5章艰苦卓绝回溯算法5.1组合问题与回溯算法•很多现实问题中，合法的解可能要通过在一个大量但有限多种可能性中做穷尽搜索才能获得，这样的问题通常称之为组合问题。•一种通用的称为回溯的搜索技巧用来在穷尽搜索过程中，能避免搜索所有的可能情形。它普遍地适用于解决需要检测有限但却是大量的可能解的组合问题。3-着色问题•1．问题的理解与描述•假定图G的顶点集合为V={1,2,…,n}，则3-着色问题形式化为：•输入：图G=。•输出：若G存在各顶点的合法着色方案，输出所有解向量c=，其中1≤c≤312ni为
2、G的第i个顶点的着色，且对∀(i,j)∈E，c≠ic。否则输出无解信息。j树根abca=1de(a)b=2b=3b=1c=1c=2c=3c=1c=2c=3d=1d=3d=1d=2d=2d=3e=1e=2e=3e=1e=2e=3e=1e=2e=3e=1e=2e=3(b)•(a)表示图G，我们要对其顶点用颜色{1,2,3}来着色。(b)部分展示了合法着色方案形成过程中搜索树的路径。首先，在产生出第三个结点后，发现着色方案<1,1>不是合法部分解，所以该节点在图中用×标识为死结点。接着b涂成颜色2，这样着色方案<1,2>看起来是
3、一个部分解。于是产生一个对应于顶点b的新的孩子结点，其初始着色为1。重复上述过程，最终将得到一个合法的着色方案<1,2,2,1,3>。2．算法的伪代码描述•THREE-COLOR(G)•1flag←false•2为解向量x分配存储空间•3GRAPHCOLOR(1)从根起对以下第1层节点进行搜索•4ifflag=false•5thenprint"nosolution."•GRAPH-COLOR(k)•1ifk>n判断是否为完整解•2thenflag←true•3printx•4return•5forcolor←1to3
4、对当前第k个顶点逐一检测3种可能的着色•6dox[k]←color•7fori←1tok-1•8doifi,k在G中相邻且x[i]=x[k]•9then检测x[k]的下一种着色•10GRAPH-COLOR(k+1)进入下一层搜索3．算法的运行时间•注意在最坏情形下将产生Θ(3n)个节点，对每一个产生的节点（x[k]的一个取值）第7～9行判断其是否能与x[1...k-1]一起，使得x[1...k]构成一个部分解需要用Θ(n)时间。所以，最坏情形下总的运行时间为Θ(n3n)。5.1.2n-皇后问题•如何在一个8×8的棋盘上放
5、置8个皇后使得任意两个皇后之间不能相互攻击？(a)(b)1．问题的理解与描述•我们将n-皇后问题形式化为：•输入：棋盘规模n。•输出：如果此n×n棋盘存在合法格局，则输出所有由向量x=，其中，x,12n1x,…,x是1,2,…,n的一个排列，且∀（1i≠2njn）有x–x≠i–j且x–x≠j–i决定的格局：ijij棋盘上的第i行第x格放置一个皇后，i=1,i2,…,n。否则，输出无解信息。x1=2x2=4Xx3=1x4=3对于n=4的情形，x置为1且x置为1。这将导致一个死节点，因为这12两个皇后置于
6、同一列中。若x置为2也将发生同样的结果，因为这两2个皇后置于同一斜线上。将x置为3将导致一个部分解向量<1,3>且探2索对x寻求一个值。如图中所示，无论x假设为何值，都不会得到33x=1,x=3及x>0的部分解。所以搜索回溯到第二层并对x赋予一个新1232的值，即4。如图所示，这导致了部分解向量<1,4,2>。此向量还是不能被扩展，在产生出一些新的节点后，搜索回到第一层。现在，x增1加为2，以同样的方式，找到部分解向量<2,4,1>。如此，此向量被扩展为合法向量<2,4,1,3>，这就对应一个合法解。2．算法的伪代码描述•
7、N-QUEENS(n)•1flag←false•2为解向量x分配存储空间•3PLACE(1)从根起对以下第1层节点进行搜索•4ifflag=false•5thenerror"nosolution"••PLACE(k)•1ifk>n判断是否为完整解•2thenflag←ture•3fori←1ton•4do输出棋盘中第i行格局•5return•6forcolum←1ton对当前第k行逐一检测各种可能的位置•7dox[k]←colum•8fori←1tok-1•9doifx[i]=x[k]or
8、x[i]–x[k]
9、=
10、i
11、–k
12、•10then检测第k行的下一个置放位置•11PLACE(k+1)进入下一层搜索3．算法的运行时间•在最坏情形下将产生完全n叉树中Θ(nn)个节点，对每一个产生的节点（x[k]的一个取值）第8～10行判断其是否能与x[1...k-1]一起，使得x[1...k]构成一个部分解需要用Θ(n)时间。所
