- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
通常g(d)的构造较易，h(d)的构造较难。
2020/3/30
计算机算法设计与分析
3
搜索路径的构造
在对每回一溯个法扩中展，的每结次点，仅建考立察三一个条信路息径： ，因 而只需要 构(1)造该这结点一的条名路称径；即可：前进时 记下相应 结(2)点它，的评回价溯函时数删值去；最末尾结点 的记录。 这(3)比指较向其容前易驱实的现指。针；
评价函数f(d)为1到d的代 价减去已经过的边数。
&& f(d)＜f’(d)，则②删d去O旧pe结n &点&并d将[Cdl,ofs(edd)。, p] 重新插入到Open中; 否则
⑻ 将[d, f(d), p] 插入到Open中}}}。
2020/3/30
计算机算法设计与分析
5
分支限界法求单源最短路径
单源最短路径问题的评价函数的构造：
g(d)定义为从源s到结点d所走的路径长度： g(d) = g(p) + C[p][d]
2 30 5
Open表
[[5[51,,,196000,,,0431]]] [43, 3650, 124] [24, 130, 1]
Closed表
[1, 0, 0] [2, 10, 1] [4, 30, 1]
50 10
60
3 20 4
[3, 50, 4]
初 取 取始 出 出[时[45123,,，01536,00将,,01413]源放]]放，放[入1入因入,C0其CC,loll0oos已]ess放dee经dd；入；；是生O生生目p成e成成标n其，其其结后C后后点继lo继继，s[e2[[d算3,32为,1, 法0615空,00成1,0,。2],4、3]]，] [并 和 功4,依 [并53,0序 终,9610插 止], 和43入 。][，，5O,前p修1e0n者订0。,因O1]p劣，en于并中C依已lo序有se放d的中入两的O个[p2e结,n1。点0, 并1]依而 序 被 依排 抛 据列 弃 逆。， 向后 指者针修可订得了最短Op路en径中为的1[→5, 49→0, 34→]。5。
2020/3/30
计算机算法设计与分析
8
用分支限界法求TSP
TSP是求排列的问题，不是仅找一条路径而已。 因而需要对分支限界法的一般算法作些修改：
(1)待扩展的结点如果在本路径上已经出现，则 不再扩展，但若是在其他路径上出现过，则仍 需要扩展。
(2)新结点，无论其优劣，既不影响其它路径上 的结点，也不受其它路径上的结点的影响。
这里p为d的前驱结点，C[p][d]为p到d的距离。 h(d)定义为0。于是f(d) = g(d)。
源s的评价函数f(s) = 0。
评价函数的下界为0；上界初始时为∞，以后不 算机算法设计与分析
6
分支限界法求最短路径举例
赋权图G
1
10
100
⑸ 若p是目标，则考虑修改上界函数值；否则
⑹ {将[p, f(p), L]放入Closed;
⑺ 在该路径上扩展结点p；对每个后继d
⑻ {计算f(d)；
⑼ 若f(d)＜U, 则{L = L {p};
将[d, f(d),L]依序放入Open。}
}}}
2020/3/30
计算机算法设计与分析
10
2020/3/30
计算机算法设计与分析
2
评价函数的构造
评价函数要能够提供一个评定候选扩展结点的 方法，以便确定哪个结点最有可能在通往目标 的最佳路径上。
一个评价函数f(d)通常可以由两个部分构成： ⑴从开始结点到结点d的已有耗损值g(d)，和⑵ 再从结点d到达目标的期望耗损值h(d)。即：
f(d) = g(d) + h(d)
分支限界法求TSP举例
设有向图G = (V, E)的边的代价矩阵为C = [cij]。 若不存在有向边<i, j>∈E，则定义cij=∞且规定 cii=∞。不失一般性，设周游路线均以顶点1为起 点。左下为一个有向图G的代价矩阵C。
∞ 25 40 31 27 5 ∞ 17 30 25 19 15 ∞ 6 1
2020/3/30
计算机算法设计与分析
7
界限(Bounding)
评价函数f(d)关系着算法的效率乃至成败。
因为在大多数问题中f(d)只是个估计值，所以 单靠f(d)是不够的。通常还要设计它的上下界 函数U(d)和L(d)。 L(d)≤f(d)≤U(d)。
所谓分支限界法就是通过评价函数及其上下界 函数的计算，将状态空间中不可能产生最佳解 的子树剪去，减少搜索的范围，提高效率。因 而更准确的称呼应是“界限剪支法”
在这样分一支旦限找界到法目中标，即是可同逆时向考构察造若其干路径条。路 径用一，个那表么保又存该准如备何扩展构的造结搜点索，的称路为径Op呢en表？。
用一个表保存已搜索过的结点，称为Closed表。
2020/3/30
计算机算法设计与分析
4
分支限界法的一般算法
⑴计算初始结点s的f(s); [s, f(s), nil]放入Open; ⑵while (Open ≠Φ) { ⑶ 从Open中取出[p, f(p), x](f(p)为最小); ⑷ 将[p, f(p), x]放入Closed; ⑸ 若p是目标，则成功返回；否则 ⑹ { 产生p的后继d并计算f(d) ；对每个后继d ⑺ {若有(二[d种, f情’(d况), ：p]①CdlosCedlo|s| e[d,||fd’(d)O, pp]enO；pen)
第六章
分支限界法
2020/3/30
计算机算法设计与分析
1
分支限界法是最佳优先搜索法
分支限界法就是最佳优先(包括广度优先在内) 的搜索法。
分支限界法将要搜索的结点按评价函数的优劣 排序，让好的结点优先搜索，将坏的结点剪去。 所以准确说，此方法应称为界限剪支法。
分支限界法中有两个要点：
(1)评价函数的构造； (2)搜索路径的构造。
(3)依据上界函数决定结点是否可以剪去。
2020/3/30
计算机算法设计与分析
9
分支限界法求排列
⑴计算初始结点s的f(s); [s, f(s), nil]放入Open;
⑵while (Open ≠Φ) {
⑶ 从Open中取出[p, f(p), L]; //L是路径已有结点
⑷ 若f(p)≥U，则抛弃该路径；
