旅行商售货员问题的分支限界算法

《旅行商售货员问题的分支限界算法》由会员分享，可在线阅读，更多相关《旅行商售货员问题的分支限界算法（10页珍藏版）》请在装配图网上搜索。

1、旅行商售货员问题的分支限界算法姓名： 陈宇博 学号：105135一、实验目的与要求1、掌握旅行商售货员问题的分支限界算法；2、区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。二、实验题：编程实现：某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。三、实验提示旅行商问题的解空间是一个排列树。有两种实现的方法。第一种是只使用一个优先队列，队列中的每个元素 中都包含到达根的路径。另一种是保留一个部分解空间树和一个优先队列，优先队列中 的元素并不包含到达根的路径。以下为第一种方法。 由于我

2、们要寻找的是最小耗费的旅行路径，因此可以使用最小耗费分枝定界法。在实现过程中，使用一个最小优先队列来记录活节点，队列中每个节点的类型为MinHeapNode。每个节点包括如下区域： x（从1到n的整数排列，其中x0 = 1 ），s（一个整数，使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x0:s, 而剩余待访问的节点是x s + 1 : n - 1 ），cc（旅行路径前缀，即解空间树中从根节点到当前节点的耗费），lcost（该节点子树中任意叶节点中的最小耗费）， rcost（从顶点xs : n - 1出发的所有边的最小耗费之和）。当类型为MinHeapNode( T )的数据被转换成

3、为类型T时，其结果即为lcost的值。代码：#include <stdio.h> #include <istream> using namespace std; /-宏定义- #define MAX_CITY_NUMBER 10 /城市最大数目 #define MAX_COST 10000000 /两个城市之间费用的最大值 /-全局变量- int City_GraphMAX_CITY_NUMBERMAX_CITY_NUMBER; /表示城市间边权重的数组 int City_Size; /表示实际输入的城市数目 int Best_Cost; /最小费用 int Best_

4、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 MiniHeap Node* pHead; /堆的头 MiniHeap; /初始化 void Init

5、MiniHeap(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; pinnode->lcost = node.lcost; pinno

6、de->pNext = node.pNext; pinnode->rcost = node.rcost; pinnode->s = node.s; pinnode->pNext = NULL; for(int k=0;k<City_Size;k+) pinnode->xk = node.xk; pre = pMiniHeap->pHead; next = pMiniHeap->pHead->pNext; if(next = NULL) pMiniHeap->pHead->pNext = pinnode; else while(n

7、ext != NULL) if(next->lcost) > (pinnode->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

8、->pNext != NULL) pnode = pMiniHeap->pHead->pNext; pMiniHeap->pHead->pNext = 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; /保存每个结点的最小出边的索

9、引 MiniHeap* heap = new MiniHeap; /分配堆 InitMiniHeap(heap); /初始化堆 miniSum = 0; for (i=0;i<City_Size;i+) miniOuti = MAX_COST; /初始化时每一个结点都不可达 for(j=0;j<City_Size;j+) if (City_Graphij>0 && City_Graphij<miniOuti) /从i到j可达，且更小 miniOuti = City_Graphij; if (miniOuti = MAX_COST)/ i 城市没有出边 B

10、est_Cost = -1; return ; miniSum += miniOuti; for(i=0;i<City_Size;i+) /初始化的最优路径就是把所有结点依次走一遍 Best_Cost_Pathi = i; Best_Cost = MAX_COST; /初始化的最优费用是一个很大的数 pNode = new Node; /初始化第一个结点并入堆 pNode->lcost = 0; /当前结点的优先权为0 也就是最优 pNode->cc = 0; /当前费用为0（还没有开始旅行） pNode->rcost = miniSum; /剩余所有结点的最小出边费用

11、和就是初始化的miniSum pNode->s = 0; /层次为0 pNode->pNext = NULL; for(int k=0;k<City_Size;k+) pNode->xk = Best_Cost_Pathk; /第一个结点所保存的路径也就是初始化的路径 put(heap,*pNode); /入堆 while(pNode != NULL && (pNode->s) < City_Size-1) /堆不空 不是叶子 for(int k=0;k<City_Size;k+) Best_Cost_Pathk = pNode->

12、;xk ; /将最优路径置换为当前结点本身所保存的 /* * * pNode 结点保存的路径中的含有这条路径上所有结点的索引 * * x路径中保存的这一层结点的编号就是xCity_Size-2 * * 下一层结点的编号就是xCity_Size-1 */ 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;

13、 if(edge1 >= 0 && edge2 >= 0 && (pNode->cc+edge1+edge2) < Best_Cost) /edge1 -1 表示不可达 /叶子可达起点费用更低 Best_Cost = pNode->cc + edge1+edge2; pNode->cc = Best_Cost; pNode->lcost = Best_Cost; /优先权为 Best_Cost pNode->s+; /到达叶子层 else /内部结点 for (i=pNode->s;i<City_Siz

14、e;i+) /从当前层到叶子层 if(City_GraphpNode->xpNode->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_r

15、cost<Best_Cost) /下一个结点的最小出边费用和小于当前的最优解，说明可能存在更优解 for (j=0;j<City_Size;j+) /完全copy路径，以便下面修改 temp_xj=Best_Cost_Pathj; temp_xpNode->xpNode->s+1 = Best_Cost_Pathi; /将当前结点的编号放入路径的深度为s+1的地方 temp_xi = Best_Cost_PathpNode->s+1; /? /将原路/径中的深度为s+1的结点编号放入当前路径的 /相当于将原路径中的的深度为i的结点与深度W为s+1的结点交换 Nod

16、e* 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;k<City_Size;k+) pNextNode->xk = temp_xk; put(heap,*pNextNode); delete pNextNode; pNode = Rem

17、oveMiniHeap(heap); int main() int i,j;printf("请输入旅行的节点数"); scanf("%d",&City_Size); for(i=0;i<City_Size;i+) printf("请分别输入每个节点与其它节点的路程花费"); for(j=0;j<City_Size;j+) scanf("%d",&City_Graphij); Traveler(); printf("最小花费""%dn",Best_C

18、ost); return 1; 运行结果：分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。 由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分

19、支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性

20、产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。有一些问题其实无论用回溯法还是分支限界法都可以得到很好的解决，但是另外一些则不然。n后问题比较适合采用回溯法解决，布线问题比较适合采用分支限界法解决，0-1背包问题既可以采用回溯法也可以采用分支限界法解决。【唯美句子】 走累的时候，我就到升国旗哪里的一角台阶坐下，双手抚膝，再闭眼，让心灵受到阳光的洗涤。懒洋洋的幸福。顶 3 收藏 2【唯美句子】 一个人踮着脚

21、尖，在窄窄的跑道白线上走，走到很远的地方又走回来。阳光很好，温暖，柔和。漫天的安静。顶 7 收藏 7【唯美句子】 清风飘然，秋水缓淌。一丝云起，一片叶落，剔透生命的空灵。轻轻用手触摸，就点碎了河面的脸。落叶舞步婀娜不肯去，是眷恋，是装点？瞬间回眸，点亮了生命精彩。顶 11 收藏 9【唯美句子】 几只从南方归来的燕子，轻盈的飞来飞去，“几处早莺争暖树，谁家新燕啄春泥，”其乐融融的山林气息，与世无争的世外桃源，让人心旷神怡。顶 0 收藏 2【唯美句子】 流年清浅，岁月轮转，或许是冬天太过漫长，当一夜春风吹开万里柳时，心情也似乎开朗了许多，在一个风轻云淡的早晨，踏着初春的阳光，漫步在碧柳垂青的小河边

22、，看小河的流水因为解开了冰冻而欢快的流淌， 清澈见底的的河水，可以数得清河底的鹅软石，偶尔掠过水面的水鸟，让小河荡起一层层的涟漪。河岸换上绿色的新装，刚刚睡醒的各种各样的花花草草，悄悄的露出了嫩芽，这儿一丛，那儿一簇，好像是交头接耳的议论着些什么，又好象是在偷偷地说着悄悄话。顶 3 收藏 4【唯美句子】 喜欢海子写的面朝大海春暖花开，不仅仅是因为我喜欢看海，还喜欢诗人笔下的意境，每当夜深人静时，放一曲纯音乐，品一盏茶，在脑海中搜寻诗中的恬淡闲适。在春暖花开时，身着一身素衣，站在清风拂柳，蝶舞翩跹的百花丛中，轻吹一叶竖笛，放眼碧波万里，海鸥，沙滩，还有扬帆在落日下的古船，在心旷神怡中，做一帘红尘

23、的幽梦。顶 0 收藏 2【唯美句子】 繁华如三千东流水，你只在乎闲云野鹤般的采菊东篱、身心自由，置身置灵魂于旷野，高声吟唱着属于自己的歌，悠悠然永远地成为一个真真正正的淡泊名利、鄙弃功名利禄的隐者。顶 1 收藏 3【唯美句子】 世俗名利和青山绿水之间，你选择了淡泊明志，持竿垂钓碧泉绿潭；权力富贵和草舍茅庐之间，你选择了宁静致远，晓梦翩跹姹紫嫣红。顶 2 收藏 3【唯美句子】 那是一株清香的无名花，我看到了它在春风夏雨中风姿绰约的模样，可突如其来的秋雨，无情的打落了它美丽的花瓣，看着它在空谷中独自凋零，我莫名其妙的心痛，像针椎一样的痛。秋雨，你为何如此残忍，为何不懂得怜香惜玉，我伸出颤抖的双手，

24、将散落在泥土里的花瓣捧在手心。顶 4 收藏 5【唯美句子】 滴答滴答，疏疏落落的秋雨，赶着时间的脚步，哗啦啦的下起来。听着雨水轻轻地敲击着微薄的玻璃窗，不知不觉，我像是被催眠了一样，渐渐的进入了梦乡。顶 3 收藏 5【唯美句子】 在这极致的悲伤里，我看到了世间最美的爱，可谁又能明白，此刻的我是悲伤还是欢喜，也许只有那拨动我心弦的秋季，才知道潜藏在我心中的眼泪。顶 4 收藏 3【唯美句子】 看着此情此景，我细细地聆听。像是听到了落叶的呢喃，秋风的柔软，在这极短的瞬间，他们一起诉说着最美的爱恋，演绎着永恒的痴缠。当落叶安详的躺在大地，露出幸福的模样，你看，它多像一个进入梦乡的孩子。突然发现，秋风并

25、非是想象中的刽子手，原来它只是在叶子生命的最后一刻，让它体会到爱的缠绵，飞翔的滋味。顶 1 收藏 1【唯美句子】 很感谢那些耐心回答我的人，公交上那个姐姐，还有那位大叔，我不知道他们是不是本地人，但我们遇到的一个交警协管，一位头发花白的大姐，她是上海本地人，很和善，并不像有些人说的上海人很排外。事实上，什么都不是绝对的。顶 2 收藏 0【唯美句子】 我嗅到浓郁的香奈尔，却也被那种陌生呛了一鼻。也许，我却不知道，那时的感受了。那里没有那么美好，没有安全感，归属感。我想要的自由呢，不完全地体验到了。顶 2 收藏 1【唯美句子】 那些繁华的都市，车水马龙，灯红酒绿，流光溢彩，却充斥着一种悲哀，浮夸。

26、我看到各种奢华，却也看到各种卑微，我看到友善亲和，也看到暴躁粗鲁，我看到金光熠【优美语句】 踏过一片海，用博识的学问激起片片微澜；采过一丛花，正在聪慧的碰碰外送来缕缕清喷鼻；无过一个梦，决定从那里启程。顶 0 收藏 0【优美语句】 人生如一本书，应该多一些精彩的细节，少一些乏味的字眼；人生如一支歌，应该多一些昂扬的旋律，少一些忧伤的音符；人生如一幅画，应该多一些亮丽的色彩，少一些灰暗的色调。 顶 0 收藏 0【优美语句】 母爱是一滴甘露，亲吻干涸的泥土，它用细雨的温情，用钻石的坚毅，期待着闪着碎光的泥土的肥沃；母爱不是人生中的一个凝固点，而是一条流动的河，这条河造就了我们生命中美丽的情感之景。

27、 顶 0 收藏 0【优美语句】 生活如海，宽容作舟，泛舟于海，方知海之宽阔；生活如山，宽容为径，循径登山，方知山之高大；生活如歌，宽容是曲，和曲而歌，方知歌之动听。 顶 0 收藏 0【优美语句】 母爱就是一幅山水画，洗去铅华雕饰，留下清新自然；母爱就象一首深情的歌，婉转悠扬，轻吟浅唱；母爱就是一阵和煦的风，吹去朔雪纷飞，带来春光无限。 顶 0 收藏 0【优美语句】 努力奋斗，天空依旧美丽，梦想仍然纯真，放飞自我，勇敢地飞翔于梦想的天空，相信自己一定做得更好。 顶 0 收藏 0【优美语句】 品味生活，完善人性。存在就是机会，思考才能提高。人需要不断打碎自己，更应该重新组装自己。顶 0 收藏 0【

28、优美语句】 母爱是一缕阳光，让你的心灵即使在寒冷的冬天也能感到温暖如春；母爱是一泓清泉，让你的情感即使蒙上岁月的风尘依然纯洁明净。 顶 0 收藏 0【优美语句】 母爱是温暖心灵的太阳；母爱是滋润心灵的雨露；母爱是灌溉心灵的沃土；母爱是美化心灵的彩虹。 顶 0 收藏 0【优美语句】 一轮金色的光圈印在海面，夕阳将最后的辉煌撒向了大海，海平面波光潋滟，金光闪闪，夕阳下的海水让最后一丝蓝也带着感动。温和的海水轻轻地拍打着我的脚踝，我张开双臂拥抱最温馨的时刻我爱大海宽广的胸怀，无论多大的风浪，她都可以揽入怀中；无论多少风雨，都无法将她击垮；无论多少河流，她都可以容纳；我愿做一只填海的燕，填平她的波涛翻滚，填平她的汹涌愤怒，只留下平静、柔和的海面。