while(E->s < n - 1)
{//非叶结点
if(E->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] < bestc /*该节点相应费用小于最小费用*/
|| 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
free(E->x);//该页节点不满足条件舍弃扩展结点
}else
{/*产生当前扩展结点的儿子结点
当s<n-2时，算法依次产生当前扩展结点的所有儿子结点。由于当前扩展结点所相应的路径是x[0:s]，其可行儿子结点是从剩余顶点x[s+1:n-1]中选取的顶点x[i]，且(x[s]，x[i])是所给有向图G中的一条边。
对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x[0:s]，x[i])的费用cc和相应的下界lcost。
当lcost<bestc时，将这个可行儿子结点插入到活结点优先队列中。*/
for(i = E->s + 1; i < n; 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 < bestc || bestc == NoEdge)
{//子树可能含最优解,结点插入最小堆
MinHeapNode * N;
N = (MinHeapNode*)malloc(sizeof(MinHeapNode));
N->x = new int[n];
for(int j = 0; j < n; j++)
N->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);
}//完成结点扩展
DeleteMin(E);//取下一扩展结点
if(E == NULL)
break; //堆已空
}
if(bestc == NoEdge)
return NoEdge;//无回路
for(i = 0; i < n; i++)
v[i + 1] = E->x[i];//将最优解复制到v[1:n]
while(true)
{//释放最小堆中所有结点
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 <= n; i++)
{
a[i] = (int*)malloc(sizeof(int) * (n + 1));
}
for(i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
fscanf(in, "%d", &a[i][j]);
// prev = (int*)malloc(sizeof(int)*(n+1)) ;
int*v = (int*)malloc(sizeof(int) * (n + 1));// MaxLoading(w , c , n) ;
for(i = 1; i <= n; i++)
v[i] = 0;
bestc = BBTSP(v);
for(i = 1; i <= n; i++)
fprintf(stdout, "%d\t", v[i]); fprintf(stdout, "\n"); fprintf(stdout, "%d\n", bestc);
return 0;
}
责任编辑：小草
