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

1、2020/10/9,计算机算法设计与分析,1,第五章回溯法,2020/10/9,计算机算法设计与分析,2,计算机求解的过程,求解过程可看成在状态空间从初始状态出发搜索目标状态(解所在状态)的过程。,状态空间,初始状态,目标状态,搜索,可描述为：S0S1Sn，S0为初态，Sn为终态。或者(S0)且(Sn)，这里称为初始条件，称为终止条件。,2020/10/9,计算机算法设计与分析,3,求解是状态空间的搜索,求解的过程可以描述为对状态空间的搜索,其中S0为初始状态，不妨设Sni为 终止状态,于是问题的求解就是通过搜索寻找出一条从初始状态S0到终止状态Sni的路径。,Sni,2020/10/9,计算

2、机算法设计与分析,4,几种搜索方法,状态空间的搜索实际上是一种树/DAG的搜索，常用的方法有：,广度优先的搜索： 深度优先的搜索： 启发式的搜索：,从初始状态开始，逐层地进行搜索。,从初始状态开始，逐个分枝地进行搜索。,从初始状态开始，每次选 择最有可能达到终止状态的结点进行搜索。,2020/10/9,计算机算法设计与分析,5,三种搜索的比较,理论上广度优先搜索与深度优先搜索的时间复杂性都是指数级。但在实际上深度优先搜索的时间复杂性要低，在空间复杂性更要低得多。 广度优先搜索是一定能找到解；而深度优先搜索在理论上存在找不到解的可能。 启发式搜索是最好优先的搜索，若评价函数设计得好则能较快地找到

3、解，降低时间复杂性；因而评价函数的优劣决定了启发式搜索的优劣。另外评价函数本身的开销也是很重要的。,2020/10/9,计算机算法设计与分析,6,树搜索的一般形式,SearchTree(Space T) ok = 0; L = T.initial; while (!ok | L) a = L.first; if (a is goal) ok = 1 else Control-put-in(L, Sons(a); ,ok表示搜索结束。,将初始状态放入L 。,从L中取出第一个元素。,若a是终态则结束。,否则，将a的儿子们以某种控制方式放入L中。,表L用来存放待考察的结点。,2020/10/9,计算

4、机算法设计与分析,7,三种搜索的不同之处,树的三种搜索方法的不同就在于它们对表L使用了不同控制方式：,L是一个队列 L是一个栈 L的元素按照某方式排序,广度优先搜索 深度优先搜索 启发式搜索,其中，深度优先搜索就是回溯法。,2020/10/9,计算机算法设计与分析,8,递归回溯法的一般形式,Try(s) 做挑选候选者的准备； while (未成功且还有候选者) 挑选下一个候选者next； if (next可接受) 记录next； if (满足成功条件) 成功并输出结果 else Try(s+1); if (不成功) 删去next的记录; return 成功与否,Try(s+1)意味着按照这条分

5、支继续尝试。,Try(s+1)返回后，若不成功，则意味着这条分支失败了。这时必须删除原来记录。,2020/10/9,计算机算法设计与分析,9,迭代回溯法的一般形式,先让我们回顾解空间搜索的一般形式：,SearchTree(Space T)/ Ok = 0; L = T.initial; while (!Ok | L) a = L.first; /从L中取出第一个元素 if (a is goal) Ok = 1 else Control-put-in(L, Sons(a); ,Ok表示是否找到解。,表L存放待考察结点。对L的控制方式不同，则搜索方法也不同。 在回溯法中，控制方式是栈。初始将根节点

6、放入L中。,2020/10/9,计算机算法设计与分析,10,迭代回溯法的一般形式,先让我们回顾解空间搜索的一般形式：,SearchTree(Space T)/ Ok = 0; L = T.initial; while (!Ok | L) a = L.first; if (a is goal) Ok = 1 else Control-put-in(L, Sons(a); ,从L中取出第一个元素。在栈操作中就是弹出栈顶元素。,在通常求解问题时，解是由逐个状态构成的。因此，这里还需要判断状态是否可接受，并进行纪录路径等工作。,2020/10/9,计算机算法设计与分析,11,迭代回溯法的一般形式,先让

7、我们回顾解空间搜索的一般形式：,SearchTree(Space T)/ Ok = 0; L = T.initial; while (!Ok | L) a = L.first; if (a is goal) Ok = 1 else Control-put-in(L, Sons(a); ,若a可接收但未终止，则要将a的后继压入栈中。若要抛弃状态a，当a是最后的儿子时，还需要消除原有的纪录甚至回溯一步。,2020/10/9,计算机算法设计与分析,12,如何判断最后一个儿子？,若只要遍历解空间树的结点，那么将各结点按栈方式控制便可实现深度为主搜索。 在求解问题时，需要记录解的路径，在回溯时还需要删除

8、结点和修改相应信息。 栈中结点应该分层次，而却没有区分其层次。这就增加了回溯判断和操作的困难。,怎么办呢？,2020/10/9,计算机算法设计与分析,13,如何判断最后一个儿子？,若只要遍历解空间树的结点，那么将各结点按栈方式控制便可实现深度为主搜索。 在求解问题时，需要记录解的路径，在回溯时还需要删除结点和修改相应信息。 栈中结点应该分层次，而却没有区分其层次。这就增加了回溯判断和操作的困难。,采用一个简洁有效的方法：设计一个末尾标记，每次压栈时，先压入末尾标记。,2020/10/9,计算机算法设计与分析,14,用末尾标记的迭代回溯,Backtrack(Tree T) Ok = 0; L.P

9、ush(T.root); while (!Ok| L) a = L.Pop( ); if (a is the last mark) Backastep( ); else if (a is good) Record(a); if (a is goal) Ok = 1; Output( ) else if (a has sons) L.Push-Sons(a) else Move-off(a);,末尾,2020/10/9,计算机算法设计与分析,15,用末尾标记的迭代回溯,Backtrack(Tree T) Ok = 0; L.Push(T.root); while (!Ok| L) a = L.P

10、op( ); if (a is the last mark) Backastep( ); else if (a is good) Record(a); if (a is goal) Ok = 1; Output( ) else if (a has sons) L.Push-Sons(a) else Move-off(a);,2020/10/9,计算机算法设计与分析,16,用末尾标记的迭代回溯,Backtrack(Tree T) Ok = 0; L.Push(T.root); while (!Ok| L) a = L.Pop( ); if (a is the last mark) Backast

11、ep( ); else if (a is good) Record(a); if (a is goal) Ok = 1; Output( ) else if (a has sons) L.Push-Sons(a) else Move-off(a);,2020/10/9,计算机算法设计与分析,17,用末尾标记的迭代回溯,Backtrack(Tree T) Ok = 0; L.Push(T.root); while (!Ok| L) a = L.Pop( ); if (a is the last mark) Backastep( ); else if (a is good) Record(a);

12、if (a is goal) Ok = 1; Output( ) else if (a has sons) L.Push-Sons(a) else Move-off(a);,2020/10/9,计算机算法设计与分析,18,用末尾标记的迭代回溯,Backtrack(Tree T) Ok = 0; L.Push(T.root); while (!Ok| L) a = L.Pop( ); if (a is the last mark) Backastep( ); else if (a is good) Record(a); if (a is goal) Ok = 1; Output( ) else

13、if (a has sons) L.Push-Sons(a) else Move-off(a);,2020/10/9,计算机算法设计与分析,19,用末尾标记的迭代回溯,Backtrack(Tree T) Ok = 0; L.Push(T.root); while (!Ok| L) a = L.Pop( ); if (a is the last mark) Backastep( ); else if (a is good) Record(a); if (a is goal) Ok = 1; Output( ) else if (a has sons) L.Push-Sons(a) else Mo

14、ve-off(a);,2020/10/9,计算机算法设计与分析,20,用末尾标记的迭代回溯,Backtrack(Tree T) Ok = 0; L.Push(T.root); while (!Ok| L) a = L.Pop( ); if (a is the last mark) Backastep( ); else if (a is good) Record(a); if (a is goal) Ok = 1; Output( ) else if (a has sons) L.Push-Sons(a) else Move-off(a);,2020/10/9,计算机算法设计与分析,21,Bac

15、kastep与Move-off,Backstep的动作：,末尾,Move-off的动作：,非末尾,Move-off需要做的只是删除自身的记录而转向兄弟结点。而Backstep除此之外，还需要删除父节点的记录而转向叔叔结点。,2020/10/9,计算机算法设计与分析,22,迭代回溯法的一般形式,Backtrack(Tree T) Ok = 0; L.Push(T.root); while (!Ok| L) a = L.Pop( ); if (a is the last mark) Backastep( ); else if (a is good) Record(a); if (a is goal

16、) Ok = 1; Output( ) else if (a has sons) L.Push-Sons(a) else Move-off(a);,2020/10/9,计算机算法设计与分析,23,不可接受的结点,破坏了解的相容条件的结点 超出了状态空间的范围，或者说不满足约束条件，的结点； 评价值很差的结点，即已经知道不可能获得解的结点； 已经存在于被考察的路径之中的结点，这种结点会造成搜索的死循环。,2020/10/9,计算机算法设计与分析,24,N后问题,要求在一个nn的棋盘上放置n个皇后，使得她们彼此不受攻击。 按照国际象棋的规则，一个皇后可以攻击与之同一行或同一列或同一斜线上的任何棋子

17、。 因此，N后问题等价于：要求在一个nn的棋盘上放置n个皇后，使得任意两个皇后不得在同一行或同一列或同一斜线上。,2020/10/9,计算机算法设计与分析,25,用递归回溯法求N后问题,Try(s) 做挑选候选者的准备； while (未成功且还有候选者) 挑选下一个候选者next； if (next可接受) 记录next； if (满足成功条件) 成功并输出结果 else Try(s+1); if (不成功) 删去next的记录; return 成功与否,让我们先回顾递归回溯法的一般形式：,2020/10/9,计算机算法设计与分析,26,用递归回溯法求N后问题,Try(s) 做挑选候选者的准

18、备； while (未成功且还有候选者) 挑选下一个候选者next； if (next可接受) 记录next； if (满足成功条件) 成功并输出结果 else Try(s+1); if (不成功) 删去next的记录; return 成功与否,s为准备放置后的行数。,候选者为0到n 1列。,2020/10/9,计算机算法设计与分析,27,用递归回溯法求N后问题,Try(s) while if (next可接受) 记录next； if (满足成功条件) 成功并输出结果 else Try(s+1); if (不成功) 删去next的记录; return 成功与否,j = 1; q = 0;,令列

19、标志j为1 ，q表示未成功。,(未成功且还有候选者) ,(!q ,2020/10/9,计算机算法设计与分析,28,用递归回溯法求N后问题,Try(s) while if 记录next； if (满足成功条件) 成功并输出结果 else Try(s+1); if (不成功) 删去next的记录; return 成功与否,j = 1; q = 0;,(!q ,(next可接受) ,放置后各后都安全，便可接受。,用函数Safe(s, j)进行位置(s, j)是否安全的判断。,(Safe(s, j) ,2020/10/9,计算机算法设计与分析,29,用递归回溯法求N后问题,Try(s) while i

20、f if (满足成功条件) 成功并输出结果 else Try(s+1); if (不成功) 删去next的记录; return 成功与否,j = 1; q = 0;,(!q ,记下该行后的位置(列数) 。,用函数Record(s, j)记下位置(s, j) 。,(Safe(s, j) ,记录next；,Record(s, j);,2020/10/9,计算机算法设计与分析,30,用递归回溯法求N后问题,Try(s) while if if else Try(s+1); if (不成功) 删去next的记录; return 成功与否,j = 1; q = 0;,(!q ,n行后都放完就成功了。,q

21、赋值为1，表示已经完成，退出循环 。,(Safe(s, j) ,Record(s, j);,(满足成功条件) 成功并输出结果,(s = = n 1) q = 1; Output( );,2020/10/9,计算机算法设计与分析,31,用递归回溯法求N后问题,Try(s) while if if else Try(s+1); if return,j = 1; q = 0;,(!q ,(Safe(s, j) ,Record(s, j);,(s = = n 1) q = 1; Output( );,未完成，放s+1行 。,(不成功) 删去next的记录; ,不成功，删去后在该行的位置。,(!q) M

22、ove-off(s, j); ,成功与否,q ,2020/10/9,计算机算法设计与分析,32,用递归回溯法求N后问题,Try(s) while if if else Try(s+1); if return,j = 1; q = 0;,(!q ,(Safe(s, j) ,Record(s, j);,(s = = n 1) q = 1; Output( );,q ,(!q) Move-off(s, j); ,现在便得到了求N后的回溯程序。,2020/10/9,计算机算法设计与分析,33,求解N后问题中的数据表示,数组Bn表示棋盘。若Bi = j，0i, jn，表示棋盘的第i行第j列上有皇后。 数

23、组Cj = 1表示第j列上无皇后，0jn。,数组Dk=1表示第k条下行对角线()上无皇后。这里k=i + j，0k2(n 1)。,2020/10/9,计算机算法设计与分析,34,求解N后问题中的数据表示,数组Bn表示棋盘。若Bi = j，0i, jn，表示棋盘的第i行第j列上有皇后。 数组Cj = 1表示第j列上无皇后，0jn。,数组Dk = 1表示第k条下行对角线()上无皇后。这里k=i + j，0k2(n 1)。,数组Uk = 1表示第k条上行对角线()上无皇后。这里k=i j，n+1kn1。,2020/10/9,计算机算法设计与分析,35,求解N后问题中的子程序,Record(s, j)

24、 k = s j + n 1; Bs = j; Cj = 0; Ds+j = 0; Uk = 0; ,Move-off(s, j) k = s j + n 1; Bs = -1; Cj = 1; Ds+j = 1; Uk = 1; ,Safe(s, j) k = s j + n 1; if (Cj=1 ,此处k是上行对角线的下标，为什么要进行这样一个计算呢？,2020/10/9,计算机算法设计与分析,36,求解N后问题的主程序,N-Queens( ) int Bn, Cn, D2n 1, U2n 1; for (j = 0, j n; j+) Bj = -1; Cj = 1; U2j = 1;

25、 U2j + 1 = 1; D2j = 1; D2j + 1 = 1; try(0); Output(B); ,从第一行开始递归,2020/10/9,计算机算法设计与分析,37,N后问题的迭代程序,先看看迭代回溯法的一般形式：,2020/10/9,计算机算法设计与分析,38,N后问题的迭代程序,Backtrack(Tree T) Ok = 0; while (!Ok| L) a = L.Pop( ); if else if (a is good) Record(a); if (a is goal) Ok = 1; Output( ); else if (a has sons) L.Push-S

26、ons(a) else Move-off(a);,L.Push(T.root);,(a is the last mark) Backastep( );,迭代从第一行(行号为0）开始，将第一行的0n1 列和n压入栈中，这里n作为末尾标记。,2020/10/9,计算机算法设计与分析,39,N后问题的迭代程序,Backtrack(Tree T) Ok = 0; while (!Ok| L) a = L.Pop( ); if else if (a is good) Record(a); if (a is goal) Ok = 1; Output( ); else if (a has sons) L.P

27、ush-Sons(a) else Move-off(a);,L.Push(T.root);,(a is the last mark) Backastep( );,i = 0; L.Push(n, 0, 1, 2, );,栈指针p0，即栈为空。,a是末尾标记则回溯。,p = 0),2020/10/9,计算机算法设计与分析,40,N后问题的迭代程序,Backtrack(Tree T) Ok = 0; while (!Ok| p = 0) a = L.Pop( ); if else if (a is good) Record(a); if (a is goal) Ok = 1; Output( );

28、 else if (a has sons) L.Push-Sons(a) else Move-off(a);,(a is the last mark) Backastep( );,i = 0; L.Push(n, 0, 1, 2, );,(a = = n) Backastep;,回溯需要退回一行，即i ;同时删除该行的原纪录。,2020/10/9,计算机算法设计与分析,41,N后问题的迭代程序,Backtrack(Tree T) Ok = 0; while (!Ok| p = 0) a = L.Pop( ); if else if (a is good) Record(a); if (a is

29、 goal) Ok = 1; Output( ); else if (a has sons) L.Push-Sons(a) else Move-off(a);,i = 0; L.Push(n, 0, 1, 2, );,(a = = 0) Backastep;,(a = n) i ; a = Bi; Move-off(i, a); ,若置放后的位置是安全的，则是好的位置。现设有谓词safe(i, a)表示第i行第a列是安全的位置。,2020/10/9,计算机算法设计与分析,42,N后问题的迭代程序,Backtrack(Tree T) Ok = 0; while (!Ok| p = 0) a =

30、L.Pop( ); if else if if (a is goal) Ok = 1; Output( ); else if (a has sons) L.Push-Sons(a) else Move-off(a);,i = 0; L.Push(n, 0, 1, 2, );,(a = n) i ; a = Bi; Move-off(i, a); ,(Safe(i, a) Record(i, a);,如果safe(i, a)，则放下后，即Record(a)。,2020/10/9,计算机算法设计与分析,43,N后问题的迭代程序,Backtrack(Tree T) Ok = 0; while (!O

31、k| p = 0) a = L.Pop( ); if else if if (a is goal) Ok = 1; Output( ); else if (a has sons) L.Push-Sons(a) else Move-off(a);,i = 0; L.Push(n, 0, 1, 2, );,(a = n) i ; a = Bi; Move-off(i, a); ,(Safe(i, a) Record(i, a);,如果到了第n行，则成功。,(i = = n 1),2020/10/9,计算机算法设计与分析,44,N后问题的迭代程序,Backtrack(Tree T) Ok = 0;

32、while (!Ok| p = 0) a = L.Pop( ); if else if if (a is goal) Ok = 1; Output( ); else if (a has sons) L.Push-Sons(a) else Move-off(a);,i = 0; L.Push(n, 0, 1, 2, );,(a = n) i ; a = Bi; Move-off(i, a); ,(Safe(i, a) Record(i, a);,(i = = n 1),i+; L.Push(n, 0, 1, 2, );,只要没到第n行，则总是有后继的。,2020/10/9,计算机算法设计与分析,

33、45,N后问题的迭代程序,Backtrack(Tree T) Ok = 0; while (!Ok| p = 0) a = L.Pop( ); if else if if (a is goal) Ok = 1; Output( ); else if (a has sons) L.Push-Sons(a) else Move-off(a);,i = 0; L.Push(n, 0, 1, 2, );,(a = n) i ; a = Bi; Move-off(i, a); ,(Safe(i, a) Record(i, a);,i+; L.Push(n, 0, 1, 2, );,于是就得到了N后问题的

34、迭代程序。,注：这里的几个子程序与递归程序中的完全相同。,(i = = n 1),请同学们自己考虑栈的操作。,2020/10/9,计算机算法设计与分析,46,迭代回溯解N后问题的主程序,N-Queens(n) int Bn, Cn, D2n 1, U2n 1; Tn2; for (j = 0, j n; j+) Bj = -1; Cj = 1; U2j = 1; U2j + 1 = 1; D2j = 1; D2j + 1 = 1; int p = 1; /栈初始化为空/ Backtrack(n, B);,T为栈，最多能有n2个候选者。,2020/10/9,计算机算法设计与分析,47,N后问题的

35、时间复杂性,如果只要找出N后问题的一个解，那么这是一个求路径的问题。 求路径：只需要找到一条路径便可以得到解。设每个状态有k个后继，其搜索树为K叉树，其结点总数为kn+11，遍历的时间为O(kn)，这里n为找到解的路径长度。 N后问题的路径深度为n，可选择的后继有n个，所以时间复杂性为O(nn)。,2020/10/9,计算机算法设计与分析,48,旅行售货员问题,TSP：某售货员到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条路线，经过每个城市一遍最后回到驻地的路线，使得总的路程(或总旅费)最小。 设G=(V, E)是一个带权图。图中各边的费用(权值)为正。图中一条周游路线是包

36、括V中所有顶点的回路。一条周游路线的费用是该路线上所有边的费用之和。所谓旅行售货员问题就是要在图G中找出一条最小费用的周游路线。,2020/10/9,计算机算法设计与分析,49,考虑TSP的递归回溯算法,Try(s) 做挑选候选者的准备； while (未成功且还有候选者) 挑选下一个候选者next； if (next可接受) 记录next； if (满足成功条件) 成功并输出结果 else Try(s+1); if (不成功) 删去next的记录; return 成功与否,线路上第s个结点,只需依次考察n1个结点，即 for (i=2; i=n; i+) 下一个候选就是i。,2020/10/

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

38、 = 2; i = n; i+),if (Accept(i) Record(s, i)；,s = = n-1,若新线路更好，就用新线路取代老线路。,2020/10/9,计算机算法设计与分析,52,考虑TSP的递归回溯算法,Try(s) else Try(s+1); if (不成功) 删去next的记录; return 成功与否,for (i = 2; i = n; i+),if (Accept(i) Record(s, i)；,if (s = = n-1),if (better) TakeNewPath( ) ;,无所谓成功与否，因为每条周游路线都要进行比较。,2020/10/9,计算机算法设

39、计与分析,53,考虑TSP的递归回溯算法,Try(s) else Try(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( ) ;,2020/10/9,计算机算法设计与分析,54,TSP的递归回溯算法,Try(s) for (i = 2; i = n; i+) if (Accept(i) Record(s, i)； if (s = = n-1) if (better) TakeNewPath( ) ; el

40、se Try(s+1); Move-off(s, i) return ,现在便得到了TSP问题的递归回溯算法的程序。,2020/10/9,计算机算法设计与分析,55,求解TSP的数据结构,数组Cnn存放个城市间的费用值。 数组Pn记录已经找到的费用最小的周游路线，C为其相应的费用， C初值为。 数组Nn记录目前正在寻找的周游路线，NC为其相应的费用； 若NC+CNn1小于C，则路线N更佳，于是P = N，C = NC+CNn1。 若结点next不是N中已有结点，且C大于 NC+CNinext，则结点next可接受。,2020/10/9,计算机算法设计与分析,56,TSP的递归程序Try,Try

41、(s) for (i = 2; i = n; i+) if (Accept(i) Record(s, i)； if (s = = n-1) if (better) TakeNewPath( ) ; else Try(s+1); Move-off(s, i) return ,2020/10/9,计算机算法设计与分析,57,TSP的递归程序Try,Try(s) for (i = 2; i = n; i+) if Record(s, i)； if (s = = n-1) if (better) TakeNewPath( ) ; else Try(s+1); Move-off(s, i) return

42、 ,(CNC CNsi i = n; i+) if Record(s, i)； if (s = = n-1) if else Try(s+1); Move-off(s, i) return ,(C NC+CNn1) TakeNewPath( );,(CNC CNsi NC = NC + CNsi; Ti = 0; Ns+1 = i; ,Move-off(s, i); NC = NC CNsi; Ti = 1; Ns+1 = 0;,TakeNewPath( ) for (i=1; i=n; i+) Pi = Ni; C = NC + CNn1;,2020/10/9,计算机算法设计与分析,60,递

43、归回溯求TSP的主程序,TSP(n, Cnn) for (i = 1; i = n; i+) Ni=0; Pi = 0; Ti = 1 NC = 0；C = ; N1=1; T1 = 0; Try(1); Output(P)； ,2020/10/9,计算机算法设计与分析,61,考虑TSP的迭代程序,为了便于迭代程序中回溯的判断，我们将城市结点编号为1 n，用编号0作为末尾的标记。 先回顾一下采用末尾标记的迭代回溯法：,2020/10/9,计算机算法设计与分析,62,考虑TSP的迭代程序,Backtrack(Tree T) unfinish = true; L.Push(T.root); whi

44、le (unfinish | L) a = L.Pop( ); if (a is the last mark) Backastep( ); else if (a is good) Record(a); if (a is goal) unfinish = false; Output( ); else if (a has sons) L.Push-Sons(a) else Move-off(a);,要比较所有路径，无需此句。,2020/10/9,计算机算法设计与分析,63,考虑TSP的迭代程序,Backtrack(Tree T) L.Push(T.root); while (L) a = L.Po

45、p( ); if (a is the last mark) Backastep( ); else if (a is good) Record(a); if (a is goal) Output( ); else if (a has sons) L.Push-Sons(a) else Move-off(a);,初始化后压入第一个结点。,2020/10/9,计算机算法设计与分析,64,考虑TSP的迭代程序,Backtrack(Tree T) j = 1; Nj = 1; L.Push-Sons(1); while (L) a = L.Pop( ); if (a is the last mark)

46、Backastep( ); else if (a is good) Record(a); if (a is goal) Output( ); else if (a has sons) L.Push-Sons(a) else Move-off(a);,j为栈指针。,2020/10/9,计算机算法设计与分析,65,考虑TSP的迭代程序,Backtrack(Tree T) j = 1; Nj = 1; L.Push-Sons(1); while (L.size() 0) a = L.Pop( ); if (a is the last mark) Backastep( ); else if (a is

47、 good) Record(a); if (a is goal) Output( ); else if (a has sons) L.Push-Sons(a) else Move-off(a);,若栈不空。,2020/10/9,计算机算法设计与分析,66,考虑TSP的迭代程序,Backtrack(Tree T) j = 1; Nj = 1; L.Push-Sons(1); while (j 0) a = L.Pop( ); if (a is the last mark) Backastep( ); else if (a is good) Record(a); if (a is goal) Ou

48、tput( ); else if (a has sons) L.Push-Sons(a) else Move-off(a);,末尾标记为0。,2020/10/9,计算机算法设计与分析,67,考虑TSP的迭代程序,Backtrack(Tree T) j = 1; Nj = 1; L.Push-Sons(1); while (j 0) a = L.Pop( ); if (a = 0) Backastep( ); else if (a is good) Record(a); if (a is goal) Output( ); else if (a has sons) L.Push-Sons(a) e

49、lse Move-off(a);,末尾标记为0。,2020/10/9,计算机算法设计与分析,68,考虑TSP的迭代程序,Backtrack(Tree T) j = 1; Nj = 1; L.Push-Sons(1); while (j 0) a = L.Pop( ); if (a = 0) Move-off(j1, Nj); j ; else if (a is good) Record(a); if (a is goal) Output( ); else if (a has sons) L.Push-Sons(a) else Move-off(a);,回溯：删除第j个结点，然后j 。,2020

50、/10/9,计算机算法设计与分析,69,考虑TSP的迭代程序,Backtrack(Tree T) j = 1; Nj = 1; L.Push-Sons(1); while (j 0) a = L.Pop( ); if (a = 0) Move-off(j1, Nj); j ; else if (a is good) Record(a); if (a is goal) Output( ); else if (a has sons) L.Push-Sons(a) else Move-off(a);,a不在路线中且新增后的费用仍低。,2020/10/9,计算机算法设计与分析,70,考虑TSP的迭代程

51、序,Backtrack(Tree T) j = 1; Nj = 1; L.Push-Sons(1); while (j 0) a = L.Pop( ); if (a = 0) Move-off(j1, Nj); j ; else if (Ta,已经n个结点且新路线的费用更低。,这个判断不再需要了。,2020/10/9,计算机算法设计与分析,71,考虑TSP的迭代程序,Backtrack(Tree T) j = 1; Nj = 1; L.Push-Sons(1); while (j 0) a = L.Pop( ); if (a = 0) Move-off(j1, Nj); j ; else if

52、 (Ta,已经n个结点且新路线的费用更低。,2020/10/9,计算机算法设计与分析,72,考虑TSP的迭代程序,Backtrack(Tree T) j = 1; Nj = 1; L.Push-Sons(1); while (j 0) a = L.Pop( ); if (a = 0) Move-off(j1, Nj); j ; else if (Ta L.Push-Sons(a),2020/10/9,计算机算法设计与分析,73,考虑TSP的迭代程序,Backtrack(Tree T) j = 1; Nj = 1; L.Push-Sons(1); while (j 0) a = L.Pop( )

53、; if (a = 0) Move-off(Nj1, Nj); j ; else if (Ta L.Push-Sons(a),这就是TSP的迭代程序。,2020/10/9,计算机算法设计与分析,74,迭代回溯求TSP的主程序,TSP(n, Cnn) for (i = 1; i = n; i+) Ni=0; Pi = 0; Ti = 1 NC = 0；C = ; N1=1; T1 = 0; Backtrack(n, C); Output(P)； ,2020/10/9,计算机算法设计与分析,75,求解TSP的时间复杂性,显然TSP是一个求排列的问题。 求排列：确定n个元素的满足某种性质的排列。其搜

54、索树称为排列树，通常有n!个叶结点，因此遍历排列树需要时间为O(n!)。 所以TSP问题的时间复杂性为O(n!),2020/10/9,计算机算法设计与分析,76,用回溯法解0-1背包问题,类似于TSP，用一个数组Pn存放目前取得的最优解，用变量V表示其价值；再用一个数组Nn来产生新的解，用变量NV表示其价值，用变量W表示当前重量。如果新解更优，则替代原来的最优解，否则就丢弃新解。然后回溯寻找下一个新解。 为此，我们先回顾一下回溯法的一般递归算法：,2020/10/9,计算机算法设计与分析,77,用回溯法解0-1背包问题,Try(s) 做挑选候选者的准备； while (未成功且还有候选者) 挑

55、选下一个候选者next； if (next可接受) 记录next； if (满足成功条件) 成功并输出结果 else Try(s+1); if (不成功) 删去next的记录; return 成功与否,考察的第s个物品,2020/10/9,计算机算法设计与分析,78,用回溯法解0-1背包问题,Try(s) 做挑选候选者的准备； while (未成功且还有候选者) 挑选下一个候选者next； if (next可接受) 记录next； if (满足成功条件) 成功并输出结果 else Try(s+1); if (不成功) 删去next的记录; return 成功与否,只考虑两种情况，选或不选，即

56、for (i=0; i2; i+) 下个候选是i。,2020/10/9,计算机算法设计与分析,79,用回溯法解0-1背包问题,Try(s) for (i = 0; i 2; i+) if (next可接受) 记录next； if (满足成功条件) 成功并输出结果 else Try(s+1); if (不成功) 删去next的记录; return 成功与否,令Accept(s)判断s可接受,令Record(s)记录s,2020/10/9,计算机算法设计与分析,80,用回溯法解0-1背包问题,Try(s) for (i = 0; i 2; i+) if (Accept(s) Record(s,i)

57、 if (next可接受) 记录next； if (满足成功条件) 成功并输出结果 else Try(s+1); if (不成功) 删去next的记录; return 成功与否,物体s可放入背包中,将物体s放入背包中,2020/10/9,计算机算法设计与分析,81,用回溯法解0-1背包问题,Try(s) for (i = 0; i 2; i+) if (Accept(s) Record(s,i) if (满足成功条件) 成功并输出结果 else Try(s+1); if (不成功) 删去next的记录; return 成功与否,增加物体s未超过背包容量。,if (W+ws*i = C) ,2020/10/9,计算机算法设计与分析,82,用回溯法解0-1背包问题,Try(s) for (i = 0; i 2; i+) if (W+ws*i = C) Record(s,i) if (满足成功条件) 成功并输出结果 else Try(s+1); if (不成功) 删去next的记录; retu