分支限界法实现实验报告(共9页)

1、精选优质文档-倾情为你奉上xxxxx实验报告课程名称： _算法设计与分析 项目名称：_分支限界法实现_ 姓名：_xxxxx专业：xxxxxxx班级：_xxxxxxx_学号：_xxxxxxxxxxxxxxxxx_同组成员_无_一、实验准备：实验目的：   掌握分支限界法求解问题的一般特征和步骤。  使用分支限界法编程，求解旅行售货员问题。实验环境准备：Windows XP Microsoft C+2008在当前节点（扩展节点）处，先生成其所有的儿子节点（分支），然后再从当前的活节点（当前节点的子节点）表中选择下一个扩展节点。为了有效地选择下一个扩展节点，加速搜索的进

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

3、，键入代码进行编程：源代码为：#include <stdio.h> #include "stdafx.h"#include <istream> using namespace std; #define MAX_CITY_NUMBER 10 #define MAX_COST int City_GraphMAX_CITY_NUMBERMAX_CITY_NUMBER; int City_Size; int Best_Cost; int Best_Cost_PathMAX_CITY_NUMBER; typedef struct Node int lcost;

4、 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 = new Node; pMiniHeap->pHead->pNext = NULL; void put(MiniHeap* pMiniHeap,Node node) Node* next; Node* pre; Node*

5、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;k<City_Size;k+) pinnode->xk = node.xk; pre = pMiniHeap->pHead; next = pMiniHeap->pHe

6、ad->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(MiniHeap* pM

7、iniHeap) 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_CIT

8、Y_NUMBER; 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) miniOuti = City_Graphij; if (miniOuti = MAX_COST) Best_Cost = -1; return ; miniSum += miniO

9、uti; for(i=0;i<City_Size;i+) Best_Cost_Pathi = i; Best_Cost = MAX_COST; pNode = new Node; pNode->lcost = 0; pNode->cc = 0; pNode->rcost = miniSum; pNode->s = 0; pNode->pNext = NULL; for(int k=0;k<City_Size;k+) pNode->xk = Best_Cost_Pathk; put(heap,*pNode); while(pNode != NULL

10、 && (pNode->s) < City_Size-1) for(int k=0;k<City_Size;k+) Best_Cost_Pathk = pNode->xk ; 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 &&

11、; edge2 >= 0 && (pNode->cc+edge1+edge2) < Best_Cost) Best_Cost = pNode->cc + edge1+edge2; pNode->cc = Best_Cost; pNode->lcost = Best_Cost; pNode->s+; else for (i=pNode->s;i<City_Size;i+) if(City_GraphpNode->xpNode->spNode->xi >= 0) int temp_cc = pNode-&

12、gt;cc+City_GraphpNode->xpNode->spNode->xi; int temp_rcost = pNode->rcost-miniOutpNode->xpNode->s; if (temp_cc+temp_rcost<Best_Cost) for (j=0;j<City_Size;j+) temp_xj=Best_Cost_Pathj; temp_xpNode->xpNode->s+1 = Best_Cost_Pathi; temp_xi = Best_Cost_PathpNode->s+1; Node*

13、 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 = RemoveMiniHeap(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("最小花费"