算法设计与分析 课件 8.4-分支限界 - 典型应用 - 旅行售货员问题.pptx

算法设计与分析

分支限界—旅行售货员问题;问题描述：某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使得总的路程（或总旅费）最小。

问题抽象：设G=(V,E)是一个带权图。

图中各边的权值为正数。图中一条周游路线是包括V中每个顶点在内的一条回路。周游路线的费用是这条回路上所有边的权值之和。旅行售货员问题就是要在图G中找出费用最小的回路。;实例分析：

优先队列：

小根堆，用于表示活结点优先队列

优先级=下界lcost

lcost=cc+顶点的最小费用出边和(未来最小的花费);;;输入：图结点数n，图邻接矩阵a[][]

输出：最优值bestc，最优解v[]

1BBTSP(){

2若图中存在没有出边的结点，则退出;

3计算各顶点最小出边和MinSum;

4定义最优值bestc=∞;

5创建根结点E,令其s=0,cc=0,lcost=cc+MinSum,

6x={1,2,…,n};

7while(E不是叶结点){//遇到叶子时结束

8if(E是叶子的父结点){//E的层次为n-2

9c=E-cc+a[E-x[n-2]][E-x[n-1]]+

10a[E-x[n-1]][1];

11if(cbestc){

12bestc=c;改造E为扩展的叶结点,

13E-s++,E-cc=bestc;E入队;

14}

15else释放E;

16};17else{//扩展E的儿子结点

18for(i=E-s+1;i=n-1;i++){

19cc=E-cc+a[E-x[E-s]][E-x[i]];

20lcost=cc+E-lcost-MinOut[E-x[E-s]];

21if(lcostbestc){

22申请结点N;把E中x复制到N;

23N-s=E-s+1;交换N-x[N-s]与N-x[i];

24N-cc=cc;N-lcost=lcost;

25N入队;}

26}

27释放E;

28}

29从队列取下一个扩展结点E;

30if(E不存在)break;

31}

32if(bestc==∞)return∞;//无回路

33从E中复制x到解v中；

34释放E及优先队列中剩余结点;

35returnbestc;};