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

旅行商售货员问题的分支限界算法姓名： 学号：一、实验目的与要求1、掌握旅行商售货员问题的分支限界算法；2、区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。二、实验题：编程实现：某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。三、实验提示旅行商问题的解空间是一个排列树。有两种实现的方法。第一种是只使用一个优先队列，队列中的每个元素 中都包含到达根的路径。另一种是保留一个部分解空间树和一个优先队列，优先队列中 的元素并不包含到达根的路径。以下为第一种方法。 由于我们要寻找的是最小耗费的旅行路径，因此可以使用最小耗费分枝定界法。在实现过程中，使用一个最小优先队列来记录活节点，队列中每个节点的类型为MinHeapNode。每个节点包括如下区域： x（从1到n的整数排列，其中x0 = 1 ），s（一个整数，使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x0:s, 而剩余待访问的节点是x s + 1 : n - 1 ），cc（旅行路径前缀，即解空间树中从根节点到当前节点的耗费），lcost（该节点子树中任意叶节点中的最小耗费）， rcost（从顶点xs : n - 1出发的所有边的最小耗费之和）。当类型为MinHeapNode( T )的数据被转换成为类型T时，其结果即为lcost的值。代码：#include #include 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_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 = 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; 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) (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-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 MiniHeap; /分配堆 InitMiniHeap(heap); /初始化堆 miniSum = 0; for (i=0;iCity_Size;i+) miniOuti = MAX_COST; /初始化时每一个结点都不可达 for(j=0;j0 & City_GraphijminiOuti) /从i到j可达，且更小 miniOuti = City_Graphij; if (miniOuti = MAX_COST)/ i 城市没有出边 Best_Cost = -1; return ; miniSum += miniOuti; for(i=0;ilcost = 0; /当前结点的优先权为0 也就是最优 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-s) City_Size-1) /堆不空 不是叶子 for(int k=0;kxk ; /将最优路径置换为当前结点本身所保存的 /* * * 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; if(edge1 = 0 & edge2 = 0 & (pNode-cc+edge1+edge2) cc + edge1+edge2; pNode-cc = Best_Cost; pNode-lcost = Best_Cost; /优先权为 Best_Cost pNode-s+; /到达叶子层 else /内部结点 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_rcostBest_Cost) /下一个结点的最小出边费用和小于当前的最优解，说明可能存在更优解 for (j=0;jxpNode-s+1 = Best_Cost_Pathi; /将当前结点的编号放入路径的深度为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 = temp_xk; put(heap,*pNextNode); delete pNextNode; pNode = RemoveMiniHeap(heap); int main() int i,j;printf(请输入旅行的节点数); scanf(%d,&City_Size); for(i=0;iCity_Size;i+) printf(请分别输入每个节点与其它节点的路程花费); for(j=0;jCity_Size;j+) scanf(%d,&City_Graphij); Traveler(); printf(最小花费%dn,Best_Cost); return 1; 运行结果：分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机