算法设计与分析(第六章)

1、2021-11-5计算机算法设计与分析1第六章分支限界法2021-11-5计算机算法设计与分析2树搜索的一般形式 SearchTree(Space T) ok = 0; L = T.initial; while (!ok | L) a = L.first; if (a is goal) unfinish = false else Control-put-in(L, Sons(a); 三种搜索方法的不同就在三种搜索方法的不同就在于存放待考察的结点的表于存放待考察的结点的表L的控制方式不同：的控制方式不同：DFS(回溯法回溯法)是栈；是栈；WFS是队列；是队列；BFS是队列中的元素排序。是队列中的

2、元素排序。2021-11-5计算机算法设计与分析3分支限界法基本思想 分支限界法就是最佳优先(包括广度优先)的搜索法。其基本思想是：将要待考察的结点按其优劣排序，优先搜索好结点。 于是便有了两个问题： (1)如何知道结点的优劣？ (2)在回溯法中，表L中结点的层次分明，因而路径也分明。但是这里排序会打乱表L中结点的层次，那又如何找回解的路径呢？2021-11-5计算机算法设计与分析4分支限界法基本思想 分支限界法就是最佳优先(包括广度优先)的搜索法。其基本思想是：将要待考察的结点按其优劣排序，优先搜索好结点。 于是便有了两个要点： (1)需要构造评价结点优劣的评价函数。 (2)需要能够重新构造

3、解的路径，也就是搜索的路径。2021-11-5计算机算法设计与分析5评价函数的构造 评价函数要能够提供一个评定候选扩展结点的方法，以便确定哪个结点最有可能在通往目标的最佳路径上。 一个评价函数f(d)通常由两个部分构成： 从开始结点到d的已有耗损值g(d)，和 再从d到达目标的期望耗损值h(d)。即： f(d) = g(d) + h(d)。 通常g(d)的构造较易，h(d)的构造较难。2021-11-5计算机算法设计与分析6搜索路径的构造 在回溯法中，每次仅考察一条路径，因而只需要构造这一条路径即可：前进时记下相应结点，回溯时删去最末尾结点的记录。这比较容易实现。 在分支限界法中，是同时考察若

4、干条路径，那么又该如何构造搜索的路径呢？ 往前看，前程无数！往回看，来路一条。每个结点只要记住其前驱结点就行了！2021-11-5计算机算法设计与分析7搜索路径的构造 为此，只需要对每一个扩展的结点d，建立三个信息： (1)该结点的名称d； (2)它的评价函数值f(d)； (3)指向其前驱的指针p； 即表示为d, f(d), p。 这样一旦找到目标，即可以很方便地逆向构造出该路径。2021-11-5计算机算法设计与分析8Open表与Closed表 搜索中，表L用来保存准备扩展的结点，即下一步的结点。把表L称为Open表。 此外，为了构造解的路径，还需要一个表来保存已经搜索过的结点，即已经走过的

5、结点。此表被称为Closed表。 故任意结点d必是： dOpen &dClosed； dClosed | d Open。结点结点d尚未尚未被考察。被考察。结点结点d已经已经被考察。被考察。2021-11-5计算机算法设计与分析9分支限界法的一般算法 初始化：计算起点s的f(s); s, f(s), nil放入Open; while (Open ) 从Open中取出p, f(p), x(f(p)为最小); if (f(p) U) 将p, f(p), x放入Closed; if (p是目标) 成功返回 else 产生p的后继d并计算f(d) ；对每个后继d有二种情况： dOpen &

6、; dClosed ； dClosed | d Open 。若结点若结点d尚未被考察，则尚未被考察，则将将d, f(d), p插入到插入到Open中中。若若f(p)U，则，则剪去该路径。剪去该路径。2021-11-5计算机算法设计与分析10分支限界法的一般算法 初始化：计算起点s的f(s); s, f(s), nil放入Open; while (Open ) 从Open中取出p, f(p), x(f(p)为最小); if (f(p) U) 将p, f(p), x放入Closed; if (p是目标) 成功返回 else 产生p的后继d并计算f(d) ；对每个后继d有二种情况： dOpen &a

7、mp; dClosed ； dClosed | d Open 。若结点若结点d已被考察，则说明这次是通过另一已被考察，则说明这次是通过另一条路径到达到条路径到达到d 。设。设d原来评价为原来评价为f(d)，将其，将其与新的评价与新的评价f(d)比较。若新评价更好，则删比较。若新评价更好，则删去旧的，将新的插入到去旧的，将新的插入到Open中；否则丢弃。中；否则丢弃。2021-11-5计算机算法设计与分析11分支限界法的一般算法 初始化：计算起点s的f(s); s, f(s), nil放入Open; while (Open ) 从Open中取出p, f(p), x(f(p)为最小); if (f

8、(p) U) 将p, f(p), x放入Closed; if (p是目标) 成功返回 else 产生p的后继d并计算f(d) ；对每个后继d if (dClosed & dOpen) 将d, f(d), p 插入到Open中 else if (f(d)f(d) 删去旧结点并将d, f(d), p重新插入到Open中。2021-11-5计算机算法设计与分析12分支限界法求单源最短路径 单源最短路径问题的评价函数的构造： g(d)定义为从源s到结点d所走的路径长度：g(d) = g(p) + Cpd， 这里p为d的前驱结点，Cpd为p到d的距离。 h(d)定义为0。于是f(d) = g(d

9、)。 源s的评价函数f(s) = 0。 评价函数的下界为0；上界初始时为，以后不断用取得的更短路径的长度来替代。2021-11-5计算机算法设计与分析13分支限界法求最短路径举例12543102050100301060赋权图G初始时，将源1, 0, 0放入Open，Closed为空。Open表1, 0, 0Closed表取出1, 0, 0放入Closed；生成其后继2, 10, 1、 4, 30, 1和5, 100, 1，并依序放入Open。1, 0, 05, 100, 14, 30, 12, 10, 1取出2, 10, 1放入Closed；生成其后继3, 60, 2，并依序插入Open。2,

10、 10, 13, 60, 24, 30, 1取出4, 30, 1放入Closed；生成其后继3, 50, 4和5, 90, 4 ，修订Open中已有的两个结点并依序排列。4, 30, 15, 90, 43, 50, 4取出3, 50, 4放入Closed；生成其后继2, 100, 3和5, 60, 3，前者因劣于Closed中的2, 10, 1而被抛弃，后者修订了Open中的5, 90, 4。3, 50, 45, 60, 3取出5, 60, 3，因其已经是目标结点，算法成功并终止。依据逆向指针可得最短路径为1435。2021-11-5计算机算法设计与分析14界限(Bounding) 评价函数f

11、(d)关系着算法的效率乃至成败。 因为在大多数问题中f(d)只是个估计值，所以单靠f(d)是不够的。通常还要设计它的上下界函数U(d)和L(d)。 L(d)f(d)U(d)。 所谓分支限界法就是通过评价函数及其上下界函数的计算，将状态空间中不可能产生最佳解的子树剪去，减少搜索的范围，提高效率。因而更准确的称呼应是“界限剪支法”2021-11-5计算机算法设计与分析15用分支限界法求TSP TSP是求排列的问题，不是仅找一条路径而已。因而需要对分支限界法的一般算法作些修改： (1)待扩展结点若已在本路径上，则不再扩展，但若是在其他路径上出现过，则仍需要扩展。 为此，用一个表L来存储该路径出现的结

12、点，即将d, f(d), p改为d, f(d), *L。该结点是否已经出现过，可查该结点是否已经出现过，可查Closed表或表或者者Open表。但是要查它出现在哪条路径表。但是要查它出现在哪条路径上，就颇费周章了。上，就颇费周章了。这个这个L该怎么做？该怎么做？2021-11-5计算机算法设计与分析16用分支限界法求TSP TSP是求排列的问题，不是仅找一条路径而已。因而需要对分支限界法的一般算法作些修改： (1)待扩展结点若在本路径上已经出现，则不再扩展，但若是在其他路径上出现过，则仍需要扩展。 为此，用一个表L来存储该路径出现的结点。 (2)新结点，无论其优劣，既不影响其它路径上的结点，也

13、不受其它路径上的结点的影响。 (3)若考察结点的评价值超过上界值，则可以剪去。这实际上是剪去了这一支。L可设计为数组可设计为数组Ln，初始值都为，初始值都为n；每加；每加入新结点入新结点i，则，则Li = p，这里，这里p是是i的前驱结的前驱结点。若点。若Li n，则则i已在此路径中。这样结已在此路径中。这样结点点i的插入时间和判定时间都为常量。的插入时间和判定时间都为常量。2021-11-5计算机算法设计与分析17分支限界法的一般算法 初始化：计算起点s的f(s); s, f(s), nil 放入Open; while (Open ) 从Open中取出p, f(p), x(f(p)为最小);

14、 if (f(p) U) 将p, f(p), x放入Closed; if (p是目标) 成功返回 else 产生p的后继d并计算f(d) ；对每个后继d if (dClosed & dOpen) 将d, f(d), p 插入到Open中 else if (f(d)f(d) 删去旧结点并将d, f(d), p重新插入到Open中。不失一般性，令不失一般性，令0为起点，为起点，U为上界值：为上界值： Initialization： U = ; Open = Closed = ; 计算计算f(0)； 产生空表产生空表L；/L0 = 0, n, , n Put-ordered-in(Open,

15、 0, f(0), *L); /把把0, f(0), *L)按序放入按序放入Open表中。表中。/ 2021-11-5计算机算法设计与分析18分支限界法的一般算法 Initialization； while (Open ) 从Open中取出p, f(p), x (f(p)为最小); if (f(p) U) 将p, f(p), x放入Closed; if (p是目标) 成功返回 else 产生p的后继d并计算f(d) ；对每个后继d if (dClosed & dOpen) 将d, f(d), p 插入到Open中 else if (f(d)f(d) 删去旧结点并将d, f(d), p重

16、新插入到Open中。*L此处改为表此处改为表L。2021-11-5计算机算法设计与分析19分支限界法的一般算法 Initialization； while (Open ) 从Open中取出p, f(p), *L(f(p)为最小); if (f(p) U) 将p, f(p), x放入Closed; if (p是目标) 成功返回 else 产生p的后继d并计算f(d) ；对每个后继d if (dClosed & dOpen) 将d, f(d), p 插入到Open中 else if (f(d)f(d) 删去旧结点并将d, f(d), p重新插入到Open中。此句可以不要了。此句可以不要了。

17、因为每条通路上考察过因为每条通路上考察过的结点放在表的结点放在表L中了。中了。Closed表表L不再需要了。不再需要了。2021-11-5计算机算法设计与分析20分支限界法的一般算法 Initialization； while (Open ) 从Open中取出p, f(p), *L(f(p)为最小); if (f(p) U) if (p是目标) 成功返回 else 产生p的后继d并计算f(d) ；对每个后继d if (dClosed & dOpen) 将d, f(d), p 插入到Open中 else if (f(d)f(d) 删去旧结点并将d, f(d), p重新插入到Open中。如

18、何知道如何知道p是目标？是目标？如果如果L中已有中已有n个结点了，则个结点了，则p是目标。是目标。那又如何知道那又如何知道L中已有中已有n个结点了？个结点了？2021-11-5计算机算法设计与分析21分支限界法的一般算法 Initialization； while (Open ) 从Open中取出p, f(p), *L(f(p)为最小); if (f(p) U) if (p是目标) 成功返回 else 产生p的后继d并计算f(d) ；对每个后继d if (dClosed & dOpen) 将d, f(d), p 插入到Open中 else if (f(d)f(d) 删去旧结点并将d,

19、f(d), p重新插入到Open中。L中存放的是每个结点的前驱，故可用中存放的是每个结点的前驱，故可用L0作计数器。初始化时作计数器。初始化时L0=1；之后每加入一；之后每加入一个结点，个结点，L0+。当。当L0=n，则已达目标。，则已达目标。2021-11-5计算机算法设计与分析22分支限界法的一般算法 Initialization； while (Open ) 从Open中取出p, f(p), *L(f(p)为最小); if (f(p) U) if (p是目标) 成功返回 else 产生p的后继d并计算f(d) ；对每个后继d if (dClosed & dOpen) 将d, f(

20、d), p 插入到Open中 else if (f(d)f(d) 删去旧结点并将d, f(d), p重新插入到Open中。所以，这里应改为：所以，这里应改为： if (L0=n) S =p, f(p), *Lp; U = f(p) else /这里变量这里变量S用于存放解。用于存放解。/2021-11-5计算机算法设计与分析23分支限界法的一般算法 Initialization； while (Open ) 从Open中取出p, f(p), *L(f(p)为最小); if (f(p) U) if (L0=n) S =p, f(p), *Lp; U = f(p) else 产生p的后继d并计算f

21、(d) ；对每个后继d if (dClosed & dOpen) 将d, f(d), p 插入到Open中 else if (f(d)f(d) 删去旧结点并将d, f(d), p重新插入到Open中。因为因为TSP要考察每一条要考察每一条通路，只要这条通路没通路，只要这条通路没走完，就要继续考察。走完，就要继续考察。 扩展结点扩展结点p：对：对p的每个后继结点的每个后继结点d，若，若d不在不在L中，则中，则计算计算f(d); 若若f(d) U, 则生成则生成d, f(d), *Ld并将其按序放入并将其按序放入Open表中表中; 2021-11-5计算机算法设计与分析24扩展结点p 扩展

22、结点p需要做的事情有： 对p的每个后继结点d， 若d不在L中，则 计算f(d)； 若f(d)U，则生成d, f(d), *Ld并将其按序放入Open表中。什么样的结点是什么样的结点是p的的后继结点？后继结点？令代价矩阵为令代价矩阵为Cnn。若若Cpd ，则则d是是p的后继结点。的后继结点。即：即：for (d = 1, d n, d+) if (Cpd ) 。0是起点，无需考虑。是起点，无需考虑。if (Ld = n) then把这两个把这两个if 写在一起。写在一起。2021-11-5计算机算法设计与分析25扩展结点p 扩展结点p需要做的事情有： 对p的每个后继结点d， 若d不在L中，则 计

23、算f(d)； 若f(d)U，则生成d, f(d), *L并将其按序放入Open表中。for (d = 1, d n, d+) if (L(d) = =n &Cpd ) then V = f(d); /调用评价函数计算调用评价函数计算f(d)/ if (V U) 生成生成Ld; Ld = L d; Put-ordered-in(Open, d, f(d), *Ld)需要为需要为d生成一个其生成一个其自有的路径表自有的路径表Ld。将将p的路径表的路径表L插入插入p的后继结点的后继结点d之后之后再赋值给再赋值给Ld 。最后将新扩展结点最后将新扩展结点d按序放入按序放入Open表中表中 。20

24、21-11-5计算机算法设计与分析26扩展结点p Develop(p, f(p), *L) for (d = 1, d n, d+) if (L(d) = n &Cpd ) then V = f(d); /调用评价函数计算f(d)/ if (V U) 生成Ld; Ld = L d; Put-ordered-in(Open, d, f(d), *Ld)2021-11-5计算机算法设计与分析27分支限界法的一般算法 Branch-bounding-for-TSP(n, *C) Initialization； while (Open ) 从Open中取出p, f(p), *L(f(p)为最小

25、); if (f(p) U) if (L0=n) S =p, f(p), *Lp; U = f(p) else Develop(p, f(p), *Lp ; 2021-11-5计算机算法设计与分析28分支限界法求TSP举例 设有向图G = (V, E)的边的代价矩阵为C = cij。若没有有向边E，则定义cij=且规定cii=。不失一般性，设周游路线均以顶点1为起点。左下为一个有向图G的代价矩阵C。 25 40 31 27 5 17 30 2519 15 6 1 9 50 24 622 8 7 10 l评价函数f(d)为1到d的代价减去已经过的边数。l初始时f(1) = 0; lf(d) =

26、f(p) + cpd 1，这里p是d的前驱。 2021-11-5计算机算法设计与分析29分支限界法求TSP的搜索 25 40 31 27 5 17 30 2519 15 6 1 9 50 24 622 8 7 10 102243394305262340453548523333243542793535453246437234946242843584286找到了一条周游路线153421，其长度为95。这不是最短周游路线，需要修改上界后继续搜索。装载问题问题描述有一批n个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且211ccwnii装载问题要求确定是否有一个合理的装载方

27、案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。 容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。 (1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。 31队列式分支限界法 在算法的while循环中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。 活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判

28、断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。32队列式分支限界法while (true) if (ew + wi = c) enQueue(ew + wi, i); / 检查左儿子结点 enQueue(ew, i); /右儿子结点总是可行的 ew = (Integer) queue.remove().intValue(); / 取下一扩展结点 if (ew = -1) if (queue.isEmpty() return bestw; queue.put(new Integer(-1); / 同层结点尾部标志 ew = (Integer) qu

29、eue.remove().intValue(); / 取下一扩展结点 i+; / 进入下一层 33算法的改进 节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew+rbestw时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。 另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。34算法的改进/ 检查左儿子结点 int wt = ew + wi; if (wt bestw) bestw = wt; / 加入活结点队列 if (i bestw &a

30、mp; i 0; j-) bestxj = (e.leftChild) ? 1 : 0; e = e.parent; 37优先队列式分支限界法 解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点活结点x x在优先队列中的优先级在优先队列中的优先级定义为从根结点到结点定义为从根结点到结点x x的路径所相应的载重量再加的路径所相应的载重量再加上剩余集装箱的重量之和。上剩余集装箱的重量之和。 优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。 在优先队列式分支限界法中，一旦有一个

31、叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。 380-1背包问题算法的思想 首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。 在下面描述的优先队列分支限界法中，节点的优节点的优先级由已装袋的物品价值加上剩下的最大单位重量价先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。值的物品装满剩余容量的价值和。 算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队

32、列。当扩展到叶节点时为问题的最优值。39上界函数while (i = n & wi = cleft) / n表示物品总数，cleft为剩余空间 cleft -= wi; /wi表示i所占空间 b += pi; /pi表示i的价值 i+; if (i = n) b += pi / wi * cleft; / 装填剩余容量装满背包return b; /b为上界函数400-1背包问题 while (i != n + 1) / 非叶结点 double wt = cw + wi; if (wt bestp) bestp = cp + pi; addLiveNode(up,cp + pi,cw +

33、 wi,i + 1, enode, true); up = bound(i + 1); if (up = bestp) /检查右儿子节点 addLiveNode(up,cp,cw,i + 1, enode, false); / 取下一个扩展节点（略）分支限界搜索分支限界搜索过程过程41批处理作业问题问题的描述 给定n个作业的集合J=J1,J2,Jn。每一个作业Ji都有2项任务要分别在2台机器上完成。每一个作业必须先由机器1处理，然后再由机器2处理。作业Ji需要机器j的处理时间为tji，i=1,2,n；j=1,2。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。则所有作业在机器

34、2上完成处理的时间和niiFf12 称为该作业调度的完成时间和。批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。42限界函数在结点E处相应子树中叶结点完成时间和的下界是：,max212SSFfMii注意到如果选择Pk，使t1pk在k=r+1时依非减序排列，S1则取得极小值。同理如果选择Pk使t2pk依非减序排列，则S2取得极小值。 ,max212SSFfMii这可以作为优先队列式分支限界法中的限界函数。 43算法描述 算法的while循环完成对排列树内部结点的有序扩展。在while循环体内算法依次从活结点优先队列中取出具有最小bb值（完成时间和下界）的结

35、点作为当前扩展结点，并加以扩展。 首先考虑enode.s=n的情形，当前扩展结点enode是排列树中的叶结点。enode.sf2是相应于该叶结点的完成时间和。当enode.sf2 bestc时更新当前最优值bestc和相应的当前最优解bestx。 当enode.sn时，算法依次产生当前扩展结点enode的所有儿子结点。对于当前扩展结点的每一个儿子结点node，计算出其相应的完成时间和的下界bb。当bb bestc时，将该儿子结点插入到活结点优先队列中。而当bb bestc时，可将结点node舍去。 44算法描述 do if (enode.s = n ) / 叶结点 if (enode.sf2

36、bestc) bestc = enode.sf2; for (int i = 0; i n; i+) bestxi = enode.xi; 当当enode.sf2bestcenode.sf2bestc时，时，更新当前最优值更新当前最优值bestebeste和和相应的最优解相应的最优解bestxbestx45 else / 产生当前扩展结点的儿子结点 for (int i = enode.s; i n; i+) MyMath.swap(enode.x, enode.s,i); int f= new int 3; int bb=bound(enode,f); if (bb bestc HeapNo

37、de node=new HeapNode(enode,f,bb,n); heap.put(node); MyMath.swap(enode.x, enode.s,i); / 完成结点扩展当当bbbestcbbbestc时，将儿时，将儿子结点插入到活结点子结点插入到活结点优先队列中优先队列中) 2021-11-5计算机算法设计与分析46评价函数影响搜索效率 前面的搜索的效率不高，几乎要搜索全部的状态空间。其原因是评价函数性能不好以及上下界的估计太低。 要提高搜索效率，就必须要提高评价函数的性能，并精确上界的估计值。 为了设计求解TSP问题的更好的评价函数，先定义其代价矩阵的归约矩阵和约数。202

38、1-11-5计算机算法设计与分析47归约矩阵以及约数 给定代价矩阵C，从C的任何行i(或列i)的各元素中减去此行(或此列)的最小元素的值r(i)(或r(i)，称为对i行(或i列)的归约。 将C的各行和各列都归约后的矩阵称为C的归约矩阵。 数r = in r(i) + in r(i)，即各行最小元素的值之和加上各列最小元素之和，称为C的约数。2021-11-5计算机算法设计与分析48例子中的归约矩阵和约数 计算前面例子中的归约矩阵及其约数如下： 25 40 31 27 5 17 30 2519 15 6 1 9 50 24 622 8 7 10 先做行归约： 25 40 31 27 5 17 3

39、0 2519 15 6 1 9 50 24 622 8 7 10 r(1) = 25 0 15 6 2r(2) = 5 0 12 25 20r(3) = 118 14 5 0r(4) = 6 3 44 21 0r(5) = 715 1 0 3 2021-11-5计算机算法设计与分析49例子中的归约矩阵和约数 计算前面例子中的归约矩阵及其约数如下： 25 40 31 27 5 17 30 2519 15 6 1 9 50 24 622 8 7 10 再做列归约： 25 40 31 27 5 17 30 2519 15 6 1 9 50 24 622 8 7 10 r(1) = 25 0 15 6

40、 2r(2) = 5 0 12 25 20r(3) = 118 14 5 0r(4) = 6 3 44 21 0r(5) = 715 1 0 3 r(1)=r(2)=r(3)=r(5)=0r(4) = 3322 047 约数 r = 47。归约矩阵归约矩阵这个约数这个约数r是什么呢？是什么呢？2021-11-5计算机算法设计与分析50约数是周游路线代价的下界 定理：设C是图G的代价矩阵，P是周游路线，则P的代价，即P cij = r + P cij ， 式中C = cij是C的归约矩阵，r为约数。 证明：由归约矩阵的构造可知： cij = cij r(i) r(j)，即cij = cij +

41、r(i) + r(j)。 任何周游路线包含n条边并且对应在C中的每行每列有且仅有一条边。于是 Pcij =P(cij + r(i) + r(j) = r +Pcij。原来约数原来约数r r是图是图G的任何一条周游路的任何一条周游路线的代价的下界线的代价的下界! !2021-11-5计算机算法设计与分析51用约数定义期望函数h(d) 既然约数是周游路线长度的下界，可以考虑用约数来定义期望函数h(d)： 对开始结点1，令g(1) = 0，h(1) = r，f(1) = r。 若从结点1选择了一条边，不妨设边，则令g(2) = f(1)+从1到2的距离l ，显然l应该是c12，而不应该再是c12了。

42、 那么h(2) = ？ 自然可以想到h(2)是从2开始的路线的下界r2。 是否可用类似求r一样去求新的约数r2呢？2021-11-5计算机算法设计与分析52求新的约数r2 可以。要先将边和所有边和边都删去，即置c12、c1k和ck2为。 设Cp为路线上点p的归约矩阵。从p选择边所得点d的归约矩阵Cd和约数rd为： 先将Cp中的cpd，cpk和ckd都置为，这里1kn，即删去这些边； 依照求归约矩阵C的方法对Cp进行行归约和列归约，便得到了Cd和rd。因为边因为边已走过，所以不可已走过，所以不可能再走边能再走边和边和边了。了。2021-11-5计算机算法设计与分析53新的评价函数f(d) 不失一

43、般性，将图G中结点标记为1n，并设0为起点。将图G的代价矩阵C的约数r和归约矩阵C分别为起点0的约数r1和归约矩阵C1。 对任意路线上结点d，定义其评价函数为：f(d) = g(d) + h(d)， 其中： g(d) = f(p) + Cppd，这里p为d的前驱结点，并规定g(1) = 0； h(d) = rd。两点在两点在p的归约矩阵中的代价的归约矩阵中的代价2021-11-5计算机算法设计与分析54用新的评价函数求TSP 下面用新的评价函数求前面的例子，我们已经求得了它的归约矩阵C和约数r = 47。 0 15 3 2 0 12 22 2018 14 2 0 3 44 18 015 1 0

44、 0 1472g(2) = 47 + 0 = 47 0 10801512h(2) = 12 + 3 = 15f(2) = 47 +15 = 62623 0 15 3 2 0 12 22 2018 14 2 0 3 44 18 015 1 0 0 g(3) = 47 + 15 = 62 04313h(3) = 1f(3) = 63634类似地可求出 f(4) = 51。515类似地可求出 f(5) = 50。50下面优先扩展的是结点5。2此时C2是在C5的基础上进行。右边就是C5。 0 12 22 18 14 2 3 44 18 0 0 0 g(2) = 50 + 0 = 50 01601503

45、h(2) = 17f(2) = 67673类似地计算出f(3) = 68684类似地计算出f(4) = 8181下面扩展f(4) = 51的结点4。并用同样方法计算它们的评价函数值。2121369464154 下面要扩展的结点 是f(2)= 62的结点2。 右边是其对应的归 约矩阵C2。2 0 10 815 2 0 0 18 012 0 0 3g(3) = 62 + 0 = 62；对C2进行归约， 得h(3) = 0；于是f(3) = 62。62对结点2的另外两个儿子进行同样的计算，得：f(4) = 84，f(5) = 72。484572下面对f(3) = 62的结点3进行扩展。它有两个后继结点。345对结点4，g(4) = 62 + 2 = 64。0h(4) = 12 ，于是f(4) = 64 + 12 = 7676对结点5，g(5) = 62 + 0 = 62。 15 2 0 0 012 0 h(5) = 0，于是f(5) = 62 + 0 = 6262对结点5(f(5) = 62)再进行扩展。54g(4) = 62 + 0 = 62，h(4) = 0，f(4) =