branchbound.c

算法作业

//分支定界法解有条件限制下的最小路径问题
//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;
	}
}