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

旅行商售货员问题的分支限界算法 姓名： 学号： 一、实验目的与要求 1、掌握旅行商售货员问题的分支限界算法； 2、区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。 二、实验题： 编程实现：某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。 三、实验提示 旅行商问题的解空间是一个排列树。有两种实现的方法。第一种是只使用一个优先队列，队列中的每个元素 中都包含到达根的路径。另一种是保留一个部分解空间树和一个优先队列，优先队列中 的元素并不包含到达根的路径。以下为第一种方法。 由于我们要寻找的是最小耗费的旅行路径，因此可以使用最小耗费分枝定界法。在实现过程中，使用一个最小优先队列来记录活节点，队列中每个节点的类型为MinHeapNode。每个节点包括如下区域： x（从1到n的整数排列，其中x[0] = 1 ）#include stdio.h #include istream 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;