//分支定界法解有條件限制下的最小路徑問題
//Author:SY0806209成柳

#include <stdio.h>
#include "BranchBound.h"

//從文件中讀出圖的矩陣形式
int readMatrix(FILE *,int **);

//排序，將每個節點與其他節點的距離排序，得到排序后的索引，據此以構造圖的鏈表，使得深度優先，擴展節點時，選擇最短的路徑，盡早的定下界
void sortMatrix(int *,int *);

//分支定界法搜索，遞歸調用，深度優先
void branchBoundSearch(PNode *,int);


int m1[50][50];  //城市之間距離的有向圖矩陣
int m2[50][50];  //城市之間道路的收費額有向圖矩陣

int bound[50];	//分支定界的下界，為每個節點都定一個下界，即從0節點到i節點的當前最小距離

int stack[50];  //堆棧，保存當前搜索路徑
int top = -1;   //棧頂

int answer[50][50];		//保存找到的可行解，最后一個是最優解
int count = 0;			//可行解的個數

int current = 0;   //當前搜索路徑的長度

int spend =0;      //當前搜索路徑的花費

int cost= 0;  //存最優解的花費


//主函數
int
main()
{
	int i = 0;
	PNode length_map[50];    //有向圖的鏈表表示，存距離有向圖


	//1.讀入距離和花費的兩個矩陣m1、m2。
	FILE * file;
	if ((file = fopen("m1.txt","r"))==NULL)
		printf("open file m1.txt error");

	readMatrix(file,m1);
	fclose(file);
	if ((file=fopen("m2.txt","r"))==NULL)
	{
		printf("open file m2.txt error");
	}
	readMatrix(file,m2);
	fclose(file);

	//2.把m1距離有向圖信息保存在鏈表length_map。
	for (i=0;i<50;i++)
	{
		length_map[i] =NULL;
		bound[i] = 9999;     //初始化下界，開始都為無限大
	}
	createMap(length_map,m1);

	//3、分支定界法搜索圖，找到最優解。
	branchBoundSearch(length_map,0);

	//4、打印出最優解的路徑、距離、花費
	printf("作者：SY0806209成柳\n");
	printf("\nPath：0-->");
	for(i=0;i<50&answer[count-1][i]!=49;i++)
	{
		printf("%d-->",answer[count-1][i]);
	}
	printf("49\n");
	printf("Length：%d\n",bound[49]);
	printf("Cost：%d\n",cost);

	return 0;
}


//從文件中讀出圖的矩陣形式
int readMatrix(FILE * file,int m[50][50])
{
	char temp[5],ch;
	int i = 0,k=0;
	while((ch=fgetc(file))!=EOF)
	{
		if (ch!='\t'&&ch!=' '&&ch!='\n')
		{
			temp[k++] = ch;
		}
		else
		{
			temp[k] = '\0';
			m[i/50][i%50] = atoi(temp);
			i++;
			k=0;
		}
	}
	
	return 0;
}


//排序，將每個節點與其他節點的距離排序，得到排序后的索引，據此以構造圖的鏈表，使得深度優先，擴展節點時，選擇最短的路徑，盡早的定下界
void sortMatrix(int * m,int *key)
{
	int i,j;
	int min = 0;
	int mk;
	int temp;

	for (i=0;i<50;i++)
	{
		key[i]=i;
	}
	for (i=0;i<49;i++)
	{
		min = m[key[i]];
		for (j=i+1;j<50;j++)
		{
			if (m[key[j]]<min)
			{
				min = m[key[j]];
				mk = j;
			}
		}
		if (min != m[key[i]])
		{
			temp = key[i];
			key[i] = key[mk];
			key[mk] = temp;
		}
	}

}



//由矩陣表示構造出鏈表表示
void createMap(PNode * lenth_map,int m[][50])
{
	int key[50];
	int i,j;
	PNode aNode,tail;
 
	for(i=0;i<50;i++)
	{
		//排序，將每個節點與其他節點的距離排序，得到排序后的索引，據此以構造圖的鏈表，使得深度優先，擴展節點時，選擇最短的路徑，盡早的定下界
		sortMatrix(m,key);

		for(j=0;j<50;j++)
		{
			if (m[i][key[j]]!=9999)
			{
				aNode = (PNode)malloc(sizeof(Node));
				aNode->id = key[j];
				aNode->nextNode = NULL;
				if(lenth_map[i]==NULL)
				{
					lenth_map[i] = aNode;
				}
				else
					tail->nextNode = aNode;
				tail = aNode;
			}
		}
	}

}




//分支定界法搜索，遞歸調用，深度優先
void branchBoundSearch(PNode * length_map,int v)
{
	PNode w;
	int i,j;
	int flag=0;

	w = length_map[v];
	
	//已遞歸到了終點49，即產生一個可行解，存儲
	if (v == 49)
	{
		cost = spend;
		for(j=0;j<=top;j++)
			answer[count][j] = stack[j];
		count++;
	}

	//遞歸調用，深度優先遍歷
	while(w!=NULL)
	{
		i = w->id;

		//判斷是否回路，flag置1，回路
		for(j=0;j<=top;j++)
		{
			if (stack[j]==i)
			{
				flag =1; 
				break;
			}
		}

		//非回路
		if (flag == 0)
		{
			current += m1[v][i];
			spend += m2[v][i];

			//當前路徑距離小于下界，且花費在1200之類，則繼續遞歸，即擴展當前節點，記錄路徑
			//若非，則停止擴展，剪枝
			if(current< bound[i] && spend < 1200)
			{
				bound[i] = current;
				top++;
				stack[top] = i;
				branchBoundSearch(length_map,i);
				top--;
			}

			current -= m1[v][i];
			spend -= m2[v][i];
		}
		
		w = w->nextNode;
		flag = 0;
	}
}