A*算法解决旅行商问题

估价函数为f(n)=h(n)+g(n)。其中h(n)表示已经走过的实际路程。g(n)表示未走过路程到终点（起点）最短的距离。

#include“Astar.h“

//根据估价值排序
void sortNode（NodeState* pint l）
{
	int n=l;
	for（int i=0;i	{
		for（int j=0;j		{  
			if（（p->children[j]->f）>（p->children[j+1]->f））
			{
				NodeState *temp=p->children[j];
				p->children[j]=p->children[j+1];
				p->children[j+1]=temp;
			}
		}
	}
}

void cpyRoad（int dis[]int src[]int len）
{
	for（int i=0;i		dis[i]=src[i];
}

int getLen（int iint jMap map）
{
	return i}

void initNode（NodeState* nodeint n）
{
	node->road=（int*）malloc（sizeof（int）*n）;//分配路径
	for（int i=0;i		node->road[i]=0;

	node->f=node->roadLen=0;
	node->cityNum=n;
	node->children=（NodeState **）malloc（sizeof（NodeState*）*n-1）;//最多的子节点数目
	for（int i=0;i		node->children[i]=NULL;
}

void getNext（int road[]int nextCitys[]int n）
{
	int j=0;
	for（int i=0;i	{
		if（!road[i]） //没走过
		{	
			nextCitys[j]=i;
			j++;
		}
	}
}

Map inputMap（）
{
	Map map;
	int n=0;
	printf（“获得距离矩阵先输入城市数目:“）;
	scanf（“%d“&n）;
	getchar（）;

	map.num=n;
	map.rec=（int*）malloc（sizeof（int）*n*n）; //n方
	
	printf（“输入数据:\n“）;
	for（int i=0;i		for（int j=i+1;j		{
			printf（“%c->%c:“STRING[i]STRING[j]）;
			scanf（“%d“&（map.rec[i+j*n]））;
			getchar（）;
	    }
	return map;
}

int nearest（int road[]Map map）
{
	int min=MAXNUM;
	bool flag=false;  //判断是否还有没走过节点
	for（int i=0;i	{
		if（!road[i]） //没走过
		{
			flag=true;
			int len=getLen（0imap）; //第i个城市到终点距离 上层保证i>0
			if（len				min=len;
		}
	}
	if（!flag）
		return 0;
	return min;
}

bool AStar（NodeState& nodeMap map）
{
	//递归出口
	if（node.cityNum==map.num）  //路径满
	{
		node.roadLen+=getLen（node.city0map）;
 		return false;
	}
	
	int l=map.num-node.cityNum;  //剩下的城市数
	int* nextCitys=（int *）malloc（sizeof（int）*l）;
	getNext（node.roadnextCitysmap.num）;  //得到剩下城市名（索引）
	//初始化子节点
	for（int i=0;i	{
		node.children[i]=（NodeState *）malloc（sizeof（NodeState））;//分配一个子节点内存
		initNode（node.children[i]map.num）;                     //初始化子节点
		cpyRoad（node.children[i]->roadnode.roadmap.num）;     //获得之前走过的路径
		node.children[i]->road[nextCitys[i]]=node.cityNum+1;   //在路径上加上该子节点
		node.children[i]->city=nextCitys[i];            
		node.children[i]->cityNum=node.cityNum+1;              //该节点顺位
		node.children[i]->roadLen=node.roadLen+getLen（node.citynode.children[i]->citymap）;      //新的路径长度
		node.children[i]->f=node.children[i]->roadLen+nearest（node.roadmap）;     //计算估价值 最后一个节点f值不准
	}
	//根据估价值排序
	sortNode（&nodel）;

	//向下搜索
	bool toFind=true;  //是否继续搜索
	for（int i=0;i	{
		if（toFind）    //发现结果就不用继续递归了
		  toFind=AStar（*node.children[i]map）;
	}
	return toFind;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2014-04-28 23:19  源码\
     目录           0  2014-04-28 21:33  源码\AstartAboutTraveller\
     目录           0  2014-04-26 16:21  源码\AstartAboutTraveller\AstartAboutTraveller\
     文件     2248704  2014-04-28 21:33  源码\AstartAboutTraveller\AstartAboutTraveller.sdf
     文件         927  2014-04-26 12:41  源码\AstartAboutTraveller\AstartAboutTraveller.sln
     文件       15872  2014-04-28 21:33  源码\AstartAboutTraveller\AstartAboutTraveller.suo
     文件        3086  2014-04-28 21:28  源码\AstartAboutTraveller\AstartAboutTraveller\Astar.cpp
     文件        1735  2014-04-26 17:07  源码\AstartAboutTraveller\AstartAboutTraveller\Astar.h
     文件        4076  2014-04-26 16:33  源码\AstartAboutTraveller\AstartAboutTraveller\AstartAboutTraveller.vcxproj
     文件        1238  2014-04-26 16:33  源码\AstartAboutTraveller\AstartAboutTraveller\AstartAboutTraveller.vcxproj.filters
     文件         143  2014-04-26 12:41  源码\AstartAboutTraveller\AstartAboutTraveller\AstartAboutTraveller.vcxproj.user
     目录           0  2014-04-28 21:28  源码\AstartAboutTraveller\AstartAboutTraveller\Debug\
     文件       14378  2014-04-28 21:28  源码\AstartAboutTraveller\AstartAboutTraveller\Debug\Astar.obj
     文件         406  2014-04-26 15:00  源码\AstartAboutTraveller\AstartAboutTraveller\Debug\AstartAboutTraveller.exe.embed.manifest
     文件         472  2014-04-26 15:00  源码\AstartAboutTraveller\AstartAboutTraveller\Debug\AstartAboutTraveller.exe.embed.manifest.res
     文件         381  2014-04-28 21:28  源码\AstartAboutTraveller\AstartAboutTraveller\Debug\AstartAboutTraveller.exe.intermediate.manifest
     文件         105  2014-04-28 21:28  源码\AstartAboutTraveller\AstartAboutTraveller\Debug\AstartAboutTraveller.lastbuildstate
     文件        3314  2014-04-28 21:28  源码\AstartAboutTraveller\AstartAboutTraveller\Debug\AstartAboutTraveller.log
     文件         713  2014-04-26 15:44  源码\AstartAboutTraveller\AstartAboutTraveller\Debug\AstartAboutTraveller.vcxprojResolveAssemblyReference.cache
     文件           0  2014-04-26 15:00  源码\AstartAboutTraveller\AstartAboutTraveller\Debug\AstartAboutTraveller.write.1.tlog
     文件         230  2014-04-26 15:00  源码\AstartAboutTraveller\AstartAboutTraveller\Debug\AstartAboutTraveller_manifest.rc
     文件        1542  2014-04-28 21:28  源码\AstartAboutTraveller\AstartAboutTraveller\Debug\cl.command.1.tlog
     文件        2556  2014-04-28 21:28  源码\AstartAboutTraveller\AstartAboutTraveller\Debug\CL.read.1.tlog
     文件        1710  2014-04-28 21:28  源码\AstartAboutTraveller\AstartAboutTraveller\Debug\CL.write.1.tlog
     文件           2  2014-04-28 21:28  源码\AstartAboutTraveller\AstartAboutTraveller\Debug\link-cvtres.read.1.tlog
     文件           2  2014-04-28 21:28  源码\AstartAboutTraveller\AstartAboutTraveller\Debug\link-cvtres.write.1.tlog
     文件           2  2014-04-28 21:28  源码\AstartAboutTraveller\AstartAboutTraveller\Debug\link.13052-cvtres.read.1.tlog
     文件           2  2014-04-28 21:28  源码\AstartAboutTraveller\AstartAboutTraveller\Debug\link.13052-cvtres.write.1.tlog
     文件           2  2014-04-28 21:28  源码\AstartAboutTraveller\AstartAboutTraveller\Debug\link.13052.read.1.tlog
     文件           2  2014-04-28 21:28  源码\AstartAboutTraveller\AstartAboutTraveller\Debug\link.13052.write.1.tlog
     文件        2060  2014-04-28 21:28  源码\AstartAboutTraveller\AstartAboutTraveller\Debug\link.command.1.tlog
............此处省略42个文件信息