分支限界算法设计与应用

实验七 分支限界的应用一基本原理的概括一个具体问题，其解决的方法可能有很多种，可采用各种不同的算法设计方法。二该类算法设计与实现的要点熟练掌握各种算法设计方法三实验目的和要求要求用分支限界以及至少一种其它算法求解旅行商问题，提高综合应用各种算法设计方法的能力。四实验内容（分支限界算法&贪心算法）（1） 旅行商问题分支限界算法： 由于我们要寻找的是最小耗费的旅行路径，因此可以使用最小耗费分枝定界法。在实现过程中，使用一个最小优先队列来记录活节点，队列中每个节点的类型为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 1 * * 下一层结点的编号就是xCity_Size-*/ 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; （2） 旅行商问题贪心算法贪心算法：又称贪婪算法（greedy algorithm）,每次选择得到的都是局部最优解。选择的策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。针对TSP问题，使用贪心算法的求解的过程为：1.从某一个城市开始，每次选择一个城市，直到所有的城市被走完。2.每次在选择下一个城市的时候，只考虑当前情况，保证迄今为止经过的路径总距离最小。简化问题，假设只有A、B、C、D四个城市，各城市的关系如图所示，权值表示两个城市之间的的距离。将图中关系数据化：城市映射为编号：A0，B1，C2，D3；城市之间的距离用二维数组来表示，记为Dij，如：D01表示城市A与城市B之间的距离，于是D01=2；用一维数组Si来存储访问过的路径。代码如下#includeusing namespace std;#define n 4int main() int i,j,k,l; int Sn;/用于存储已访问过的城市 int Dnn;/用于存储两个城市之间的距离 int sum = 0;/用于记算已访问过的城市的最小路径长度 int Dtemp;/保证Dtemp比任意两个城市之间的距离都大（其实在算法描述中更准确的应为无穷大） int flag;/最为访问的标志，若被访问过则为1，从未被访问过则为0 /*初始化*/ i = 1;/i是至今已访问过的城市 S0 = 0; D01 = 2;D02 = 6;D03 = 5;D10 = 2;D12 = 4; D13 = 4;D20 = 6;D21 = 4;D23 = 2;D30 = 5; D31 = 4;D32 = 2; do k = 1;Dtemp = 10000; do l = 0;flag = 0; do if(Sl = k)/判断该城市是否已被访问过，若被访问过， flag = 1;/则flag为1 break;/跳出循环，不参与距离的比较 else l+; while(l i); if(flag = 0&DkSi - 1 Dtemp)/*DkSi - 1表示当前未被访问的城市k与上一个已访问过的城市i-1之间的距离*/ j = k;/j用于存储已访问过的