分支限界法的基本思想.ppt

6.1 分支限界法的基本思想6.1 分支限界法的基本思想6.1 分支限界法的基本思想分支限界法(BranchandBound)算法设计与分析>分支限界法问题陈述设有n个物体和一个背包,物体i的重量为wi价值为pi,背包
的载荷为M,若将物体i(1in,)装入背包,则有价值为pi.
目标是找到一个方案,使得能放入背包的物体总价值最高.6.3装载问题6.3装载问题6.3装载问题6.3装载问题6.3装载问题6.3装载问题6.3装载问题6.3装载问题布线问题的解空间是一个图，适合采用队列式分支限界法来解决。从起始位置a开始将它作为第一个扩展结点。与该结点相邻并且可达的方格被加入到活结点队列中，并且将这些方格标记为1，表示它们到a的距离为1。接着从活结点队列中取出队首作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活节点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止（表示没有通路）。现在来看上面两张图。演示了分支限界法的过程。最开始，队列中的活结点为标1的格子，随后经过一个轮次，活结点变为标2的格子，以此类推，一旦b方格成为活节点便表示找到了最优方案。为什么这条路径一定就是最短的呢？这是由于我们这个搜索过程的特点所决定的，假设存在一条由a至b的更短的路径，b结点一定会更早地被加入到活结点队列中并得到处理。
最后一个图表示了a和b之间的最短布线路径。值得一提的是，在搜索的过程中我们虽然可以知道结点距起点的路径长度，却无法直接获得具体的路径描述。为了构造出具体的路径，我们需要从目标方格开始向起始方格回溯，逐步构造出最优解，也就是每次向标记距离比当前方格距离少1的相邻方格移动，直至到达起始方格时为止。
现在我们来考虑，为什么这个问题用回溯法来处理就是相当低效的。
回溯法的搜索是依据深度优先的原则进行的，如果我们把上下左右四个方向规定一个固定的优先顺序去进行搜索，搜索会沿着某个路径一直进行下去直到碰壁才换到另一个子路径，但是我们最开始根本无法判断正确的路径方向是什么，这就造成了搜索的盲目和浪费。更为致命的是，即使我们搜索到了一条由a至b的路径，我们根本无法保证它就是所有路径中最短的，这要求我们必须把整个区域的所有路径逐一搜索后才能得到最优解。正因为如此，布线问题不适合用回溯法解决。算法思路:设周游路线从结点1开始,解为等长数组X=(1,x2,...xn)
xi{2,...,n}.则解空间树为排列树.在树中做广度优先搜索,
约束条件:xixj,ij;
目标函数:解向量对应的边权之和
目标函数限界初值:U=
c(x):以x为根的叶子中路权最大值
:从根至x的部分路径的权值.算法设计与分析>分枝限界法算法设计与分析>分枝限界法算法设计与分析>分枝限界法算法思路:问题的解为n元向量X={X[1],X[2],...X[n]},xi{1...n}
解空间为排序树,在树中做广度优先搜索,
D:(1)X[i]X[j],ij时.
(2)total[j]:连接块Nj中的电路板数。
now[j]:部分解x[1:i]中所包含的Nj中的电路板数。
连接块Ni的连线跨越插槽i和i+1iffnow[j]>0且now[j]total[j]目标函数:density(X);
c(i):以i为根的叶子中路权(density值)最大者
:从根至i的部分路径长.算法设计与分析>回溯法算法设计与分析>回溯法