《分支界限法实现概要》由会员分享，可在线阅读，更多相关《分支界限法实现概要（12页珍藏版）》请在金锄头文库上搜索。
1、实 验 报 告课程名称 算法设计与分析 课题名称 分支限界法实现_ 1.算法（分支限界法实现）2.实验目的： 掌握分支限界法求解问题的一般特征和步骤。 使用分支限界法编程，求解旅行售货员问题。3.过程设计在当前节点（扩展节点）处，先生成其所有的儿子节点（分支），然后再从当前的活节点（当前节点的子节点）表中选择下一个扩展节点。为了有效地选择下一个扩展节点，加速搜索的进程，在每一个活节点处，计算一个函数值（限界），并根据函数值，从当前活节点表中选择一个最有利的节点作为扩展节点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。分支限界法解决了大量离散最优化的问题。1.队列式（FIFO
2、）分支限界法队列式分支限界法将活节点表组织成一个队列，并将队列的先进先出原则选取下一个节点为当前扩展节点。2.优先队列式分支限界法优先队列式分支限界法将活节点表组织成一个优先队列，并将优先队列中规定的节点优先级选取优先级最高的下一个节点成为当前扩展节点。如果选择这种选择方式，往往将数据排成最大堆或者最小堆来实现。一、.源代码：具体算法的实现如下：#include #include stdafx.h#include using namespace std; #define MAX_CITY_NUMBER 10 #define MAX_COST 10000000 int City_GraphMAX
3、_CITY_NUMBERMAX_CITY_NUMBER; int City_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 MiniHeap Node* pHead; MiniHeap; void InitMiniHeap(MiniHeap* pMiniHeap) pMiniHeap-pHead
4、 = new Node; pMiniHeap-pHead-pNext = NULL; void put(MiniHeap* pMiniHeap,Node node) Node* next; Node* pre; Node* pinnode = new Node; pinnode-cc = node.cc; pinnode-lcost = node.lcost; pinnode-pNext = node.pNext; pinnode-rcost = node.rcost; pinnode-s = node.s; pinnode-pNext = NULL; for(int k=0;kxk = no
5、de.xk; pre = pMiniHeap-pHead; next = pMiniHeap-pHead-pNext; if(next = NULL) pMiniHeap-pHead-pNext = pinnode; else while(next != NULL) if(next-lcost) (pinnode-lcost) pinnode-pNext = pre-pNext; pre-pNext = pinnode; break; pre = next; next = next-pNext; pre-pNext = pinnode; Node* RemoveMiniHeap(MiniHea
6、p* pMiniHeap) Node* pnode = NULL; if(pMiniHeap-pHead-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; MiniHeap* heap = new
7、MiniHeap; InitMiniHeap(heap); miniSum = 0; for (i=0;iCity_Size;i+) miniOuti = MAX_COST; for(j=0;j0 & City_GraphijminiOuti) miniOuti = City_Graphij; if (miniOuti = MAX_COST) Best_Cost = -1; return ; miniSum += miniOuti; for(i=0;ilcost = 0; pNode-cc = 0; pNode-rcost = miniSum; pNode-s = 0; pNode-pNext
8、 = NULL; for(int k=0;kxk = Best_Cost_Pathk; put(heap,*pNode); while(pNode != NULL & (pNode-s) City_Size-1) for(int k=0;kxk ; 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 & edge2 = 0 & (pNode-cc+edge1+edge2) cc + edge1+edge2; pNode-cc = Best_Cost; pNode-lcost = Best_Cost; pNode-s+; else for (i=pNode-s;ixpNode-spNode-xi = 0) int temp_cc = pNode-cc+City
