#include“iostream.h“

struct?node???//城市節(jié)點?
{
	int?num;
	int?fvalue;//f值
	int?gvalue;//g值
	int?hvalue;//h值
	int?level;?//層
	struct?node?*parent;//父節(jié)點
	struct?node?*next;//后繼
	struct?node?*front;//前驅(qū)
};

struct?final_path
{
	struct?node?*head;
	struct?node?*tail;?
}OpenBestpath;

int?main（）
{
	int?relation[100][100];//鄰接矩陣
	int?path[100];?????????//路徑點集合
	int?ijnumber;????????//number?路徑點的數(shù)目
	int?max=0;			???//存放最大值用于計算h值
	int?min;???????????????//存放最小值用于計算h值
	int?count;?????????????//用于計數(shù)

	cout<<“???輸入路徑點的數(shù)目：“;
	cin>>number;
	for（i=0;i	{
		path[i]=i+1;//用1，2，3，4.....來表示路徑點
	}

	cout<<“???按照下例方式（只輸入點陣部分）“<		<<“??????A?B?C?D?E?.?.“<		<<“????A?.?.?.?.?.?.?.“<		<<“????B?.?.?.?.?.?.?.“<		<<“????C?.?.?.?.?.?.?.“<		<<“????D?.?.?.?.?.?.?.“<		<<“????E?.?.?.?.?.?.?.“<		<<“????.?.?.?.?.?.?.?.“<		<<“????.?.?.?.?.?.?.?.“<		<<“輸入路徑點的關(guān)系權(quán)（或者鄰接矩陣）：“<	
	for（i=0;i	{//輸入鄰接矩陣
		for（j=0;j		{
			cin>>relation[i][j];
			if（relation[i][j]>max）max=relation[i][j];
			cout<<“???max：“<		}
	}
	min=max;//初始化min
	cout<<“???min：“<
	for（i=0;i	{
		for（j=0;j		{
			if（relation[i][j]==0）continue;
			else?
			{
				if（min>relation[i][j]）
					min=relation[i][j];
			}
		}
	}
	cout<<“???min：“<	
	struct?node?*p0=new?struct?node;
	p0->level=0;
	p0->num=1;????????//A點
	p0->parent=NULL;
	path[0]=-1;???????//默認(rèn)從第一個路徑點開始搜索
	
	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;
	//p1p2用于確定節(jié)點插入Open表的位置
	for（i=1;i	{//插入節(jié)點
		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
		{//尋找最優(yōu)路徑點
			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開始進(jìn)入循環(huán)）
	while（1）
	{
		for（i=0count=0;i		{
			if（path[i]==-1）
			{
				count++;
			}
		}
		if（count==number）break;//path數(shù)組中所有元素均為-1則退出
		else
		{
			p1=Open.tail->front;
			p2=Open.tail;
			for（i=0;i			{
				if（path[i]!=-1）
				{
					struct?node?*p;
					p=new?struct?node;
					p->num=path[i];
					p->level=p_min->level+1;????//由最優(yōu)路徑點的level確定子節(jié)點的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;
				

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2010-12-02?13:33??旅行商問題\
?????文件????????5252??2010-11-30?20:07??旅行商問題\mymain.cpp
?????文件??????185856??2010-12-02?13:00??旅行商問題\S310067007宋新景（作業(yè)一）.doc
?????文件?????????294??2010-11-29?21:49??旅行商問題\作業(yè)要求.txt
?????文件????????5496??2010-12-01?19:25??旅行商問題\旅行商問題.cpp