#include <stdio.h> #include <malloc.h>
#define NoEdge 1000
struct MinHeapNode
{
int lcost; //子树费用的下界
int cc; //当前费用
int 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 NoEdge; //图G的无边标记
int cc; //当前费用
int bestc; //当前最小费用
MinHeapNode* head = 0; /*堆头*/
MinHeapNode* lq = 0; /*堆第一个元素*/
MinHeapNode* fq = 0; /*堆最后一个元素*/
int DeleteMin(MinHeapNode*&E)
{
MinHeapNode* tmp = NULL;
tmp = fq;
// w = fq->weight ;
E = fq;
if(E == NULL)
return 0;
head->next = fq->next; /*一定不能丢了链表头*/
fq = fq->next;
// free(tmp) ;
return 0;
}
int Insert(MinHeapNode* hn)
{
if(head->next == NULL)
{
head->next = hn; //将元素放入链表中
fq = lq = head->next; //一定要使元素放到链中
}else
{
MinHeapNode *tmp = NULL;
tmp = fq;
if(tmp->cc > hn->cc)
{
hn->next = tmp;
head->next = hn;
fq = head->next; /*链表只有一个元素的情况*/
}else
{
for(; tmp != NULL;)
{
if(tmp->next != NULL && tmp->cc > hn->cc)
{
hn->next = tmp->next;
tmp->next = hn;
break;
}
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 <= n; i++)
{
int Min = NoEdge; /*定义当前最小值*/
for(int j = 1; j <= n; j++)
if(a[i][j] != NoEdge && /*当定点i,j之间存在回路时*/ (a[i][j] < Min || Min == NoEdge)) /*当顶点i,j之间的距离小于Min*/
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];
// E.x=new int[n];
for(i = 0; i < n; i++)
E->x[i] = i + 1;
E->s = 0;
E->cc = 0;
E->rcost = MinSum;
E->next = 0; //初始化当前扩展节点
int bestc = NoEdge; /*记录当前最小值*/
//搜索排列空间树
责任编辑：小草
