分支限界法实现实验报告

分支限界法实现实验报告

ID:25720461

大小:79.50 KB

页数:9页

时间:2018-11-22

分支限界法实现实验报告_第1页
分支限界法实现实验报告_第2页
分支限界法实现实验报告_第3页
分支限界法实现实验报告_第4页
分支限界法实现实验报告_第5页
资源描述:

《分支限界法实现实验报告》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库

1、xxxxx实验报告课程名称:_算法设计与分析项目名称:_分支限界法实现_姓名:_xxxxx专业:xxxxxxx班级:__xxxxxxx_学号:__xxxxxxxxxxxxxxxxx__同组成员____无_______一、实验准备:实验目的:  掌握分支限界法求解问题的一般特征和步骤。 使用分支限界法编程,求解旅行售货员问题。实验环境准备:WindowsXPMicrosoftC++2008在当前节点(扩展节点)处,先生成其所有的儿子节点(分支),然后再从当前的活节点(当前节点的子节点)表中选择下一个扩展节点。为了有效地选择下一个扩展节点,加速搜索的进程,在每一个活节

2、点处,计算一个函数值(限界),并根据函数值,从当前活节点表中选择一个最有利的节点作为扩展节点,使搜索朝着解空间上有最优解的分支推进,以便尽快地找出一个最优解。分支限界法解决了大量离散最优化的问题。1.队列式(FIFO)分支限界法队列式分支限界法将活节点表组织成一个队列,并将队列的先进先出原则选取下一个节点为当前扩展节点。2.优先队列式分支限界法优先队列式分支限界法将活节点表组织成一个优先队列,并将优先队列中规定的节点优先级选取优先级最高的下一个节点成为当前扩展节点。如果选择这种选择方式,往往将数据排成最大堆或者最小堆来实现。二、实验过程记录:打开MicrosoftC++2008

3、,键入代码进行编程:源代码为:#include#include"stdafx.h"#includeusingnamespacestd;#defineMAX_CITY_NUMBER10#defineMAX_COST10000000intCity_Graph[MAX_CITY_NUMBER][MAX_CITY_NUMBER];intCity_Size;intBest_Cost;intBest_Cost_Path[MAX_CITY_NUMBER];typedefstructNode{intlcost;intcc;intrcost;ints;intx

4、[MAX_CITY_NUMBER];structNode*pNext;}Node;typedefstructMiniHeap{Node*pHead;}MiniHeap;voidInitMiniHeap(MiniHeap*pMiniHeap){pMiniHeap->pHead=newNode;pMiniHeap->pHead->pNext=NULL;}voidput(MiniHeap*pMiniHeap,Nodenode){Node*next;Node*pre;Node*pinnode=newNode;pinnode->cc=node.cc;pinnode->lcost=node

5、.lcost;pinnode->pNext=node.pNext;pinnode->rcost=node.rcost;pinnode->s=node.s;pinnode->pNext=NULL;for(intk=0;kx[k]=node.x[k];}pre=pMiniHeap->pHead;next=pMiniHeap->pHead->pNext;if(next==NULL){pMiniHeap->pHead->pNext=pinnode;}else{while(next!=NULL){if((next->lcost)>(pin

6、node->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=pMiniHeap->pHead->pNext->pNext;}re

7、turnpnode;}voidTraveler(){inti,j;inttemp_x[MAX_CITY_NUMBER];Node*pNode=NULL;intminiSum;intminiOut[MAX_CITY_NUMBER];MiniHeap*heap=newMiniHeap;InitMiniHeap(heap);miniSum=0;for(i=0;i

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。