湘潭大学算法设计与分析第五章回溯法ppt课件

1、第五章回溯法用计算机求解问题问题空间现实求解过程实践解形状空间对象的定义机器求解过程算法与程序的设计机内解计算机求解的过程n在形状空间寻觅机内解可以看成是从初始形状出发搜索目的形状(解所在的形状)的过程。形状空间初始形状目的形状搜索n搜索的过程可描画为：S0S1Sn，其中S0为初态，Sn为终态。或者说(S0)且(Sn)，这里称为初始条件，称为终止条件。求解是形状空间的搜索n求解的过程可以描画为对形状空间的搜索S0S11S12S1k Sn1SniSnm其中S0为初始形状，无妨设Sni为终止形状S0Snin于是问题的求解就是经过搜索寻觅出一条从初始形状S0到终止形状Sni的途径。几种搜索方法形状空

2、间的搜索实践上是一种树的搜索，常用的方法有：n广度优先的搜索n深度优先的搜索n启发式的搜索从初始形状开场，逐层地进展搜索。从初始形状开场，逐个分枝地进展搜索。从初始形状开场，每次选择最有能够到达终止形状的结点进展搜索。三种搜索的优劣之处n普通来说，三种搜索方法各有优劣之处：n广度优先搜索的优点是一定能找到解；缺陷是空间复杂性和时间复杂性都大。n深度优先搜索的优点是空间复杂性和时间复杂性较小；缺陷是不一定能找到解。n启发式搜索是最好优先的搜索，优点是普通来说能较快地找到解，即其时间复杂性更小；缺陷是需求设计一个评价函数，并且评价函数的优劣决议了启发式搜索的优劣。树搜索的普通方式nSearchTr

3、ee(Space T)/表L用来存放待调查的结点nunfinish = true; L = T.initial; n/ unfinish表示搜索未终了，先将初始形状放入Lnwhile (unfinish | L) n a = L.first; /从L中取出第一个元素n if (a is goal) unfinish = false /假设a是终态那么终了n else Control-put-in(L, Sons(a);n /否那么，将a的儿子们以某种控制方式放入L中三种搜索的不同之处 树的三种搜索方法的不同就在于它们对表L运用了不同控制方式：nL是一个队列nL是一个栈nL的元素按照某方式排序n

4、广度优先搜索n深度优先搜索n启发式搜索n其中，深度优先搜索就是回溯法。回溯法的方式化描画n假设可以用n元组x1,x2,xn表示一个给定的问题P的解，其中xi集合Si；n元组的子组 x1,x2,xi in，假设它满足一定的约束条件，那么称为部分解。n假设它曾经是满足约束条件的部分解，那么添加xi+1Si+1构成新的子组 x1,x2,xi ,xi+1 并检查它能否满足约束条件，假设满足那么继续添加xi+2Si+2，并以此类推。假设一切的xi+1Si+1都不满足约束条件，那么去掉xi+1，回溯到xi的位置，并去掉当前的xi，另选一个xiSi，组成新的子组 x1,x2,xi 并判别其能否满足约束条件。

5、n如此反复下去，直到得到解或者证明无解为止。 递归回溯法的普通方式nTry(s)n 做挑选候选者的预备；n while (未胜利且还有候选者) n 挑选下一个候选者next； n if (next可接受) n 记录next；n if (满足胜利条件) 胜利并输出结果n else Try(s+1);n if (不胜利) 删去next的记录; n return 胜利与否迭代回溯法的普通方式n先让我们回想解空间搜索的普通方式：nSearchTree(Space T)/表L用来存放待调查的结点nunfinish = true; L = T.initial; n/ unfinish表示搜索未终了，先将初

6、始形状放入Lnwhile (unfinish | L) n a = L.first; /从L中取出第一个元素n if (a is goal) finish = false /假设a是终态那么终了n else Control-put-in(L, Sons(a);n /否那么，将a的儿子们以某种控制方式放入L中回溯法中表L为栈，将初始形状压入栈中。弹出栈顶元素在通常求解问题时，解是由逐个形状构成的。因此，这里还需求判别形状能否可接受，并进展纪录途径等任务。假设a可接纳但未终止，那么要将a的后继压入栈中。假设要丢弃形状a，当a是最后一个儿子时，还需求消除原有纪录甚至回溯一步。如何判别最后一个儿子？n

7、假设只需遍历解空间树上的结点，那么将各个结点按栈的方式控制便可实现深度为主的搜索。n但是在求解问题时，需求记录解的途径，在回溯时还需求删除结点和修正相应的信息。n栈中的结点是分层次的，而如今没有区分它们的层次。这就添加了回溯判别和操作的困难。那么怎样办？n采用一个简约有效的方法：设计一个末采用一个简约有效的方法：设计一个末尾标志，每次压栈时，先压入末尾标志。尾标志，每次压栈时，先压入末尾标志。用末尾标志的迭代回溯nBacktrack(Tree T) n unfinish = true; L.Push(T.root); n while (unfinish | L) n a = L.Pop( );

8、 n if (a is the last mark) backastep( );n else if (a is good) record(a);n if (a is goal) unfinish = false; output( );n else if (a has sons) L.Push-Sons(a) n else move-off(a);假设栈顶元素是末尾标志，阐明这个途径曾经到头了，需求回溯一步。假设a是可以接受的，那么将a参与求解的途径中。假设a是目的节点，那么终了搜索并输出求解的途径。假设a不是目的节点且a有后即，那么将a的后继压入栈中。这里的L.Push-Sons(a)要先压入

9、末尾标志，然后再压入后继结点。假设a不是目的节点又没有后继，那么将a从解的途径中删除。不可接受的结点n破坏了解的相容条件的结点n超出了形状空间的范围，或者说不满足约束条件的结点；n评价值很差的结点，即曾经知道不能够获得解的结点；n曾经存在于被调查的途径之中的结点，这种结点会呵斥搜索的死循环。数的全陈列问题n对于指定的n个数字，输出它一切能够的陈列。n容易知道n个数字恰有n!个陈列。n它有一个隐含的约束条件：每个数字用且只能用一次。 全陈列问题的解空间树n设n=4，而需求陈列的4个数字分别为：1，2，3，4。回想我们手工对这四个数字的陈列过程：n 1 2 3 41 2 4 31 3 2 44 3

10、 2 1全陈列问题中的数据表示n数组recn+1记录当前搜索途径上的每个结点所放置的数字；n数组usedn+1记录当前搜索途径上曾经被运用过的数字；用递归回溯法求N数全陈列问题nTry(s)n 做挑选候选者的预备；n while (未胜利且还有候选者) n 挑选下一个候选者next； n if (next可接受) n 记录next；n if (满足胜利条件) 胜利并输出结果n else Try(s+1);n if (不胜利) 删去next的记录; n return 胜利与否先回想递归回溯法的普通方式： 用递归回溯法求N数全陈列问题nTry(s)n 做挑选候选者的预备；n while (未胜利且

11、还有候选者) n 挑选下一个候选者next； n if (next可接受) n 记录next；n if (满足胜利条件) 胜利并输出结果n else Try(s+1);n if (不胜利) 删去next的记录; n return 胜利与否s为预备放置数字的位数候选者为数字1到n。j = 0; q = 0; 令数字从j = 0开场；q=0表示未胜利。数字不到n就还有候选者(!q & j n ) 数字加1j+;假设数字没有运用过，便可接受(Safe(j) Record (s,j);(s = = n) q = 1; output( rec ); 不胜利，清掉该数字。(!q) Move-Off

12、(s, j); q recs=j; usedj=1;(usedj=0) (!q) recs=0; usedj=0; n个位置都放完就胜利了记下该位置的数字递归求全陈列的主程序nN-Arrange( ) nint recn + 1, usedn + 1;nfor (i = 1, i= n; i+) n reci=0;n usedi=0;ntry(1); 从第一行开场递归N数全陈列问题的迭代程序先看看迭代回溯法的普通方式：nBacktrack(Tree T) n unfinish = true; L.Push(T.root); n while (unfinish | L) n a = L.Pop(

13、 ); n if (a is the last mark) backastep( );n else if (a is good) record(a);n if (a is goal) unfinish = false; output( );n else if (a has sons) L.Push-Sons(a) n else move-off(a);迭代从第一个位置开场，将数字1n和-1压入栈中，这里-1作为末尾标志。i = 1; L.Push(1, 2, , n, -1);a是末尾标志那么回溯。(a = = -1) backastep; 回溯需求回溯需求做什么？做什么？回溯需求退回一个位置

14、，即i ；同时删除该位置的原纪录。i ; a = reci; Move-Off(i, a); 假设safe(a)那么放下数字a。(Safe(a) Record(i, a);假设到了第n位，那么胜利。(i = = n) 当i n时，那么必定有后继。无需思索此情况。i+; L.Push(1, 2, , n, -1); N数全陈列问题的迭代程序nBacktrack(Tree T) n unfinish = true; i = 1; L.Push(1, 2, , n,-1);n while (unfinish | L) n a = L.Pop( ); n if (a = = -1) i ; a = r

15、eci; reci=0;useda=0;n else if (useda=0) n reci=a; useda=1;n if (i = = n) unfinish = false; output(rec);n else i+; L.Push(1, 2, , n, -1); n迭代求全陈列主程序nN-Queens(n) nint recn + 1, usedn + 1;nfor (j = 1, j n + 1; j+) n recj = 0; usedj =0; nBacktrack(n, rec);nN数全陈列问题的时间复杂性n对于规模为n的全陈列而言,该算法的时间复杂度也就是搜索的结点总数。

16、n为简单起见，只思索访问可扩展结点的时间。n将根结点所在层次标为0层，其他依次为1,2,n层。那么每层的可扩展结点数目依次为：n, n(n-1), n(n-1)(n-2), n(n-1)2, n!，设总的结点数目为S(n)，那么有 S(n)= n!/(k!)，故 2n!S(n)3n!故时间复杂度为O(n!)。 N后问题n要求在一个nn的棋盘上放置n个皇后，使得她们彼此不受攻击。n按照国际象棋的规那么，一个皇后可以攻击与之同一行或同一列或同一斜线上的任何棋子。n因此，N后问题等价于：要求在一个nn的棋盘上放置n个皇后，使得恣意两个皇后不得在同一行或同一列或同一斜线上。八皇后问题n先建立一个8*8

17、格的棋盘，在棋盘的第一行的恣意位置安放第一只皇后。n紧接着，我们就来放第二行，第二行的安放就要受一些限制了，由于与第一行的皇后在同一列或同一对角线的位置上是不能安放皇后的，接下来是第三行，n或许我们会遇到这种情况：在摆到某一行的时候，无论皇后摆放在什么位置，她都会被其它行的皇后吃掉，这时就必需求回溯，将前面的皇后重新摆放， 八皇后的一个可行解第1列第2列第3列第4列第5列第6列第7列第8列记录数组rec第1行1第2行 7第3行 5第4行 8第5行 2第6行 4用递归回溯法求N后问题nTry(s)n 做挑选候选者的预备；n while (未胜利且还有候选者) n 挑选下一个候选者next； n

18、if (next可接受) n 记录next；n if (满足胜利条件) 胜利并输出结果n else Try(s+1);n if (不胜利) 删去next的记录; n return 胜利与否先回想递归回溯法的普通方式： 用递归回溯法求N后问题nTry(s)n 做挑选候选者的预备；n while (未胜利且还有候选者) n 挑选下一个候选者next； n if (next可接受) n 记录next；n if (满足胜利条件) 胜利并输出结果n else Try(s+1);n if (不胜利) 删去next的记录; n return 胜利与否s为预备放置后的行数候选者为1到n列。j = 0; q =

19、 0; 令列标志j = 0；q表示未胜利。列数不到n就还有候选者(!q & j n ) 列数加1j+;各后都平安，便可接受(Safe(s, j) 记下该行后的位置(列数)Record(s, j);n行后都放完就胜利了(s = = n) q = 1; output( ); 不胜利，删去后在该行的位置。(!q) Move-Off(s, j); q 求解N后问题中的数据表示n数组Bn表示棋盘。假设Bi=j，1i, jn，表示棋盘的第i行第j列上有皇后。n数组Cj=1表示第j列上无皇后，1jn。n数组Dk=1表示第k条下行( )对角线上无皇后。1234561 2 3 4 5 6k = i +

20、j ，2k2n。这里，求解N后问题中的数据表示n数组Bn表示棋盘。假设Bi = j，1i, jn，表示棋盘的第i行第j列上有皇后。n数组Cj = 1表示第j列上无皇后，1jn。n数组Dk = 1表示第k条下行( )对角线上无皇后。k = i + j ，2k2n。这里，n数组Uk = 1表示第k条上行( )对角线上无皇后。1234561 2 3 4 5 6k = i j ， n+1kn1。 这里，求解N后问题中的子程序nRecord(s, j) k = s j + n 1;n Bs = j; Cj = 0; Ds + j 1 = 0; Uk = 0; nMove-Off(s, j) k = s

21、j + n 1;n Bs = 0; Cj = 1; Ds + j 1 = 1; Uk = 1; nSafe(s, j) k = s j + n 1;n if (Cj & Uk & Ds + j 1) return true n else return false; 求解N后问题的主程序nN-Queens( ) nint Bn + 1, Cn + 1, D2n, U2n;nfor (j = 1, j n + 1; j+) n Bj = 0; Cj = 1; n U2j = 1; U2j 1 = 1;n D2j = 1; D2j 1 = 1;ntry(1);noutput(B);

22、将数组Bn, Cn, U2n和D2n都赋予初值。从第一行开场递归N后问题的迭代程序n先看看迭代回溯法的普通方式：nBacktrack(Tree T) n unfinish = true; L.Push(T.root); n while (unfinish | L) n a = L.Pop( ); n if (a is the last mark) backastep( );n else if (a is good) record(a);n if (a is goal) unfinish = false; output( );n else if (a has sons) L.Push-Sons(

23、a) n else move-off(a);迭代从第一行开场，将第一行的1n列和0压入栈中，这里0作为末尾标志。i = 1; L.Push(1, 2, , n, 0);a是末尾标志那么回溯。(a = = 0) backastep; 回溯需求回溯需求做什么？做什么？回溯需求退回一行，即i ；同时删除该行的原纪录。i ; a = Bi; Move-Off(i, a); 假设safe(i, a)，那么放下后。(Safe(i, a) Record(i, a);假设到了第n行，那么胜利。(i = = n) 当行i n时，那么必定有后继。无需思索此情况。i+; L.Push(1, 2, , n, 0);

24、N后问题的迭代程序nBacktrack(Tree T) n unfinish = true; i = 1; L.Push(1, 2, , n);n while (unfinish | L) n a = L.Pop( ); n if (a = = 0) i ; a = Bi; Move-Off(i, a);n else if (Safe(i, a) Record(i, a);n if (i = = n) unfinish = false; output(B);n else i+; L.Push(1, 2, , n, 0); n迭代回溯解N后问题的主程序nN-Queens(n) nint Bn +

25、 1, Cn + 1, D2n, U2n;nfor (j = 1, j n + 1; j+) n Bj = 0; Cj = 1; n U2j = 1; U2j 1 = 1;n D2j = 1; D2j 1 = 1;nBacktrack(n, B);nN后问题的时间复杂性n假设只需找出N后问题的一个解，那么这是一个求途径的问题。n求途径：只需求找到一条途径便可以得到解。设每个形状有k个后继，其搜索树为K叉树，其结点总数为kn+11，遍历的时间为O(kn)，这里n为找到解的途径长度。nN后问题的途径深度为n，可选择的后继有n个，所以时间复杂性为O(nn)。游览售货员问题nTSP：某售货员到假设干城

26、市去推销商品，知各城市之间的路程(或旅费)。他要选定一条道路，经过每个城市一遍最后回到驻地的道路，使得总的路程(或总旅费)最小。n设G=(V, E)是一个带权图。图中各边的费用(权值)为正。图中一条周游道路是包括V中一切顶点的回路。一条周游道路的费用是该道路上一切边的费用之和。所谓游览售货员问题就是要在图G中找出一条最小费用的周游道路。nTry(s)n 做挑选候选者的预备；n while (未胜利且还有候选者)n 挑选下一个候选者next； n if (next可接受) n 记录next；n if (满足胜利条件) 胜利并输出结果n else Try(s+1);n if (不胜利) 删去nex

27、t的记录; n return 胜利与否线路上的第线路上的第s个结点个结点这里只需依次考这里只需依次考察察n1个结点，即个结点，即for (i=2; i=n; i+)下一个候选就是下一个候选就是i结点结点i尚未在道路中尚未在道路中且总耗费值不大。且总耗费值不大。思索TSP的递归回溯算法就是将结点就是将结点i放入道放入道路中并修正耗费值路中并修正耗费值s = = n假设新线路更好，就假设新线路更好，就用新线路取代老线路。用新线路取代老线路。这里无所谓胜利与否，这里无所谓胜利与否，由于每一条周游道路由于每一条周游道路都要进展比较。都要进展比较。TSP的递归回溯算法nTry(s)n for (i =

28、2; i = n; i+)n if (Accept(i) n Record(s, i)；n if (s = = n) n if (better) TakeNewPath( ) ; n else Try(s+1);n Move-off(s, i)n return 求解TSP的数据构造n用数组Cnn存放n个城市间的费用值。n用数组Pn记录曾经找到的费用最小的周游道路，C为其相应的费用， C初值为。n用数组Nn记录目前正在寻觅的周游道路，NC为其相应的费用；n假设NC+CNn1小于C，那么道路N更佳，于是P = N，C = NC+CNn1。n假设结点next不是N中已有的结点，且C大于 NC+CNi

29、next，那么结点next是可接受的。TSP的递归程序TrynTry(s)n for (i = 2; i NC+CNsi &Ti) 数组T表示结点i尚未被选(C NC+CNs1) TakeNewPath( ); Try中的子程序nRecord(s, i);n NC = NC + CNsi; Ti = 0; Ns = i; nMove-off(s, i);n NC = NC CNsi; Ti = 1; Ns = 0;nTakeNewPath( )n for (i=1; i=n; i+) Pi = Ni;n C = NC + CNs1;递归回溯求TSP的主程序nTSP(n, Cnn) n

30、for (i = 1; i CNja)Record(Nj,a);曾经n个结点且新道路的费用更低。这个判别不需求了(j = = n ) if (C NC+Ca1) TakeNewPath( ); Move-off(Nj, a); else j+; L.Push-Sons(2,n,0)TSP的迭代回溯nBacktrack(n, C) n j = 1; Nj = 1; L.Push-Sons(2,n,0);n while (L) a = L.Pop( ); n if (a = = 0) Move-off(Nj1, Nj); j ; n else if (Ta & C NC CNja) n R

31、ecord(Nj, a)；n if (j = = n ) n if (C NC+Ca1) n TakeNewPath( ); Move-off(Nj, a);n else j+; L.Push-Sons(2,n,0)Backtrack中的子程序nRecord(Nj,a);n NC = NC + CNja; Ta = 0; Nj+1 = a; nMove-off(Nj,a);n NC = NC CNja; Ta = 1; Nj+1 = 0;nTakeNewPath( ) n for (i=1; i=n; i+) Pi = Ni;n C = NC + CNj1;迭代回溯求TSP的主程序nTSP(n

32、, Cnn) n for (i = 1; i = n; i+) n Ni=0; Pi = 0; Ti = 1 n NC = 0；C = ; N1=1; T1 = 0; n Backtrack(n, C); n Output(P)；n 求解TSP的时间复杂性n显然TSP是一个求陈列的问题。n求陈列：确定n个元素的满足某种性质的陈列。其搜索树称为陈列树，通常有n!个叶结点，因此遍历陈列树需求时间为O(n!)。n所以TSP问题的时间复杂性为O(n!)0-1背包问题n给定n个物品和一个背包。物品i的分量为wi，价值为vi，背包容量为c。问如何选择装入背包中的物品，使得装入背包的物品的价值最大？n在装入

33、背包时，每种物品i只需两种选择，装入或者不装入，既不能装入多次，也不能只装入一部分。因此，此问题称为0-1背包问题。n假设在装入背包时，物品可以切割，即可以只装入一部分，这种情况下的问题称为背包问题。用回溯法解0-1背包问题n类似于游览售货员问题，用一个数组Pn存放目前获得的最优解，用变量V表示其价值；再用一个数组Nn来产生新的解，用变量NV表示其价值，用变量W表示其分量。假设新解更优，那么替代原来的最优解，否那么就丢弃新解。然后回溯寻觅下一个新解。n为此，我们先回想一下回溯法的普通递归算法：用回溯法解0-1背包问题nTry(s)n 做挑选候选者的预备；n while (未胜利且还有候选者)n

34、 挑选下一个候选者next； n if (next可接受) n 记录next；n if (满足胜利条件) 胜利并输出结果n else Try(s+1);n if (不胜利) 删去next的记录; n return 胜利与否调查的第s个物品只需考两种情况，选或不选，即for (i=0; i2; i+)下个候选就是i。物体s可放入背包中；将s放入背包中并修正权重与容量；s = = n这里无论胜利与否都要继续调查“记录的逆操作用回溯法解0-1背包问题nTry(s)n for (i = 0; i 2; i+)n if (Accept(i) n Record(s, i)；n if (s = = n) i

35、f ( better ) TakeNewChoice( ); n else Try(s+1);n Move-off(s, i);n return (W+ws*i V)0-1背包问题中的几个子程序nRecord(s, i) Ns = i; W=W + ws*i; n NV = NV + vs*i;nMove-off(s, i)Ns = 0; W = W ws*i; n NV = NV vs*i;nTakeNewChoice( ) n for (i=1; i=n; i+) n Pi = Ni; V = NV;0-1背包问题的主程序nBag(n, C, wn, vn) n for (i=1; i=n; i+) n Ni=0; Pi = 0; Ti = 1;n NV = 0, W = 0; V = 0; n Try(1); n Output(P); 思索0-1背包问题的迭代实现n先看看回溯法的普通的迭代方式： nBacktrack(Tree T) n unfinish = true; L.Push(T.root); n while (unfi