分支限界旅行售貨員

/*
----input.txt

4
0 1 2 3
1 0 9 4
2 9 0 6
3 4 6 0

*/
#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 ; 
	int i;
	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){//目前擴充結點是葉結點的父結點
		/*
		首先考慮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(out , "%d\t" , v[i]) ;
	fprintf(out , "\n") ;
	fprintf(out , "%d\n" , bestc) ;
	return 0 ;
}