1、实验七 分支限界的应用一基本原理的概括一个具体问题，其解决的方法可能有很多种，可采用各种不同的算法设计方法。二该类算法设计与实现的要点熟练掌握各种算法设计方法三实验目的和要求要求用分支限界以及至少一种其它算法求解旅行商问题，提高综合应用各种算法设计方法的能力。四实验内容（分支限界算法 /-宏定义- #define MAX_CITY_NUMBER 10 /城市最大数目 #define MAX_COST 10000000 /两个城市之间费用的最大值/-全局变量- int City_GraphMAX_CITY_NUMBERMAX_CITY_NUMBER; /表示城市间边权重的数组 int City_
2、Size; /表示实际输入的城市数目 int Best_Cost; /最小费用 int Best_Cost_PathMAX_CITY_NUMBER; /最小费用时的路径 /-定义结点- typedef struct Node int lcost; /优先级 int cc; /当前费用 int rcost; /剩余所有结点的最小出边费用的和 int s; /当前结点的深度，也就是它在解数组中的索引位置 int xMAX_CITY_NUMBER; /当前结点对应的路径 struct Node* pNext; /指向下一个结点 Node; /-定义堆和相关对操作- typedef struct Mi
3、niHeap Node* pHead; /堆的头 MiniHeap; /初始化 void InitMiniHeap(MiniHeap* pMiniHeap) pMiniHeap-pHead = new Node; pMiniHeap-pHead-pNext = NULL; /入堆 void put(MiniHeap* pMiniHeap,Node node) Node* next; Node* pre; Node* pinnode = new Node; /将传进来的结点信息 copy 一份保存 /这样在函数外部对 node 的修改就不会影响到堆了 pinnode-cc = node.cc;
4、pinnode-lcost = node.lcost; pinnode-pNext = node.pNext; pinnode-rcost = node.rcost; pinnode-s = node.s; pinnode-pNext = NULL; for(int k=0;kxk = node.xk; pre = pMiniHeap-pHead; next = pMiniHeap-pHead-pNext; if(next = NULL) pMiniHeap-pHead-pNext = pinnode; else while(next != NULL) if(next-lcost) (pinn
5、ode-lcost) /发现一个优先级大的，则置于其前面 pinnode-pNext = pre-pNext; pre-pNext = pinnode; break; /跳出 pre = next; next = next-pNext; pre-pNext = pinnode; /放在末尾 /出堆 Node* RemoveMiniHeap(MiniHeap* pMiniHeap) Node* pnode = NULL; if(pMiniHeap-pHead-pNext != NULL) pnode = pMiniHeap-pHead-pNext; pMiniHeap-pHead-pNext =
6、 pMiniHeap-pHead-pNext-pNext; return pnode; /-分支限界法找最优解- void Traveler() int i,j; int temp_xMAX_CITY_NUMBER; Node* pNode = NULL; int miniSum; /所有结点最小出边的费用和 int miniOutMAX_CITY_NUMBER; /保存每个结点的最小出边的索引 MiniHeap* heap = new MiniHeap; /分配堆 InitMiniHeap(heap); /初始化堆 miniSum = 0; for (i=0;i0 /当前结点的优先权为 0
7、也就是最优 pNode-cc = 0; /当前费用为 0(还没有开始旅行) pNode-rcost = miniSum; /剩余所有结点的最小出边费用和就是初始化的miniSum pNode-s = 0; /层次为 0 pNode-pNext = NULL; for(int k=0;kxk = Best_Cost_Pathk; /第一个结点所保存的路径也就是初始化的路径 put(heap,*pNode); /入堆 while(pNode != NULL /将最优路径置换为当前结点本身所保存的 /* * * pNode 结点保存的路径中的含有这条路径上所有结点的索引 * * x 路径中保存的这一
8、层结点的编号就是 xCity_Size-2 1 * * 下一层结点的编号就是 xCity_Size-*/ if (pNode-s) = City_Size-2)/是叶子的父亲 int edge1 = City_Graph(pNode-x)City_Size-2(pNode-x)City_Size-1; int edge2 = City_Graph(pNode-x)City_Size-1(pNode-x)0; if(edge1 = 0 pNode-cc = Best_Cost; pNode-lcost = Best_Cost; /优先权为 Best_Cost pNode-s+; /到达叶子层 e
9、lse /内部结点 for (i=pNode-s;ixpNode-spNode-xi = 0) /可达 /pNode 的层数就是它在最优路径中的位置 int temp_cc = pNode-cc+City_GraphpNode-xpNode-spNode-xi; int temp_rcost = pNode-rcost-miniOutpNode-xpNode-s; /下一个结点的剩余最小出边费用和 /等于当前结点的 rcost 减去当前这个结点的最小出边费用 if (temp_cc+temp_rcostxpNode-s+1 = Best_Cost_Pathi; /将当前结点的编号放入路径的深度
10、为 s+1 的地方 temp_xi = Best_Cost_PathpNode-s+1; /? /将原路径中的深度为 s+1 的结点编号放入当前路径的 /相当于将原路径中的的深度为 i 的结点与深度 W 为 s+1 的结点交换 Node* pNextNode = new Node; pNextNode-cc = temp_cc; pNextNode-lcost = temp_cc+temp_rcost; pNextNode-rcost = temp_rcost; pNextNode-s = pNode-s+1; pNextNode-pNext = NULL; for(int k=0;kxk =
11、 temp_xk; put(heap,*pNextNode); delete pNextNode; pNode = RemoveMiniHeap(heap); int main() int i,j; printf(“请输入旅行的节点数“); scanf(“%d“, for(i=0;iusing namespace std;#define n 4int main()int i,j,k,l;int Sn;/用于存储已访问过的城市int Dnn;/用于存储两个城市之间的距离int sum = 0;/用于记算已访问过的城市的最小路径长度int Dtemp;/保证 Dtemp 比任意两个城市之间的距离都
12、大（其实在算法描述中更准确的应为无穷大）int flag;/最为访问的标志，若被访问过则为 1，从未被访问过则为 0/*初始化*/i = 1;/i 是至今已访问过的城市S0 = 0;D01 = 2;D02 = 6;D03 = 5;D10 = 2;D12 = 4;D13 = 4;D20 = 6;D21 = 4;D23 = 2;D30 = 5;D31 = 4;D32 = 2;dok = 1;Dtemp = 10000;dol = 0;flag = 0;doif(Sl = k)/判断该城市是否已被访问过，若被访问过，flag = 1;/则 flag 为 1break;/跳出循环，不参与距离的比较el
13、sel+;while(l i);if(flag = 0/j 用于存储已访问过的城市 kDtemp = DkSi - 1;/Dtemp 用于暂时存储当前最小路径的值k+;while(k n);Si = j;/将已访问过的城市 j 存入到 Si中i+;sum += Dtemp;/求出各城市之间的最短距离，注意：在结束循环时，该旅行商尚未回到原出发的城市while(i n);sum += D0j;/D0j为旅行商所在的最后一个城市与原出发的城市之间的距离for(j = 0; j n; j+) /输出经过的城市的路径coutj“ “;coutS0;cout“n“sum;/求出最短路径的值cout“n“;
