#include "StdAfx.h"
//源代码：
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <time.h>
#include <omp.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; /*堆最后一个元素*/
clock_t start, finish;
double duration;
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 i = 0;
int numThreads = 0;
int *MinOut = new int[n + 1]; /*定义定点i的最小出边费用*/
//计算MinOut[i]=顶点i的最小出边费用
int MinSum = 0;//最小出边费用总合
printf("please input the number of threads : ");
scanf_s("%d",&numThreads);
start = clock(); //开始时间
for(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; /*记录当前最小值*/
//搜索排列空间树
while(E->s < n - 1)
{//非叶结点
if(E->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
{//产生当前扩展结点的儿子结点
omp_set_num_threads(numThreads);
#pragma omp parallel for
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;
printf("please input the number of cites : ");
scanf_s("%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++)
/*scanf("%d", &a[i][j]);*/
{
//a[i][j] = (((i + j) * 99) % 14) + 1;
a[i][j] = i+j;
if(i == j)a[i][j]=0;
//printf("%d ",a[i][j]);
}
//printf("\n");
}
// 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);
printf("the best path is :");
for(i = 1; i <= n; i++)
{
printf("%d->", v[i]);
}
printf("1\nthe shortest cost is ");
printf("%d\n", bestc);
finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "the duaration time is ：%f seconds\n", duration );
system("pause");
return 0;
}