C++实现的旅行商问题

里面含有两种使用C++语言实现的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; 
}OpenBestpath;

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

	cout<<“   输入路径点的数目：“;
	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 . . . . . . .“<		<<“    . . . . . . . .“<		<<“    . . . . . . . .“<		<<“输入路径点的关系权（或者邻接矩阵）：“<	
	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;       //默认从第一个路径点开始搜索
	
	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用于确定节点插入Open表的位置
	for（i=1;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=0count=0;i		{
			if（path[i]==-1）
			{
				count++;
			}
		}
		if（count==number）break;//path数组中所有元素均为-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;    //由最优路径点的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;
				

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2010-12-02 13:33  旅行商问题\
     文件        5252  2010-11-30 20:07  旅行商问题\mymain.cpp
     文件      185856  2010-12-02 13:00  旅行商问题\S310067007宋新景（作业一）.doc
     文件         294  2010-11-29 21:49  旅行商问题\作业要求.txt
     文件        5496  2010-12-01 19:25  旅行商问题\旅行商问题.cpp