厦门理工算法设计与分析(第五章)

第五章

回溯法2/7/20231计算机算法设计与分析计算机求解的过程求解过程可看成在状态空间从初始状态出发搜索目标状态(解所在状态)的过程。状态空间初始状态目标状态搜索可描述为：S0S1…Sn，S0为初态，Sn为终态。或者ψ(S0)且φ(Sn)，这里ψ称为初始条件，φ称为终止条件。2/7/20232计算机算法设计与分析求解是状态空间的搜索求解的过程可以描述为对状态空间的搜索其中S0为初始状态，不妨设Sni为终止状态S0S11S12…S1k………………Sn1……Sni……SnmS0于是问题的求解就是通过搜索寻找出一条从初始状态S0到终止状态Sni的路径。Sni2/7/20233计算机算法设计与分析几种搜索方法状态空间的搜索实际上是一种树/DAG的搜索，常用的方法有：广度优先的搜索：深度优先的搜索：启发式的搜索：从初始状态开始，逐层地进行搜索。从初始状态开始，逐个分枝地进行搜索。从初始状态开始，每次选择最有可能达到终止状态的结点进行搜索。2/7/20234计算机算法设计与分析三种搜索的比较理论上广度优先搜索与深度优先搜索的时间复杂性都是指数级。但在实际上深度优先搜索的时间复杂性要低，在空间复杂性更要低得多。广度优先搜索是一定能找到解；而深度优先搜索在理论上存在找不到解的可能。启发式搜索是最好优先的搜索，若评价函数设计得好则能较快地找到解，降低时间复杂性；因而评价函数的优劣决定了启发式搜索的优劣。另外评价函数本身的开销也是很重要的。2/7/20235计算机算法设计与分析树搜索的一般形式SearchTree(SpaceT){ok=0;L=T.initial;while(!ok||L≠){a=L.first;if(aisgoal)ok=1elseControl-put-in(L,Sons(a));}ok表示搜索结束。将初始状态放入L。从L中取出第一个元素。若a是终态则结束。否则，将a的儿子们以某种控制方式放入L中。表L用来存放待考察的结点。2/7/20236计算机算法设计与分析三种搜索的不同之处树的三种搜索方法的不同就在于它们对表L使用了不同控制方式：L是一个队列L是一个栈L的元素按照某方式排序广度优先搜索深度优先搜索启发式搜索其中，深度优先搜索就是回溯法。2/7/20237计算机算法设计与分析递归回溯法的一般形式Try(s){做挑选候选者的准备；while(未成功且还有候选者){挑选下一个候选者next；if(next可接受){记录next；if(满足成功条件){成功并输出结果}elseTry(s+1);if(不成功)删去next的记录;}}return成功与否}Try(s+1)意味着按照这条分支继续尝试。Try(s+1)返回后，若不成功，则意味着这条分支失败了。这时必须删除原来记录。2/7/20238计算机算法设计与分析迭代回溯法的一般形式先让我们回顾解空间搜索的一般形式：SearchTree(SpaceT)//{Ok=0;L=T.initial;while(!Ok||L≠Φ){a=L.first;//从L中取出第一个元素

if(aisgoal)Ok=1elseControl-put-in(L,Sons(a));}Ok表示是否找到解。表L存放待考察结点。对L的控制方式不同，则搜索方法也不同。在回溯法中，控制方式是栈。初始将根节点放入L中。2/7/20239计算机算法设计与分析迭代回溯法的一般形式先让我们回顾解空间搜索的一般形式：SearchTree(SpaceT)//{Ok=0;L=T.initial;while(!Ok||L≠){a=L.first;if(aisgoal)Ok=1elseControl-put-in(L,Sons(a));}从L中取出第一个元素。在栈操作中就是弹出栈顶元素。在通常求解问题时，解是由逐个状态构成的。因此，这里还需要判断状态是否可接受，并进行纪录路径等工作。2/7/202310计算机算法设计与分析迭代回溯法的一般形式先让我们回顾解空间搜索的一般形式：SearchTree(SpaceT)//{Ok=0;L=T.initial;while(!Ok||L≠){a=L.first;if(aisgoal)Ok=1elseControl-put-in(L,Sons(a));}若a可接收但未终止，则要将a的后继压入栈中。若要抛弃状态a，当a是最后的儿子时，还需要消除原有的纪录甚至回溯一步。2/7/202311计算机算法设计与分析如何判断最后一个儿子？若只要遍历解空间树的结点，那么将各结点按栈方式控制便可实现深度为主搜索。在求解问题时，需要记录解的路径，在回溯时还需要删除结点和修改相应信息。栈中结点应该分层次，而却没有区分其层次。这就增加了回溯判断和操作的困难。怎么办呢？2/7/202312计算机算法设计与分析如何判断最后一个儿子？若只要遍历解空间树的结点，那么将各结点按栈方式控制便可实现深度为主搜索。在求解问题时，需要记录解的路径，在回溯时还需要删除结点和修改相应信息。栈中结点应该分层次，而却没有区分其层次。这就增加了回溯判断和操作的困难。采用一个简洁有效的方法：设计一个末尾标记，每次压栈时，先压入末尾标记。2/7/202313计算机算法设计与分析用末尾标记的迭代回溯Backtrack(TreeT){Ok=0;L.Push(T.root);while(!Ok||L≠){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal){Ok=1;Output()}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}若栈顶元素是末尾标记，说明这个路径已经到头了，需要回溯一步。××末尾2/7/202314计算机算法设计与分析用末尾标记的迭代回溯Backtrack(TreeT){Ok=0;L.Push(T.root);while(!Ok||L≠){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal){Ok=1;Output()}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}若a是可以接受的，则将a加入求解的路径中。2/7/202315计算机算法设计与分析用末尾标记的迭代回溯Backtrack(TreeT){Ok=0;L.Push(T.root);while(!Ok||L≠){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal){Ok=1;Output()}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}若a是目标节点，则结束搜索并输出求解的路径。2/7/202316计算机算法设计与分析用末尾标记的迭代回溯Backtrack(TreeT){Ok=0;L.Push(T.root);while(!Ok||L≠){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal){Ok=1;Output()}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}若a不是目标节点且a有后继，则将a的后继压入栈中。2/7/202317计算机算法设计与分析用末尾标记的迭代回溯Backtrack(TreeT){Ok=0;L.Push(T.root);while(!Ok||L≠){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal){Ok=1;Output()}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}若a不是目标节点又没有后继，则将a从解的路径中删除。2/7/202318计算机算法设计与分析用末尾标记的迭代回溯Backtrack(TreeT){Ok=0;L.Push(T.root);while(!Ok||L≠){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal){Ok=1;Output()}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}注意：这里的L.Push-Sons(a)要先压入末尾标记，然后再压入后继结点。2/7/202319计算机算法设计与分析用末尾标记的迭代回溯Backtrack(TreeT){Ok=0;L.Push(T.root);while(!Ok||L≠){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal){Ok=1;Output()}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}a既不是目标又没有后继，则将a删除。请注意Move-off与Backstep的区别。×2/7/202320计算机算法设计与分析Backastep与Move-offBackstep的动作：××末尾Move-off的动作：×非末尾Move-off需要做的只是删除自身的记录而转向兄弟结点。而Backstep除此之外，还需要删除父节点的记录而转向叔叔结点。2/7/202321计算机算法设计与分析迭代回溯法的一般形式Backtrack(TreeT){Ok=0;L.Push(T.root);while(!Ok||L≠){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal){Ok=1;Output()}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}2/7/202322计算机算法设计与分析不可接受的结点破坏了解的相容条件的结点超出了状态空间的范围，或者说不满足约束条件，的结点；评价值很差的结点，即已经知道不可能获得解的结点；已经存在于被考察的路径之中的结点，这种结点会造成搜索的死循环。2/7/202323计算机算法设计与分析N后问题要求在一个n×n的棋盘上放置n个皇后，使得她们彼此不受攻击。按照国际象棋的规则，一个皇后可以攻击与之同一行或同一列或同一斜线上的任何棋子。因此，N后问题等价于：要求在一个n×n的棋盘上放置n个皇后，使得任意两个皇后不得在同一行或同一列或同一斜线上。2/7/202324计算机算法设计与分析用递归回溯法求N后问题Try(s){做挑选候选者的准备；while(未成功且还有候选者){挑选下一个候选者next；if(next可接受){记录next；if(满足成功条件){成功并输出结果}elseTry(s+1);if(不成功)删去next的记录;}}return成功与否}让我们先回顾递归回溯法的一般形式：

2/7/202325计算机算法设计与分析用递归回溯法求N后问题Try(s){做挑选候选者的准备；while(未成功且还有候选者){挑选下一个候选者next；if(next可接受){记录next；if(满足成功条件){成功并输出结果}elseTry(s+1);if(不成功)删去next的记录;}}return成功与否}s为准备放置后的行数。候选者为0到n–1列。2/7/202326计算机算法设计与分析用递归回溯法求N后问题Try(s){

while

if(next可接受){记录next；if(满足成功条件){成功并输出结果}elseTry(s+1);if(不成功)删去next的记录;}}return成功与否}j=–1;q=0;令列标志j为–1

，q表示未成功。(未成功且还有候选者){(!q&&j<n){列数不到n就还有候选者。挑选下一个候选者next；列数加一即为next。j++;2/7/202327计算机算法设计与分析用递归回溯法求N后问题Try(s){

while

if记录next；if(满足成功条件){成功并输出结果}elseTry(s+1);if(不成功)删去next的记录;}}return成功与否}j=–1;q=0;(!q&&j<n){j++;(next可接受){放置后各后都安全，便可接受。用函数Safe(s,j)进行位置(s,j)是否安全的判断。(Safe(s,j)){2/7/202328计算机算法设计与分析用递归回溯法求N后问题Try(s){

while

if

if(满足成功条件){成功并输出结果}elseTry(s+1);if(不成功)删去next的记录;}}return成功与否}j=–1;q=0;(!q&&j<n){j++;记下该行后的位置(列数)。用函数Record(s,j)记下位置(s,j)。(Safe(s,j)){记录next；Record(s,j);2/7/202329计算机算法设计与分析用递归回溯法求N后问题Try(s){

while

if

ifelseTry(s+1);if(不成功)删去next的记录;}}return成功与否}j=–1;q=0;(!q&&j<n){j++;n行后都放完就成功了。

q赋值为1，表示已经完成，退出循环。(Safe(s,j)){Record(s,j);(满足成功条件){成功并输出结果}(s=

=n–1){q=1;Output();}2/7/202330计算机算法设计与分析用递归回溯法求N后问题Try(s){

while

if

ifelseTry(s+1);ifreturnj=–1;q=0;(!q&&j<n){j++;(Safe(s,j)){Record(s,j);(s=

=n–1){q=1;Output();}未完成，放s+1行。(不成功)删去next的记录;}}不成功，删去后在该行的位置。(!q)Move-off(s,j);}}}成功与否}q}2/7/202331计算机算法设计与分析用递归回溯法求N后问题Try(s){

while

if

ifelseTry(s+1);ifreturnj=–1;q=0;(!q&&j<n){j++;(Safe(s,j)){Record(s,j);(s==n–1){q=1;Output();}q}(!q)Move-off(s,j);}}}现在便得到了求N后的回溯程序。2/7/202332计算机算法设计与分析求解N后问题中的数据表示数组B[n]表示棋盘。若B[i]=j，0≤i,j＜n，表示棋盘的第i行第j列上有皇后。数组C[j]=1表示第j列上无皇后，0≤j＜n。数组D[k]=1表示第k条下行对角线(↘)上无皇后。这里k=i+j，0≤k≤2(n–1)。0123450123452/7/202333计算机算法设计与分析求解N后问题中的数据表示数组B[n]表示棋盘。若B[i]=j，0≤i,j＜n，表示棋盘的第i行第j列上有皇后。数组C[j]=1表示第j列上无皇后，0≤j＜n。数组D[k]=1表示第k条下行对角线(↘)上无皇后。这里k=i+j，0≤k≤2(n–1)。数组U[k]=1表示第k条上行对角线(↗)上无皇后。这里k=i–j，–n+1≤k≤n–1。0123450123452/7/202334计算机算法设计与分析求解N后问题中的子程序Record(s,j){k=s–j+n–1;B[s]=j;C[j]=0;D[s+j]=0;U[k]=0;}Move-off(s,j){k=s–j+n–1;B[s]=-1;C[j]=1;D[s+j]=1;U[k]=1;}Safe(s,j){k=s–j+n–1;if(C[j]==1&&U[k]==1&&D[s+j]==1)returntrueelsereturnfalse;}此处k是上行对角线的下标，为什么要进行这样一个计算呢？2/7/202335计算机算法设计与分析求解N后问题的主程序N-Queens(){intB[n],C[n],D[2n–1],U[2n–1];for(j=0,j<n;j++){B[j]=-1;C[j]=1;U[2j]=1;U[2j+1]=1;D[2j]=1;D[2j+1]=1;}try(0);Output(B);}将数组B[],C[],U[]和D[]都赋予初值。从第一行开始递归2/7/202336计算机算法设计与分析N后问题的迭代程序先看看迭代回溯法的一般形式：2/7/202337计算机算法设计与分析N后问题的迭代程序Backtrack(TreeT){Ok=0;while(!Ok||L≠){a=L.Pop();ifelseif(aisgood){Record(a);if(aisgoal){Ok=1;Output();}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}L.Push(T.root);(aisthelastmark)Backastep();迭代从第一行(行号为0）开始，将第一行的0～n–1列和n压入栈中，这里n作为末尾标记。2/7/202338计算机算法设计与分析N后问题的迭代程序Backtrack(TreeT){Ok=0;while(!Ok||L≠){a=L.Pop();ifelseif(aisgood){Record(a);if(aisgoal){Ok=1;Output();}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}L.Push(T.root);(aisthelastmark)Backastep();i=0;L.Push(n,

0,1,2,…);栈指针p<0，即栈为空。a是末尾标记则回溯。p>=0)2/7/202339计算机算法设计与分析N后问题的迭代程序Backtrack(TreeT){Ok=0;while(!Ok||p>=0){a=L.Pop();ifelseif(aisgood){Record(a);if(aisgoal){Ok=1;Output();}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}(aisthelastmark)Backastep();i=0;L.Push(n,0,1,2,…);(a=

=n)Backastep;回溯需要退回一行，即i–

–;同时删除该行的原纪录。2/7/202340计算机算法设计与分析N后问题的迭代程序Backtrack(TreeT){Ok=0;while(!Ok||p>=0){a=L.Pop();ifelseif(aisgood){Record(a);if(aisgoal){Ok=1;Output();}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}i=0;L.Push(n,0,1,2,…);(a=

=0)Backastep;(a==n){i–

–;a=B[i];Move-off(i,a);}若置放后的位置是安全的，则是好的位置。现设有谓词safe(i,a)表示第i行第a列是安全的位置。2/7/202341计算机算法设计与分析N后问题的迭代程序Backtrack(TreeT){Ok=0;while(!Ok||p>=0){a=L.Pop();ifelseifif(aisgoal){Ok=1;Output();}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}i=0;L.Push(n,0,1,2,…);(a==n)

{i–

–;a=B[i];Move-off(i,a);}(Safe(i,a))

{Record(i,a);如果safe(i,a)，则放下后，即Record(a)。2/7/202342计算机算法设计与分析N后问题的迭代程序Backtrack(TreeT){Ok=0;while(!Ok||p>=0){a=L.Pop();ifelseifif(aisgoal){Ok=1;Output();}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}i=0;L.Push(n,0,1,2,…);(a==n){i–

–;a=B[i];Move-off(i,a);}(Safe(i,a)){Record(i,a);如果到了第n行，则成功。(i=

=n–1)2/7/202343计算机算法设计与分析N后问题的迭代程序Backtrack(TreeT){Ok=0;while(!Ok||p>=0){a=L.Pop();ifelseifif(aisgoal){Ok=1;Output();}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}i=0;L.Push(n,0,1,2,…);(a==n){i–

–;a=B[i];Move-off(i,a);}(Safe(i,a)){Record(i,a);(i=

=n–1){i++;L.Push(n,

0,1,2,…);}}}}

只要没到第n行，则总是有后继的。2/7/202344计算机算法设计与分析N后问题的迭代程序Backtrack(TreeT){Ok=0;while(!Ok||p>=0){a=L.Pop();ifelseifif(aisgoal){Ok=1;Output();}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}i=0;L.Push(n,0,1,2,…);(a==n){i–

–;a=B[i];Move-off(i,a);}(Safe(i,a)){Record(i,a);{i++;L.Push(n,0,1,2,…);}}}}

于是就得到了N后问题的迭代程序。注：这里的几个子程序与递归程序中的完全相同。(i=

=n–1)请同学们自己考虑栈的操作。2/7/202345计算机算法设计与分析迭代回溯解N后问题的主程序N-Queens(n){intB[n],C[n],D[2n–1],U[2n–1];T[n2];for(j=0,j<n;j++){B[j]=-1;C[j]=1;U[2j]=1;U[2j+1]=1;D[2j]=1;D[2j+1]=1;}intp=–1;//栈初始化为空//Backtrack(n,B);}T[]为栈，最多能有n2个候选者。2/7/202346计算机算法设计与分析N后问题的时间复杂性如果只要找出N后问题的一个解，那么这是一个求路径的问题。求路径：只需要找到一条路径便可以得到解。设每个状态有k个后继，其搜索树为K叉树，其结点总数为kn+1–1，遍历的时间为O(kn)，这里n为找到解的路径长度。N后问题的路径深度为n，可选择的后继有n个，所以时间复杂性为O(nn)。2/7/202347计算机算法设计与分析旅行售货员问题TSP：某售货员到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条路线，经过每个城市一遍最后回到驻地的路线，使得总的路程(或总旅费)最小。设G=(V,E)是一个带权图。图中各边的费用(权值)为正。图中一条周游路线是包括V中所有顶点的回路。一条周游路线的费用是该路线上所有边的费用之和。所谓旅行售货员问题就是要在图G中找出一条最小费用的周游路线。2/7/202348计算机算法设计与分析考虑TSP的递归回溯算法Try(s){做挑选候选者的准备；while(未成功且还有候选者){挑选下一个候选者next；if(next可接受){记录next；if(满足成功条件){成功并输出结果}elseTry(s+1);if(不成功)删去next的记录;}}return成功与否}线路上第s个结点只需依次考察n–1个结点，即for(i=2;i<=n;i++)下一个候选就是i。2/7/202349计算机算法设计与分析考虑TSP的递归回溯算法Try(s){

if(next可接受){记录next；if(满足成功条件){成功并输出结果}elseTry(s+1);if(不成功)删去next的记录;}}return成功与否}for(i=2;i<=n;i++){结点i尚未在路线中且总耗费值不大。就是将结点i放入路线中并修改耗费值2/7/202350计算机算法设计与分析考虑TSP的递归回溯算法Try(s){

if(满足成功条件){成功并输出结果}elseTry(s+1);if(不成功)删去next的记录;}}return成功与否}for(i=2;i<=n;i++){if(Accept(i)){Record(s,i)；s==n-1若新线路更好，就用新线路取代老线路。2/7/202351计算机算法设计与分析考虑TSP的递归回溯算法Try(s){

elseTry(s+1);

if(不成功)删去next的记录;}}return成功与否}for(i=2;i<=n;i++){if(Accept(i)){Record(s,i)；if(s==n-1){if(better)TakeNewPath();无所谓成功与否，因为每条周游路线都要进行比较。2/7/202352计算机算法设计与分析考虑TSP的递归回溯算法Try(s){

elseTry(s+1);Move-off(s,i)}return}

for(i=2;i<=n;i++){if(Accept(i)){Record(s,i)；if(s==n-1){if(better)TakeNewPath();2/7/202353计算机算法设计与分析TSP的递归回溯算法Try(s){for(i=2;i<=n;i++)if(Accept(i)){Record(s,i)；if(s==n-1)if(better)TakeNewPath();elseTry(s+1);Move-off(s,i)}return}现在便得到了TSP问题的递归回溯算法的程序。2/7/202354计算机算法设计与分析求解TSP的数据结构数组C[n][n]存放个城市间的费用值。数组P[n]记录已经找到的费用最小的周游路线，C为其相应的费用，C初值为∞。数组N[n]记录目前正在寻找的周游路线，NC为其相应的费用；若NC+C[N[n]][1]小于C，则路线N更佳，于是P[]=N[]，C=NC+C[N[n]][1]。若结点next不是N中已有结点，且C大于NC+C[N[i]][next]，则结点next可接受。2/7/202355计算机算法设计与分析TSP的递归程序TryTry(s){for(i=2;i<=n;i++)if(Accept(i)){Record(s,i)；if(s==n-1)if(better)TakeNewPath();elseTry(s+1);Move-off(s,i)}return}2/7/202356计算机算法设计与分析TSP的递归程序TryTry(s){for(i=2;i<=n;i++)ifRecord(s,i)；if(s==n-1)if(better)TakeNewPath();elseTry(s+1);Move-off(s,i)}return}(C–NC>C[N[s]][i]

&&T[i]){数组T[]表示结点i尚未被选2/7/202357计算机算法设计与分析TSP的递归程序TryTry(s){for(i=2;i<=n;i++)ifRecord(s,i)；if(s==n-1)ifelseTry(s+1);Move-off(s,i)}return}(C>NC+C[N[n]][1])TakeNewPath();(C–NC>C[N[s]][i]

&&T[i]){耗散值更小，则更好。2/7/202358计算机算法设计与分析Try中的子程序Record(s,i);{NC=NC+C[N[s]][i];T[i]=0;N[s+1]=i;}Move-off(s,i);{NC=NC–C[N[s]][i];T[i]=1;N[s+1]=0;}TakeNewPath(){for(i=1;i<=n;i++)P[i]=N[i];C=NC+C[N[n]][1];}2/7/202359计算机算法设计与分析递归回溯求TSP的主程序TSP(n,C[n][n]){for(i=1;i<=n;i++){N[i]=0;P[i]=0;T[i]=1}NC=0；C=∞;N[1]=1;T[1]=0;Try(1);Output(P)；}2/7/202360计算机算法设计与分析考虑TSP的迭代程序为了便于迭代程序中回溯的判断，我们将城市结点编号为1~n，用编号0作为末尾的标记。先回顾一下采用末尾标记的迭代回溯法：2/7/202361计算机算法设计与分析考虑TSP的迭代程序Backtrack(TreeT){unfinish=true;L.Push(T.root);while(unfinish||L≠){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal){unfinish=false;Output();}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}要比较所有路径，无需此句。2/7/202362计算机算法设计与分析考虑TSP的迭代程序Backtrack(TreeT){L.Push(T.root);while(L≠){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal)Output();elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}初始化后压入第一个结点。2/7/202363计算机算法设计与分析考虑TSP的迭代程序Backtrack(TreeT){

j=1;N[j]=1;L.Push-Sons(1);

while(L≠){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal)Output();elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}j为栈指针。2/7/202364计算机算法设计与分析考虑TSP的迭代程序Backtrack(TreeT){

j=1;N[j]=1;L.Push-Sons(1);while(L.size()>0){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal)Output();elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}若栈不空。2/7/202365计算机算法设计与分析考虑TSP的迭代程序Backtrack(TreeT){

j=1;N[j]=1;L.Push-Sons(1);while(j>0){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal)Output();elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}末尾标记为0。2/7/202366计算机算法设计与分析考虑TSP的迭代程序Backtrack(TreeT){

j=1;N[j]=1;L.Push-Sons(1);while(j>0){a=L.Pop();if(a==0)Backastep();elseif(aisgood){Record(a);if(aisgoal)Output();elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}末尾标记为0。2/7/202367计算机算法设计与分析考虑TSP的迭代程序Backtrack(TreeT){

j=1;N[j]=1;L.Push-Sons(1);while(j>0){a=L.Pop();if(a==0){Move-off(j–1,N[j]);j––;}elseif(aisgood){Record(a);if(aisgoal)Output();elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}回溯：删除第j个结点，然后j––。2/7/202368计算机算法设计与分析考虑TSP的迭代程序Backtrack(TreeT){

j=1;N[j]=1;L.Push-Sons(1);while(j>0){a=L.Pop();if(a==0){Move-off(j–1,N[j]);j––;}elseif(aisgood){Record(a);if(aisgoal)Output();elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}a不在路线中且新增后的费用仍低。2/7/202369计算机算法设计与分析考虑TSP的迭代程序Backtrack(TreeT){

j=1;N[j]=1;L.Push-Sons(1);while(j>0){a=L.Pop();if(a==0){Move-off(j–1,N[j]);j––;}elseif(T[a]&&C–NC>C[N[j]][a]){Record(j,a);if(aisgoal)Output();elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}已经n个结点且新路线的费用更低。这个判断不再需要了。2/7/202370计算机算法设计与分析考虑TSP的迭代程序Backtrack(TreeT){

j=1;N[j]=1;L.Push-Sons(1);while(j>0){a=L.Pop();if(a==0){Move-off(j–1,N[j]);j––;}elseif(T[a]&&C–NC>C[N[i]][a]){Record(j,a);if(aisgoal)Output();elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}已经n个结点且新路线的费用更低。2/7/202371计算机算法设计与分析考虑TSP的迭代程序Backtrack(TreeT){

j=1;N[j]=1;L.Push-Sons(1);while(j>0){a=L.Pop();if(a==0){Move-off(j–1,N[j]);j––;}elseif(T[a]&&C–NC>C[N[i]][a]){Record(N[j],a);if(j==n

-1){if(C>NC+C[a][1])

{TakeNewPath();}Move-off(j,a);}

else

{j++;L.Push-Sons(a)}}}

2/7/202372计算机算法设计与分析考虑TSP的迭代程序Backtrack(TreeT){j=1;N[j]=1;L.Push-Sons(1);while(j>0){a=L.Pop();if(a==0){Move-off(N[j–1],N[j]);j––;}elseif(T[a]&&C–NC>C[N[i]][a]){Record(N[j],a);if(s==n){if(C>NC+C[a][1])

{TakeNewPath();Move-off(N[j],a);}}else{j++;L.Push-Sons(a)}}}

这就是TSP的迭代程序。2/7/202373计算机算法设计与分析迭代回溯求TSP的主程序TSP(n,C[n][n]){for(i=1;i<=n;i++){N[i]=0;P[i]=0;T[i]=1}NC=0；C=∞;N[1]=1;T[1]=0;Backtrack(n,C);Output(P)；}2/7/202374计算机算法设计与分析求解TSP的时间复杂性显然TSP是一个求排列的问题。求排列：确定n个元素的满足某种性质的排列。其搜索树称为排列树，通常有n!个叶结点，因此遍历排列树需要时间为O(n!)。所以TSP问题的时间复杂性为O(n!)2/7/202375计算机算法设计与分析用回溯法解0-1背包问题类似于TSP，用一个数组P[n]存放目前取得的最优解，用变量V表示其价值；再用一个数组N[n]来产生新的解，用变量NV表示其价值，用变量W表示当前重量。如果新解更优，则替代原来的最优解，否则就丢弃新解。然后回溯寻找下一个新解。为此，我们先回顾一下回溯法的一般递归算法：2/7/202376计算机算法设计与分析用回溯法解0-1背包问题Try(s){做挑选候选者的准备；while(未成功且还有候选者){挑选下一个候选者next；if(next可接受){记录next；if(满足成功条件){成功并输出结果}elseTry(s+1);if(不成功)删去next的记录;}}return成功与否}考察的第s个物品2/7/202377计算机算法设计与分析用回溯法解0-1背包问题Try(s){做挑选候选者的准备；while(未成功且还有候选者){挑选下一个候选者next；if(next可接受){记录next；if(满足成功条件){成功并输出结果}elseTry(s+1);if(不成功)删去next的记录;}}return成功与否}只考虑两种情况，选或不选，即for(i=0;i<2;i++)下个候选是i。2/7/202378计算机算法设计与分析用回溯法解0-1背包问题Try(s){

for(i=0;i<2;i++){

if(next可接受){记录next；if(满足成功条件){成功并输出结果}elseTry(s+1);if(不成功)删去next的记录;}}return成功与否}令Accept(s)判断s可接受令Record(s)记录s2/7/202379计算机算法设计与分析用回溯法解0-1背包问题Try(s){

for(i=0;i<2;i++){if(Accept(s){Record(s,i)if(next可接受){记录next；if(满足成功条件){成功并输出结果}elseTry(s+1);if(不成功)删去next的记录;}}return成功与否}物体s可放入背包中将物体s放入背包中2/7/202380计算机算法设计与分析用回溯法解0-1背包问题Try(s){

for(i=0;i<2;i++){if(Accept(s){Record(s,i)

if(满足成功条件){成功并输出结果}elseTry(s+1);if(不成功)删去next的记录;}}return成功与否}增加物体s未超过背包容量。if(W+w[s]*i<=C){2/7/202381计算机算法设计与分析用回溯法解0-1背包问题Try(s){

for(i=0;i<2;i++){

if(W+w[s]*i<=C){Record(s,i)

if(满足成功条件){成功并输出结果}elseTry(s+1);if(不成功)删去next的记录;}}return成功与否}将物体s放入背包中即将s放入背包中并修改权重与容量。N[s]=i;W=W+w[s]*i;NV=NV+v[s]*i;}2/7/202382计算机算法设计与分析用回溯法解0-1背包问题Try(s){

for(i=0;i<2;i++){

if(W+w[s]*i<=C){

N[s]=i;W=W+w[s]*i;NV=NV+v[s]*i;}

if(满足成功条件){成功并输出结果}elseTry(s+1);if(不成功)删去next的记录;}}return成功与否}将物体s放入背包中即将s放入背包中并修改权重与容量。2/7/202383计算机算法设计与分析用回溯法解0-1背包问题Try(s){

for(i=0;i<2;i++){

if(W+w[s]*i<=C){

N[s]=i;W=W+w[s]*i;NV=NV+v[s]*i;}

if(满足成功条件){成功并输出结果}elseTry(s+1);if(不成功)删去next的记录;}}return成功与否}s==n2/7/202384计算机算法设计与分析用回溯法解0-1背包问题Try(s){做挑选候选者的准备；while(未成功且还有候选者){挑选下一个候选者next；if(next可接受){记录next；if(满足成功条件){成功并输出结果}elseTry(s+1);if(不成功)删去next的记录;}}return成功与否}for(i=0;i<2;i++){(Accept(s){Record(s,i)(s==n)s=

=n{if(better)TakeNewChoice();}2/7/202385计算机算法设计与分析用回溯法解0-1背包问题Try(s){做挑选候选者的准备；while(未成功且还有候选者){挑选下一个候选者next；if(next可接受){记录next；if(满足成功条件){成功并输出结果}elseTry(s+1);if(不成功)删去next的记录;}}return成功与否}for(i=0;i<2;i++){(Accept(s){Record(s,i)(s==n){if(better)TakeNewChoice();}这里无论成功与否都要继续考察Move-off(s,i);}return}“记录”的逆操作2/7/202386计算机算法设计与分析用回溯法解0-1背包问题Try(s){for(i=0;i<2;i++)if(Accept(i)){Record(s,i)；