求离散里面哈米尔顿图的最短路径的算法?

来源:百度知道 编辑:UC知道 时间:2024/06/02 01:08:04
最好能给出判断一个图是否为哈米尔顿图,如果是求出这个哈米尔顿图的最短路径。谢谢。

本程序参考了风云的最短路径代码( http://member.nease.com/~cloudwu),
并加以改进和优化:
1、把原来用于存放已处理节点的堆栈改为(store_queue)队列,这样在从
sort_queue队列出列时可直接放入store_queue中。
2、解除了地图大小的限制(如果有64K内存限制时,地图大小只能是180x180)
3、删除了原程序中的一些冗余,见程序中的注释。
4、程序继续使用dis_map数组保存各点历史历史最佳距离,也包含了某点是否已经
经过的信息,虽然这样做可能会比使用链表多用一些内存,但是在搜索时可以
节省不时间。
5、程序更具有实用性,可直接或修改后运用于你的程序中,但请你使用该代码后
应该返回一些信息给我,如算法的改进或使用于什么程序等。
本程序可以用Borland C++或DJGPP编译,并附带有一个数据文件 map.dat,
保存有地图的数据,(注:该地图文件格式与风云的原代码的地图格式不一样)
算法描述:
findpath()
{
把S点加入树根(各点所在的树的高度表示从S点到该点所走过的步数);
把S点加入排序队列(按该点到E点的距离排序+走过的步数从小到大排序);
1、排序队列sort_queue中距离最小的第一个点出列,并保存入store_queue中
2、从出列的点出发,分别向4个(或8个)方向中的一个各走出一步
3、并估算第2步所走到位置到目标点的距离,并把该位置加入树,
最后把该点按距离从小到大排序后并放入队列中。(由trytile函数实现)。
4、如果该点从四个方向上都不能移动,则把该点从store_queue中删除
5、回到第一点,直到找到E点则结束
从目标点回溯树,直到树根则可以找到最佳路径,并保存在path[]中
} <