程序源代码.txt

用A星算法解决旅行商（货郎担）问题

#include"iostream.h"

struct node
{
	int num;
	int fvalue;//f值
	int gvalue;//g值
	int hvalue;//h值
	int level; //层
	struct node *parent;//父节点
	struct node *next;//后继
	struct node *front;//前驱
};

struct final_path
{
	struct node *head;
	struct node *tail; 
}Open,Bestpath;

void main()
{
	int relation[100][100];//邻接矩阵
	int path[100];         //路径点集合
	int i,j,number;        //number 路径点的数目
	int max=0;			   //存放最大值,用于计算h值
	int min;               //存放最小值,用于计算h值
	int count;             //用于计数

	cout<<"   输入路径点的数目：";
	cin>>number;
	for(i=0;i<number;i++)
	{
		path[i]=i+1;//用1，2，3，4.....来表示路径点
	}

	cout<<"   按照下例方式(只输入点阵部分)"<<endl
		<<"      A B C D E . ."<<endl
		<<"    A . . . . . . ."<<endl
		<<"    B . . . . . . ."<<endl
		<<"    C . . . . . . ."<<endl
		<<"    D . . . . . . ."<<endl
		<<"    E . . . . . . ."<<endl
		<<"    . . . . . . . ."<<endl
		<<"    . . . . . . . ."<<endl
		<<"输入路径点的关系权(或者邻接矩阵)："<<endl;
	
	for(i=0;i<number;i++)
	{//输入邻接矩阵
		for(j=0;j<number;j++)
		{
			cin>>relation[i][j];
			if(relation[i][j]>max)max=relation[i][j];
		}
	}
	min=max;//初始化min

	for(i=0;i<number;i++)
	{
		for(j=0;j<number;j++)
		{
			if(relation[i][j]==0)continue;
			else 
			{
				if(min>relation[i][j])
					min=relation[i][j];
			}
		}
	}
	
	struct node *p0=new struct node;
	p0->level=0;
	p0->num=1;//A点
	p0->parent=NULL;
	path[0]=-1;//默认从第一个路径点开始搜索
	
	Open.head=new struct node;
	Open.tail=new struct node;
	Open.head->next=Open.tail;
	Open.tail->front=Open.head;//初始化Open表

	struct node *p1,*p2;
	struct node *p_min;
	struct node *p_temp;
	p1=Open.head;
	p2=Open.tail;
	//p1,p2用于确定节点插入Open表的位置
	for(i=1;i<number;i++)
	{//插入节点
		struct node *p;
		p=new struct node;

		p->num=path[i];
		p->level=1;//第一层
		p->gvalue=relation[0][i];//A点到其他点的距离
		p->hvalue=min*(number-p->level-1);
		p->fvalue=p->gvalue+p->hvalue;
		p->parent=p0;

		p1->next=p;
		p->front=p1;
		p->next=p2;
		p2->front=p;
		p1=p;

		if(i==1)p_min=p1;
		else
		{//寻找最优路径点
			if(p_min->fvalue>p1->fvalue)p_min=p1;
		}
	}
	
	p_temp=p_min;
	//在Open中删除找到的路径点
	p_min->front->next=p_min->next;
	p_min->next->front=p_min->front;

	path[p_min->num-1]=-1;

	//扩展找到的路径点（从第二层level=2开始进入循环）
	while(1)
	{
		for(i=0,count=0;i<number;i++)
		{
			if(path[i]==-1)
			{
				count++;
			}
		}
		if(count==number)break;//path数组中所有元素均为-1,则退出
		else
		{
			p1=Open.tail->front;
			p2=Open.tail;
			for(i=0;i<number;i++)
			{
				if(path[i]!=-1)
				{
					struct node *p;
					p=new struct node;
					p->num=path[i];
					p->level=p_min->level+1;//由最优路径点的level确定子节点的level
					p->gvalue=p_min->gvalue+relation[p_min->num-1][i];
					p->hvalue=min*(number-p->level-1);
					p->fvalue=p->gvalue+p->hvalue;
					p->parent=p_min;

					p1->next=p;
					p->front=p1;
					p->next=p2;
					p2->front=p;
					p1=p;
				}
			}
		}
		struct node *p=Open.head->next;
		i=1;
		while(p!=Open.tail)
		{//从Open表中寻找
			if(i==1)p_min=p;
			else
			{//寻找最优路径点
				if(p_min->fvalue>p->fvalue)p_min=p;
			}
			i++;
			p=p->next;
		}//找到最优路径点

		p=p_temp;//上一次的最优路径点
		while(p!=NULL)
		{//撤销上一次路径
			path[p->num-1]=p->num;
			p=p->parent;
		}

		p=p_min;//新找到的最优路径点
		while(p!=NULL)
		{//重配置新路径
			path[p->num-1]=-1;
			p=p->parent;
		}

		p_temp=p_min;//再次使得p_temp指向最优路径点，为下一次所用

		//在Open中删除找到的路径点
		p_min->front->next=p_min->next;
		p_min->next->front=p_min->front;
	}

	//循环结束
	
	//初始化Bestpath表
	Bestpath.head=new struct node;
	Bestpath.tail=new struct node;
	Bestpath.head->next=Bestpath.tail;
	Bestpath.tail->front=Bestpath.head;

	p1=Bestpath.head;
	p2=Bestpath.tail;

	struct node *p;
	p=p_min;
	while(p!=NULL)
	{//将路径顺序存入Bestpath表中
		p1->next=p;
		p->front=p1;
		p->next=p2;
		p2->front=p;
		p2=p;

		p=p->parent;
	}
	//输出结果
	//1:A
	//2:B
	//3:B
	//4:C
	//5:D
	//6:E
	//......
	cout<<"   字母与序号对应关系:"<<endl
		<<"   ----1:A----"<<endl
		<<"   ----2:B----"<<endl
		<<"   ----3:C----"<<endl
		<<"   ----4:D----"<<endl
		<<"   ----5:E----"<<endl
		<<"   ----6:F----"<<endl
		<<"   ..........."<<endl
		<<"路径如下:"<<endl<<endl;

	p=Bestpath.head->next;
	while(p!=Bestpath.tail)
	{//从Bestpath表中输出路径
		cout<<char(p->num+64)<<"-->";
		p=p->next;
	}
	cout<<"A"<<endl;
}