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

旅行商售货员问题的分支限界算法 姓名： 学号： 一、实验目的与要求 1、掌握旅行商售货员问题的分支限界算法； 2、区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。 二、实验题： 编程实现：某售货员要到若干城市去推销商品，已知各城市之间的路程 或旅费 。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程 或总旅费 最小。 三、实验提示 旅行商问题的解空间是一个排列树。有两种实现的方法。第一种是只使用一个优先队列，队列中的每个元素 中都包含到达根的路径。另一种是保留一个部分解空间树和一个优先队列，优先队列中 的元素并不包含到达根的路径。以下为第一种方法。 由于我们要寻找的是最小耗费的旅行路径，因此可以使用最小耗费分枝定界法。在实现过程中，使用一个最小优先队列来记录活节点，队列中每个节点的类型为MinHeapNode。每个节点包括如下区域： x（从1到n的整数排列，其中x[0] 1 ）#include #include using namespace std; // #define MAX_CITY_NUMBER 10 //城市最大数目 #define MAX_COST//两个城市之间费用的最大值 // int City_Graph[MAX_CITY_NUMBER][MAX_CITY_NUMBER]; //表示城市间边权重的数组 int City_Size; //表示实际输入的城市数目 int Best_Cost; //最小费用 int Best_Cost_Path[MAX_CITY_NUMBER]; //最小费用时的路径 // typedef struct Node int lcost; //优先级 int cc; //当前费用 int rcost; //剩余所有结点的最小出边费用的和 int s; //当前结点的深度，也就是它在解数组中的索引位置 int x[MAX_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;k City_Size;k++ pinnode- x[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 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_x[MAX_CITY_NUMBER]; Node* pN