第六章 分支限界法

分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索解的算法。

1.但分支限界法与回溯法有不同的求解目标:

回溯法的求解目标是找出T中满足约束条件的所有解，或任意一个解;

分支限界法的求解目标则是找出T中使得某一目标函数值达到极小或极大的解，即问题在某种意义下的最优解。

2.由于求解目标不同， 导致分支限界法与回溯法在解空间树T上搜索的算法有两点不同：

（1）回溯法以深度优先的方式搜索解空间树T;分支限界法以广度优先或最小耗费优先的方式搜索解空间树T。

（2）回溯法一般只通过约束条件，而分支限界法不仅通过约束条件，而且通过目标函数的限界来减少无效搜索，提高求解效率。

3.分支限界法的搜索策略是：

在扩展结点处，先生成其所有儿子结点（使其变为活结点），然后再从当前的活结点表中选择下一个扩展结点。

为了有效地选择下一个扩展结点，以加速搜索的进程，在每一活结点处，计算一个函

数值（限界），并根据这些已计算出的函数值【耗费】，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。

【Best-First-Search】

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

在问题的边带权的解空间树中进行广度优先搜索，找一个回答结点使其对应路径的权最小（最大）。当搜索到达一个拓展结点时，一次性拓展它的所有儿子，将那些满足约束条件且最小耗费函数<=目标函数限界的儿子，插入活动结点表中，再从活动结点表中取下一结点同样拓展，直到找到所需的解或活动结点表为空为止。

5. 队列式(FIFO)

优先队列式(PQ, Prioroty Queue)

---优先队列可用堆实现

所以，常见的分支限界法分为：

（1）队列式(FIFO)分支限界法

（2）优先队列式（PQ）分支限界法

6.用队列式分支限界法求解单源最短路径问题

按队列式分支限界法求解单源最短路径的算法：

SSShortestPaths(v)

{ E.i=v;

E.length=0;

dist[v]=0; //源点V到源点V的最近距离

INSERT (Q, E); //Q是一个队列

while(!Empty(Q))

{ E=DELETE(Q);

if(dist[E.i]for(j=1; j<=n; j++)

if ((c[E.i][j]{ dist[j]=E.length+c[E.i][j];

prev[j]=E.i;

N.i=j;

N.length=dist[j];

INSERT(Q,N);

}

}

}

7.按优先队列式分支限界法求解单源最短路径的算法：

template

void graph :: ShortestPaths(int v)

{MinHeap > H(1000); //小根堆的容量为1000

MinHeapNode E;

E.i=v; E.length=0; dist[v]=0; //定义源为初始扩展结点

//搜索问题的解空间

while(true)

{ if(dist[E.i]>E.length)

for(j=1; j<=n; j++)

if ((c[E.i][j]{ dist[j]=E.length+c[E.i][j]; prev[j]=E.i;

MinHeapNode N;

N.i=j; N.length=dist[j];

H.Insert(N);

}

try { H.DeleteMin(E);} //从优先队列取下一个扩展结点

catch (OutOfBounds) {break;} // 优先队列空

}

}

8.求解多段图最短路径

(1) 按队列式分支限界法求解多段图最短路径的算法：

ShortestPath(v)

{ Bound=inf; //也可用贪心法先确定一个初始界限

E.i=v; E.length=0;

(Q, E); //Q是队列

while(!Empty(Q))

{ E=DELETE(Q);

if(Boundfor (j=1; j<=n; j++)

{ if ((c[E.i][j]&& (E.length+c[E.i][j]< dist[j]))

{ dist[j]= E.length+c[E.i][j]; prev[j]=E.i;

if（j是终点）

{Bound=E.length+c[E.i][j]; }

else

{N.i=j;

N.length= E.length+c[E.i][j];

INSERT(Q,N);

}

} }}

9.按优先队列式分支限界法求解多段图问题的算法：

template

void graph :: ShortestPath(int v)

{MinHeap > H(1000); //定义小根堆容量为1000

MinHeapNode E;

E.i=v; E.length=0; //定义源为初始扩展结点

Bound=inf; //开始搜索问题的解空间

while(true)

{ if(E.lengthfor(j=1; j<=n; j++)

if ((c[E.i][j]&& (E.length+c[E.i][j]< dist[j]))

{ prev[j]=E.i;

if（j是终点）

{Bound=E.length+c[E.i][j]；continue; }

MinHeapNode N;

N.i=j; N.length= E.length+c[E.i][j];

H.Insert(N);

}

try { H.DeleteMin(E);} //从优先队列取下一个扩展结点

catch (OutOfBound) {break;} // 优先队列空

}

}