算法分析题目:旅行商问题
旅行商问题：
程序源码：
#include
#include
#define NoEdge 1000//图G的无边标记
struct MinHeapNode//最小堆，用于表示活结点优先队列；
{
}; int lcost,cc,rcost; //x[s:n-1]中顶点最小出边权的和 int s; //根节点到当前节点的路径为x[0:s] int *x; //需要进一步搜索的顶点是//x[s+1:n-1] struct MinHeapNode *next;
int n; //图G的顶点数
int **a; //图G的邻接矩阵
int cc; //当前费用
int bestc; //当前最小费用
MinHeapNode* head = 0; /*堆头*/
MinHeapNode* fq = 0; /*堆第一个元素*/
MinHeapNode* lq = 0; /*堆最后一个元素*/
int DeleteMin(MinHeapNode*&E)
{
MinHeapNode* tmp = NULL;
tmp = fq;
} E = fq; if(E == NULL) return 0; head->next = fq->next; /*一定不能丢了链表头*/ fq = fq->next; return 0;
int Insert(MinHeapNode* hn)
{
if(head->next == NULL) { } else { MinHeapNode *tmp = NULL; tmp = fq; if(tmp->cc > hn->cc) head->next = hn; //将元素放入链表中 fq = lq = head->next; //一定要使元素放到链中
} else { for(; tmp != NULL;) { if(tmp->next != NULL && tmp->cc > hn->cc) { hn->next = tmp->next; tmp->next = hn; break; hn->next = tmp; head->next = hn; fq = head->next; /*链表只有一个元素的情况*/ } tmp = tmp->next; } } if(tmp == NULL) { lq->next = hn; lq = lq->next; } } return 0;
}
int BBTSP(int v[])
{//解旅行商问题的优先队列式分支限界法
/*初始化最优队列的头结点*/
head = (MinHeapNode*)malloc(sizeof(MinHeapNode));
head->cc = 0; head->x = 0; head->lcost = 0; head->next = NULL; head->rcost = 0; head->s = 0; int *MinOut = new int[n + 1]; /*定义定点i的最小出边费用*/ //计算MinOut[i]=顶点i的最小出边费用 int MinSum = 0;//最小出边费用总合 for(int i = 1; i
} Min = a[i][j]; /*更新当前最小值*/ if(Min == NoEdge) return NoEdge;//无回路 MinOut[i] = Min; /*顶点i的最小出边费用*/ MinSum += Min; /*最小出边费用的总和*/ MinHeapNode *E = 0; E = (MinHeapNode*)malloc(sizeof(MinHeapNode)); E->x = new int[n]; for(i = 0; i x[i] = i + 1; E->s = 0; E->cc = 0; E->rcost = MinSum; E->next = 0; //初始化当前扩展节点 int bestc = NoEdge; /*记录当前最小值*/ //搜索排列空间树 while(E->s s == n - 2)
{//当前扩展结点是叶结点的父结点
/*
首先考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应一条可行回路
*/ if(a[E->x[n - 2]][E->x[n - 1]] != NoEdge && /*当前要扩展和叶节点有边存在*/ a[E->x[n - 1]][1] != NoEdge && /*当前页节点有回路*/
(E->cc + a[E->x[n - 2]][E->x[n - 1]] + a[E->x[n - 1]][1]
{
}
else
free(E->x);//该页节点不满足条件舍弃扩展结点 || bestc == NoEdge)) bestc = E->cc + a[E->x[n - 2]][E->x[n - 1]] + a[E->x[n - 1]][1]; /*更新当前最新E->cc = bestc; E->lcost = bestc; E->s++; E->next = NULL; Insert(E); /*将该页节点插入到优先队列中*/ 费用*/
} else
{/*产生当前扩展结点的儿子结点
当s
其可行儿子结点是从剩余顶点x[s+1:n-1]中选取的顶点x[i]，且(x[s]，x[i])是所给有向图G中的一条边。
对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x[0:s]，x[i])的费用cc和相应的下界lcost。
当lcost
for(i = E->s + 1; i
if(a[E->x[E->s]][E->x[i]] != NoEdge)
{ /*当前扩展节点到其他节点有边存在*/
//可行儿子结点
int cc = E->cc + a[E->x[E->s]][E->x[i]]; /*加上节点i后当前节点路径*/ int rcost = E->rcost - MinOut[E->x[E->s]]; /*剩余节点的和*/ int b = cc + rcost; //下界 if(b x = new int[n]; for(int j = 0; j x[j] = E->x[j]; N->x[E->s + 1] = E->x[i]; N->x[i] = E->x[E->s + 1];/*添加当前路径*/ N->cc = cc; /*更新当前路径距离*/ N->s = E->s + 1; /*更新当前节点*/ N->lcost = b; /*更新当前下界*/ N->rcost = rcost; N->next = NULL; Insert(N); /*将这个可行儿子结点插入到活结点优先队列中*/
}
}
free(E->x); }//完成结点扩展 } if(bestc == NoEdge) return NoEdge;//无回路 for(i = 0; i x[i];//将最优解复制到v[1:n] while(true) DeleteMin(E);//取下一扩展结点 if(E == NULL) break; //堆已空
free(E->x); DeleteMin(E); if(E == NULL) break; } return bestc;
}
int main()
{
n = 0; int i = 0; FILE *in, *out; in = fopen("input.txt", "r"); out = fopen("output.txt", "w"); if(in == NULL || out == NULL) { printf("没有输入输出文件\n"); return 1; } fscanf(in, "%d", &n); a = (int**)malloc(sizeof(int*) * (n + 1)); for(i = 1; i
for(i = 1; i
v[i] = 0;
}
bestc = BBTSP(v); for(i = 1; i ", v[i]); if(i=n) fprintf(stdout,"%d",v[i]); fprintf(stdout, "\n"); fprintf(stdout, "%d\n", bestc); return 0;
算法分析
先计算任何旅程长度l的下界：对于每个城市i,1