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

旅行商售货员问题的分支限界算法
姓名： 学号：
一、实验目的与要求
1、掌握旅行商售货员问题的分支限界算法；
2、区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。
二、实验题：
编程实现：某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。

三、实验提示
旅行商问题的解空间是一个排列树。有两种实现的方法。第一种是只使用一个优先队列，队列中的每个元素 中都包含到达根的路径。另一种是保留一个部分解空间树和一个优先队列，优先队列中 的元素并不包含到达根的路径。以下为第一种方法。
由于我们要寻找的是最小耗费的旅行路径，因此可以使用最小耗费分枝定界法。在实现过程中，使用一个最小优先队列来记录活节点，队列中每个节点的类型为MinHeapNode。每个节点包括如下区域： x（从1到n的整数排列，其中x[0] = 1 ），s（一个整数，使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x[0:s], 而剩余待访问的节点是x [s + 1 : n - 1 ]），cc（旅行路径前缀，即解空间树中从根节点到当前节点的耗费），lcost（该节点子树中任意叶节点中的最小耗费）， rcost（从顶点x[s : n - 1]出发的所有边的最小耗费之和）。当类型为MinHeapNode( T )的数据被转换成为类型T时，其结果即为lcost的值。
代码：
#include <stdio.h>
#include <istream>
using namespace std;
//---------------------宏定义------------------------------------------
#define MAX_CITY_NUMBER 10 //城市最大数目
#define MAX_COST 10000000 //两个城市之间费用的最大值
//---------------------全局变量----------------------------------------
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* pNode = NULL;
int miniSum; //所有结点最小出边的费用和
int miniOut[MAX_CITY_NUMBER];
//保存每个结点的最小出边的索引
MiniHeap* heap = new MiniHeap; //分配堆
InitMiniHeap(heap); //初始化堆

miniSum = 0;
for (i=0;i<City_Size;i++){
miniOut[i] = MAX_COST; //初始化时每一个结点都不可达
for(j=0;j<City_Size;j++){
if (City_Graph[i][j]>0 && City_Graph[i][j]<miniOut[i]){
//从i到j可达，且更小
miniOut[i] = City_Graph[i][j];
}
}
if (miniOut[i] == MAX_COST){// i 城市没有出边
Best_Cost = -1;
return ;
}
miniSum += miniOut[i];
}
for(i=0;i<City_Size;i++){ //初始化的最优路径就是把所有结点依次走一遍
Best_Cost_Path[i] = i;
}
Best_Cost = MAX_COST; //初始化的最优费用是一个很大的数
pNode = new Node; //初始化第一个结点并入堆
pNode->lcost = 0; //当前结点的优先权为0 也就是最优
pNode->cc = 0; //当前费用为0（还没有开始旅行）
pNode->rcost = miniSum; //剩余所有结点的最小出边费用和就是初始化的miniSum
pNode->s = 0; //层次为0
pNode->pNext = NULL;
for(int k=0;k<City_Size;k++){
pNode->x[k] = Best_Cost_Path[k]; //第一个结点所保存的路径也就是初始化的路径
}
put(heap,*pNode); //入堆
while(pNode != NULL && (pNode->s) < City_Size-1){
//堆不空 不是叶子
for(int k=0;k<City_Size;k++){
Best_Cost_Path[k] = pNode->x[k] ; //将最优路径置换为当前结点本身所保存的
}
/*
* * pNode 结点保存的路径中的含有这条路径上所有结点的索引
* * x路径中保存的这一层结点的编号就是x[City_Size-2]
* * 下一层结点的编号就是x[City_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) < Best_Cost){
//edge1 -1 表示不可达
//叶子可达起点费用更低
Best_Cost = pNode->cc + edge1+edge2;
pNode->cc = Best_Cost;
pNode->lcost = Best_Cost; //优先权为 Best_Cost
pNode->s++; //到达叶子层
}
}
else{ //内部结点
for (i=pNode->s;i<City_Size;i++){ //从当前层到叶子层
if(City_Graph[pNode->x[pNode->s]][pNode->x[i]] >= 0){ //可达
//pNode的层数就是它在最优路径中的位置
int temp_cc = pNode->cc+City_Graph[pNode->x[pNode->s]][pNode->x[i]];
int temp_rcost = pNode->rcost-miniOut[pNode->x[pNode->s]];
//下一个结点的剩余最小出边费用和
//等于当前结点的rcost减去当前这个结点的最小出边费用
if (temp_cc+temp_rcost<Best_Cost){ //下一个结点的最小出边费用和小于当前的最优解，说明可能存在更优解
for (j=0;j<City_Size;j++){ //完全copy路径，以便下面修改
temp_x[j]=Best_Cost_Path[j];
}
temp_x[pNode->x[pNode->s+1]] = Best_Cost_Path[i];
//将当前结点的编号放入路径的深度为s+1的地方
temp_x[i] = Best_Cost_Path[pNode->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;k<City_Size;k++){
pNextNode->x[k] = temp_x[k];
}
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_Graph[i][j]);
}
}
Traveler();
printf("最小花费""%d\n",Best_Cost);
return 1;
}
运行结果：

分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。 
由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。 
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。
有一些问题其实无论用回溯法还是分支限界法都可以得到很好的解决，但是另外一些则不然。n后问题比较适合采用回溯法解决，布线问题比较适合采用分支限界法解决，0-1背包问题既可以采用回溯法也可以采用分支限界法解决。