下载文档原格式
售货员问题的分支限界算法设计售货员问题（Traveling Salesman Problem，TSP）是一个经典的组合优化问题，其目标是找到一条最短的路径，让售货员访问每个城市一次并回到起始城市。
分支限界算法是一种常用于解决组合优化问题的方法之一，可以用于 TSP。
以下是一个简单的分支限界算法设计框架：问题定义：将售货员问题明确定义为一个具体的数学模型，包括城市之间的距离矩阵等。
状态空间树的构建：将问题表示为状态空间树，其中每个节点代表问题的一个可能状态，每个边代表状态之间的转移。
起始节点对应于售货员的起始城市。
界的计算：在每个节点上计算一个上界（可行解的上界）和一个下界（最优解的下界）。
这些界用于指导搜索。
搜索过程：使用深度优先搜索或广度优先搜索策略，通过分支和界的计算逐步构建状态空间树，直到找到最优解或搜索完整个状态空间。
分支操作：在每个节点上，生成所有可能的分支（城市的排列顺序），并计算每个分支的成本。
剪枝操作：对于某些分支，如果它们的成本已经超过已知的最优解，可以剪枝，减少搜索空间。
更新最优解：在搜索过程中，不断更新已知的最优解。
终止条件：当搜索到达树的叶子节点时，或者当已知的最优解不再被更新时，算法终止。
下面是一个简单的伪代码示例，演示了 TSP 的分支限界算法：function traveling_salesman(node, cost):if is_leaf(node):update_best_solution(cost)else:for each branch in generate_branches(node):if cost_of(branch) < current_best_solution_cost:traveling_salesman(branch, cost + cost_of(branch))在这个伪代码中，generate_branches 生成当前节点的所有可能分支，is_leaf 判断节点是否是叶子节点，cost_of(branch) 计算分支的成本。
算法分析与设计实验报告第七次实验姓名学号班级时间12.26上午地点工训楼309实验名称分支限界法实验(单源最短路径)实验目的1.掌握并运用分支限界法的基本思想2.运用分支限界法实现单源最短路径问题实验原理问题描述：在下图所给的有向图G中，每一边都有一个非负边权。
要求图G的从源顶点s 到目标顶点t之间的最短路径。
基本思想：下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。
其中，每一个结点旁边的数字表示该结点所对应的当前路长。
为了加速搜索的进程，应采用有效地方式选择活结点进行扩展。
按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。
catch (int){break;}if(H.currentsize==0) //优先队列空{break;}}}上述有向图的结果：测试结果附录：完整代码（分支限界法）Shorest_path.cpp//单源最短路径问题分支限界法求解#include<iostream>#include<time.h>#include<iomanip>#include"MinHeap2.h"using namespace std;template<class Type>class Graph //定义图类{friend int main();public:void shortest_path(int); private:int n, //图的顶点数*prev; //前驱顶点数组Type **c, //图的邻接矩阵*dist; //最短距离数组};template<class Type>class MinHeapNode //最小堆中的元素类型为MinHeapNode{friend Graph<Type>;public:operator int() const{return length;}private:int i; //顶点编号Type length; //当前路长};//单源最短路径问题的优先队列式分支限界法template<class Type>void Graph<Type>::shortest_path(int v){MinHeap<MinHeapNode<Type>> H(1000);//定义最小堆的容量为1000//定义源为初始扩展结点MinHeapNode<Type> E;//初始化源结点E.i=v;E.length=0;dist[v]=0;while(true)//搜索问题的解空间{for(int j=1;j<=n;j++)if((c[E.i][j]!=0)&&(E.length+c[E.i][j]<dist[j])){//顶点i到顶点j可达，且满足控制约束//顶点i和j之间有边，且此路径小于原先从源点i到j的路径长度dist[j]=E.length+c[E.i][j];//更新dist数组prev[j]=E.i;//加入活结点优先队列MinHeapNode<Type> N;N.i=j;N.length=dist[j];H.Insert(N);//插入到最小堆中}try{H.DeleteMin(E); // 取下一扩展结点}catch (int){break;}if(H.currentsize==0)//优先队列空{break;}}}int main(){int n=11;int prev[12]={0,0,0,0,0,0,0,0,0,0,0,0};//初始化前驱顶点数组intdist[12]={1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000 };//初始化最短距离数组cout<<"单源图的邻接矩阵如下："<<endl;int **c=new int*[n+1];for(int i=1;i<=n;i++) //输入图的邻接矩阵{c[i]=new int[n+1];for(int j=1;j<=n;j++){cin>>c[i][j];}}int v=1; //源结点为1Graph<int> G;G.n=n;G.c=c;G.dist=dist;G.prev=prev;clock_t start,end,over; //计算程序运行时间的算法start=clock();end=clock();over=end-start;start=clock();G.shortest_path(v);//调用图的最短路径查找算法//输出从源结点到目的结点的最短路径cout<<"从S到T的最短路长是："<<dist[11]<<endl;for(int i=2;i<=n;i++)//输出每个结点的前驱结点{cout<<"prev("<<i<<")="<<prev[i]<<" "<<endl;}for(int i=2;i<=n;i++) //输出从源结点到其他结点的最短路径长度{cout<<"从1到"<<i<<"的最短路长是："<<dist[i]<<endl;}for(int i=1;i<=n;i++) //删除动态分配时的内存{delete[] c[i];}delete[] c;c=0;end=clock();printf("The time is %6.3f",(double)(end-start-over)/CLK_TCK); //显示运行时间cout<<endl;system("pause");return 0;}MinHeap.h#include<iostream>template<class Type>class Graph;template<class T>class MinHeap //最小堆类{template<class Type>friend class Graph;public:MinHeap(int maxheapsize=10); //构造函数，堆的大小是10~MinHeap(){delete[] heap;} //最小堆的析构函数int Size() const{return currentsize;} //Size()返回最小堆的个数T Max(){if(currentsize) return heap[1];} //第一个元素出堆MinHeap<T>& Insert(const T& x); //最小堆的插入函数MinHeap<T>& DeleteMin(T& x); //最小堆的删除函数void Initialize(T x[],int size,int ArraySize); //堆的初始化void Deactivate();void output(T a[],int n);private:int currentsize,maxsize;T *heap;};template<class T>void MinHeap<T>::output(T a[],int n) //输出函数，输出a[]数组的元素{for(int i=1;i<=n;i++)cout<<a[i]<<" ";cout<<endl;}template<class T>MinHeap<T>::MinHeap(int maxheapsize){maxsize=maxheapsize;heap=new T[maxsize+1]; //创建堆currentsize=0;}template<class T>MinHeap<T>& MinHeap<T>::Insert(const T& x){if(currentsize==maxsize) //如果堆中的元素已经等于堆的最大大小return *this; //那么不能在加入元素进入堆中int i= ++currentsize;while(i!=1 && x<heap[i/2]){heap[i]=heap[i/2];i/=2;}heap[i]=x;return *this;}template<class T>MinHeap<T>& MinHeap<T>::DeleteMin(T& x) //删除堆顶元素{if(currentsize==0){cout<<"Empty heap!"<<endl;return *this;}x=heap[1];T y=heap[currentsize--];int i=1,ci=2;while(ci<=currentsize){if(ci<currentsize && heap[ci]>heap[ci+1])ci++;if(y<=heap[ci])break;heap[i]=heap[ci];i=ci;ci*=2;}heap[i]=y;return *this;}template<class T>void MinHeap<T>::Initialize(T x[],int size,int ArraySize) //堆的初始化{delete[] heap;heap=x;currentsize=size;maxsize=ArraySize;for(int i=currentsize/2;i>=1;i--){T y=heap[i];int c=2*i;while(c<=currentsize){if(c<currentsize && heap[c]>heap[c+1])c++;if(y<=heap[c])break;heap[c/2]=heap[c];c*=2;}heap[c/2]=y;}}template<class T>void MinHeap<T>::Deactivate(){heap=0; }。
布线问题：如图1所示，印刷电路板将布线区域划分成n*m个方格。
精确的电路布线问题要求确定连接方格a的中点到b的中点的最短布线方案。
在布线时，电路只能沿直线或直角布线，如图1所示。
为了避免线路相交，已经布线的方格做了封锁标记（如图1中阴影部分），其他线路不允许穿过被封锁的方格。
3 问题的算法选择题目的要求是找到最短的布线方案，从图1的情况看，可以用贪婪算法解决问题，也就是从a开始朝着b的方向垂直布线即可。
实际上，再看一下图2，就知道贪婪算法策略是行不通的。
因为已布线的放个没有规律的所以直观上说只能用搜索方法去找问题的解。
根据布线方法的要求，除边界或已布线处，每个E-结点分支扩充的方向有4个：上、下、左、右，也就是说，一个E-结点扩充后最多产生4个活结点。
以图2的情况为例，图的搜索过程如图3所示。
搜索以a为第一个E-结点，以后不断扩充新的活结点，直到b结束（当然反之也可以）。
反过来从b到a，按序号8-7-6-5-4-3-2-1就可以找到最短的布线方案。
从图3中也可以发现最短的布线方案是不唯一的。
且由此可以看出，此问题适合用分支限界搜索。
#include <stdio.h>#include <stdlib.h>typedef struct Position{int row;int col;}Position;typedef struct team{int x;int y;struct team *next;}team,*TEAM;Position start,end,path[100];TEAM team_l=NULL;int a[100][100];int m,n,path_len;void output(){int i,j;printf("\n|-------------------布线区域图-------------------|\n");for(i=0;i<m+2;i++){for(j=0;j<n+2;j++){printf("%5d",a[i][j]);}printf("\n");}printf("|------------------------------------------------|\n");return;}void input_data(){char yes;int x,y;printf("创建布线区域...\n\n");printf("请输入区域大小(行列的个数): ");scanf("%d,%d",&m,&n);printf("请输入开始点坐标(x,y): ");scanf("%d,%d",&start.row,&start.col);printf("请输入结束点坐标(x,y): ");scanf("%d,%d",&end.row,&end.col);printf("区域内是否有被占用点? (y/n) ");fflush(stdin);scanf("%c",&yes);fflush(stdin);while(yes=='y'){printf("请输入占用点的坐标(x,y): ");scanf("%d,%d",&x,&y);fflush(stdin);if(x<0 || x>m+1 || y<0 || y>n+1 || (x==start.row && y==start.col) || (x==end.row && y==end.col)){printf("输入错误,请重新输入\n");continue;}else{a[x][y]=-1;}printf("是否还有被占用点? (y/n) ");scanf("%c",&yes);fflush(stdin);}for(x=0;x<m+2;x++){a[0][x]=-1;a[m+1][x]=-1;}for(x=0;x<n+2;x++){a[x][0]=-1;a[x][n+1]=-1;}return;}void inq(Position p){TEAM t,q;q=team_l;t=(TEAM)malloc(sizeof(TEAM));t->x=p.row;t->y=p.col;t->next=NULL;if(team_l==NULL){team_l=t;return ;}while(q->next!=NULL){q=q->next;}q->next=t;return;}Position outq(){Position out;out.row=team_l->x;out.col=team_l->y;team_l=team_l->next;return out;}void find_path(){Position offset[4];Position here={start.row,start.col};Position nbr={0,0};int num_of_nbrs=4;int i,j;offset[0].row=0;offset[0].col=1; //右offset[1].row=1;offset[1].col=0; //下offset[2].row=0;offset[2].col=-1;//左offset[3].row=-1;offset[3].col=0;//上printf("\n开始搜索路径...\n");if((start.row == end.row)&&(start.col == end.col)){ path_len = 0;return;}while(1){for(i=0;i<num_of_nbrs;i++){nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(a[nbr.row][nbr.col]==0){a[nbr.row][nbr.col]=a[here.row][here.col] + 1;if((nbr.row == end.row) && (nbr.col == end.col)) break;inq(nbr); //nbr入队}}//是否到达目标位置finishif((nbr.row == end.row) && (nbr.col == end.col)) break;//或节点队列是否为空if(team_l==NULL){printf("\n没有结果\n");return ;}here=outq();}path_len=a[end.row][end.col];here=end;for(j=path_len-1;j>=0;j--){path[j] = here;for(i = 0;i < num_of_nbrs;i++){nbr.row = here.row + offset[i].row;nbr.col = here.col + offset[i].col;if(a[nbr.row][nbr.col] == j) //+ 2)break;}here=nbr;}return;}void out_path(){int i;printf("\n路径为:\n");printf("(%d,%d) ",start.row,start.col);for(i=0;i<path_len;i++){printf("(%d,%d) ",path[i].row,path[i].col);}printf("\n");return;}void main(){input_data();output();find_path();out_path();output(); }。
算法——分⽀限界法（装载问题）对⽐回溯法回溯法的求解⽬标是找出解空间中满⾜约束条件的所有解，想必之下，分⽀限界法的求解⽬标则是找出满⾜约束条件的⼀个解，或是满⾜约束条件的解中找出使某⼀⽬标函数值达到极⼤或极⼩的解，即在某种意义下的最优解。
另外还有⼀个⾮常⼤的不同点就是，回溯法以深度优先的⽅式搜索解空间，⽽分⽀界限法则以⼴度优先的⽅式或以最⼩耗费优先的⽅式搜索解空间。
分⽀限界法的搜索策略在当前节点（扩展节点）处，先⽣成其所有的⼉⼦节点（分⽀），然后再从当前的活节点（当前节点的⼦节点）表中选择下⼀个扩展节点。
为了有效地选择下⼀个扩展节点，加速搜索的进程，在每⼀个活节点处，计算⼀个函数值（限界），并根据函数值，从当前活节点表中选择⼀个最有利的节点作为扩展节点，使搜索朝着解空间上有最优解的分⽀推进，以便尽快地找出⼀个最优解。
分⽀限界法解决了⼤量离散最优化的问题。
选择⽅法1.队列式（FIFO）分⽀限界法队列式分⽀限界法将活节点表组织成⼀个队列，并将队列的先进先出原则选取下⼀个节点为当前扩展节点。
2.优先队列式分⽀限界法优先队列式分⽀限界法将活节点表组织成⼀个优先队列，并将优先队列中规定的节点优先级选取优先级最⾼的下⼀个节点成为当前扩展节点。
如果选择这种选择⽅式，往往将数据排成最⼤堆或者最⼩堆来实现。
例⼦：装载问题有⼀批共n个集装箱要装上2艘载重量分别为c1，c2的轮船，其中集装箱i的重量为wi，且要求确定是否有⼀个合理的装载⽅案可将这n个集装箱装上这2艘轮船。
可证明，采⽤如下策略可以得到⼀个最优装载⽅案：先尽可能的将第⼀艘船装满，其次将剩余的集装箱装到第⼆艘船上。
代码如下：//分⽀限界法解装载问题//⼦函数，将当前活节点加⼊队列template<class Type>void EnQueue(Queue<Type> &Q, Type wt, Type &bestw, int i, int n){if(i == n) //可⾏叶结点{if(wt>bestw) bestw = wt ;}else Q.Add(wt) ; //⾮叶结点}//装载问题先尽量将第⼀艘船装满//队列式分⽀限界法，返回最优载重量template<class Type>Type MaxLoading(Type w[],Type c,int n){//初始化数据Queue<Type> Q; //保存活节点的队列Q.Add(-1); //-1的标志是标识分层int i=1; //i表⽰当前扩展节点所在的层数Type Ew=0; //Ew表⽰当前扩展节点的重量Type bestw=0; //bestw表⽰当前最优载重量//搜索⼦集空间树while(true){if(Ew+w[i]<=c) //检查左⼉⼦EnQueue(Q,Ew+w[i],bestw,i,n); //将左⼉⼦添加到队列//将右⼉⼦添加到队列即表⽰不将当前货物装载在第⼀艘船EnQueue(Q,Ew,bestw,i,n);Q.Delete(Ew); //取下⼀个节点为扩展节点并将重量保存在Ewif(Ew==-1) //检查是否到了同层结束{if(Q.IsEmpty()) return bestw; //遍历完毕，返回最优值Q.Add(-1); //添加分层标志Q.Delete(Ew); //删除分层标志，进⼊下⼀层i++;}}}算法MaxLoading的计算时间和空间复杂度为O(2^n).上述算法可以改进，设r为剩余集装箱的重量，当Ew+r<=bestw的时候，可以将右⼦树剪去。
0034算法笔记——【分⽀限界法】最优装载问题问题描述有⼀批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且装载问题要求确定是否有⼀个合理的装载⽅案可将这个集装箱装上这2艘轮船。
如果有，找出⼀种装载⽅案。
容易证明：如果⼀个给定装载问题有解，则采⽤下⾯的策略可得到最优装载⽅案。
(1)⾸先将第⼀艘轮船尽可能装满；(2)将剩余的集装箱装上第⼆艘轮船。
1、队列式分⽀限界法求解在算法的循环体中，⾸先检测当前扩展结点的左⼉⼦结点是否为可⾏结点。
如果是则将其加⼊到活结点队列中。
然后将其右⼉⼦结点加⼊到活结点队列中(右⼉⼦结点⼀定是可⾏结点)。
2个⼉⼦结点都产⽣后，当前扩展结点被舍弃。
活结点队列中的队⾸元素被取出作为当前扩展结点，由于队列中每⼀层结点之后都有⼀个尾部标记-1，故在取队⾸元素时，活结点队列⼀定不空。
当取出的元素是-1时，再判断当前队列是否为空。
如果队列⾮空，则将尾部标记-1加⼊活结点队列，算法开始处理下⼀层的活结点。
节点的左⼦树表⽰将此集装箱装上船，右⼦树表⽰不将此集装箱装上船。
设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。
则当ew+r为了在算法结束后能⽅便地构造出与最优值相应的最优解，算法必须存储相应⼦集树中从活结点到根结点的路径。
为此⽬的，可在每个结点处设置指向其⽗结点的指针，并设置左、右⼉⼦标志。
找到最优值后，可以根据parent回溯到根节点，找到最优解。
算法具体代码实现如下：1、Queue.h[cpp]view plain copy1.#include/doc/951702836.htmling namespace std;3.4.template5.class Queue6.{7.public:8. Queue(int MaxQueueSize=50);9. ~Queue(){delete [] queue;}10.bool IsEmpty()const{return front==rear;}11.bool IsFull(){return ( ( (rear+1) %MaxSize==front )?1:0);}12. T Top() const;13. T Last() const;14. Queue& Add(const T& x);15. Queue& AddLeft(const T& x);16. Queue& Delete(T &x);17.void Output(ostream& out)const;18.int Length(){return (rear-front);}19.private:20.int front;21.int rear;22.int MaxSize;23. T *queue;24.};25.26.template27.Queue::Queue(int MaxQueueSize)28.{29. MaxSize=MaxQueueSize+1;30. queue=new T[MaxSize];31. front=rear=0;32.}33.34.template35.T Queue::Top()const36.{37.if(IsEmpty())38. {39. cout<<"queue:no element,no!"<40.return 0;41. }42.else return queue[(front+1) % MaxSize];43.}44.45.template46.T Queue ::Last()const47.{48.if(IsEmpty())49. {50. cout<<"queue:no element"<51.return 0;52. }53.else return queue[rear];54.}55.56.template57.Queue& Queue::Add(const T& x)58.{59.if(IsFull())cout<<"queue:no memory"<60.else61. {62. rear=(rear+1)% MaxSize;63. queue[rear]=x;64. }65.return *this;66.}67.68.template69.Queue& Queue::AddLeft(const T& x)70.{71.if(IsFull())cout<<"queue:no memory"<72.else73. {74. front=(front+MaxSize-1)% MaxSize;75. queue[(front+1)% MaxSize]=x;76. }77.return *this;78.}79.80.template81.Queue& Queue ::Delete(T & x)82.{83.if(IsEmpty())cout<<"queue:no element(delete)"<84.else85. {86. front=(front+1) % MaxSize;87. x=queue[front];88. }89.return *this;90.}91.92.93.template94.void Queue ::Output(ostream& out)const95.{96.for(int i=rear%MaxSize;i>=(front+1)%MaxSize;i--)97. out<98.}99.100.template101.ostream& operator << (ostream& out,const Queue& x) 102.{x.Output(out);return out;} 2、6d3-1.cpp[cpp]view plain copy1.//装载问题队列式分⽀限界法求解2.#include "stdafx.h"3.#include "Queue.h"4.#include/doc/951702836.htmling namespace std;6.7.const int N = 4;8.9.template10.class QNode11.{12.template13.friend void EnQueue(Queue*>&Q,Type wt,int i,int n,Type bestw,QNode*E,QNode *&bestE,int bestx[],bool ch);14.15.template16.friend Type MaxLoading(Type w[],Type c,int n,int bestx[]);17.18.private:19. QNode *parent; //指向⽗节点的指针20.bool LChild; //左⼉⼦标识21. Type weight; //节点所相应的载重量22.};23.24.template25.void EnQueue(Queue*>&Q,Type wt,int i,int n,Type bestw,QNode >*E,QNode *&bestE,int bestx[],bool ch);26.27.template28.Type MaxLoading(Type w[],Type c,int n,int bestx[]);29.30.int main()31.{32.float c = 70;33.float w[] = {0,20,10,26,15};//下标从1开始34.int x[N+1];35.float bestw;36.37. cout<<"轮船载重为："<38. cout<<"待装物品的重量分别为："<39.for(int i=1; i<=N; i++)40. {41. cout<42. }43. cout<44. bestw = MaxLoading(w,c,N,x);45.46. cout<<"分⽀限界选择结果为:"<47.for(int i=1; i<=4; i++)48. {49. cout<50. }51. cout<52. cout<<"最优装载重量为："<53.54.return 0;55.}56.57.//将活节点加⼊到活节点队列Q中58.template59.void EnQueue(Queue*>&Q,Type wt,int i,int n,Type bestw,QNode >*E,QNode *&bestE,int bestx[],bool ch)60.{61.if(i == n)//可⾏叶节点62. {63.if(wt == bestw)64. {65.//当前最优装载重量66. bestE = E;67. bestx[n] = ch;68. }69.return;70. }71.//⾮叶节点72. QNode *b;73. b = new QNode;74. b->weight = wt;75. b->parent = E;76. b->LChild = ch;77. Q.Add(b);78.}79.80.template81.Type MaxLoading(Type w[],Type c,int n,int bestx[])82.{//队列式分⽀限界法，返回最优装载重量，bestx返回最优解83.//初始化84. Queue*> Q; //活节点队列85. Q.Add(0); //同层节点尾部标识86.int i = 1; //当前扩展节点所处的层87. Type Ew = 0, //扩展节点所相应的载重量88. bestw = 0, //当前最优装载重量89. r = 0; //剩余集装箱重量90.91.for(int j=2; j<=n; j++)92. {93. r += w[j];94. }95.96. QNode *E = 0, //当前扩展节点97. *bestE; //当前最优扩展节点98.99.//搜索⼦集空间树100.while(true)101. {102.//检查左⼉⼦节点103. Type wt = Ew + w[i];104.if(wt <= c)//可⾏节点105. {106.if(wt>bestw)107. {108. bestw = wt;109. }110. EnQueue(Q,wt,i,n,bestw,E,bestE,bestx,true); 111. } 112.113.//检查右⼉⼦节点114.if(Ew+r>bestw)115. {116. EnQueue(Q,Ew,i,n,bestw,E,bestE,bestx,false); 117. } 118. Q.Delete(E);//取下⼀扩展节点119.120.if(!E)//同层节点尾部121. {122.if(Q.IsEmpty())123. {124.break;125. }126. Q.Add(0); //同层节点尾部标识127. Q.Delete(E); //取下⼀扩展节点128. i++; //进⼊下⼀层129. r-=w[i]; //剩余集装箱重量130. }131. Ew =E->weight; //新扩展节点所对应的载重量132. }133.134.//构造当前最优解135.for(int j=n-1; j>0; j--)136. {137. bestx[j] = bestE->LChild;138. bestE = bestE->parent;139. }140.return bestw;141.}程序运⾏结果如图：2、优先队列式分⽀限界法求解解装载问题的优先队列式分⽀限界法⽤最⼤优先队列存储活结点表。
实验七分支限界法（2学时）一、实验目的与要求1、掌握旅行商售货员问题的分支限界算法；2、区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。
二、实验题：某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。
他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。
三、实验提示旅行商问题的解空间是一个排列树。
有两种实现的方法。
第一种是只使用一个优先队列，队列中的每个元素中都包含到达根的路径。
另一种是保留一个部分解空间树和一个优先队列，优先队列中的元素并不包含到达根的路径。
以下为第一种方法。
由于我们要寻找的是最小耗费的旅行路径，因此可以使用最小耗费分枝定界法。
在实现过程中，使用一个最小优先队列来记录活节点，队列中每个节点的类型为MinHeapNode。
每个节点包括如下区域： x（从1到n的整数排列，其中x[0] = 1 ），s（一个整数，使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x[0:s], 而剩余待访问的节点是x [s + 1 : n - 1 ]），cc（旅行路径前缀，即解空间树中从根节点到当前节点的耗费），lcost（该节点子树中任意叶节点中的最小耗费）， rcost（从顶点x[s : n - 1]出发的所有边的最小耗费之和）。
当类型为MinHeapNode( T )的数据被转换成为类型T时，其结果即为lcost的值。
分枝定界算法的代码见程序程序首先生成一个容量为100的最小堆，用来表示活节点的最小优先队列。
活节点按lcost 值从最小堆中取出。
接下来，计算有向图中从每个顶点出发的边中耗费最小的边所具有的耗费MinOut。
如果某些顶点没有出边，则有向图中没有旅行路径，搜索终止。
如果所有的顶点都有出边，则可以启动最小耗费分枝定界搜索。
根的孩子B作为第一个E-节点，在此节点上，所生成的旅行路径前缀只有一个顶点1，因此s=0, x[0]=1, x[1:n-1]是剩余的顶点（即顶点2 ， 3 ，.， n ）。
