Astar 算法求解旅行商问题
一、问题描述
一共有 n 个城市,某推销员从其中的一个城市 A 出发经过每个城市一次且仅一次后回
到 A,求代价最小的路径。
二、知识表示
1、状态表示
初始状态,目标状态。
初始状态:A(出发城市)
目标状态:A,···((n-1)个城市),A
2、算法描述
(1)设城市结点的个数为 n,获取开始结点,计算所有成员变量的值,将开始结点放
入 open 表(open 表用队列实现);
(2)如果 open 表不为空,转(3),否则转(7);
(3)将 open 表中的首元素放入 close 表,并将该首元素从 open 表中删除。
(4)获取已访问结点的个数 num,如果 num ≥ n+1,则找到最佳路径,转(7);
(5)如果 num==n,还访问一个结点到达目标结点,设置初始结点的访问状态 isVisited[0]
的值为 false,表示初始结点没有被访问,即可以回到出发点;
(6)如果 num<n,将从当前结点出发可访问的结点和 open 表中剩余的结点放入一个向
量 vector 中,根据每个结点的 fvalue 值按升序排列,排列的结果按升序放入 open 表,转
(2);
(7)获取 close 表中的最后一个元素,打印最佳路径,相邻城市之间的距离,最短的
距离值。
3、估价函数
f(n)=g(n)+h(n) ,h(n)≤h*(n)。
g(n):从开始结点到当前结点 n 的实际距离,等于路径的权值的和。
h(n):假设城市结点 n 的深度为 depth,城市的个数为 city_num,(city_num-depth)表示
从 n 到 目 标 城 市 还 需 要 的 路 径 个 数 , min 表 示 所 有 路 径 长 度 的 最 小 值 , 则
h(n)=min*(city_num-deep)表示从当前城市结点 n 到目标结点的路径长度的最小估计值,h(n)
≤h*(n)显然对于任意的一个城市结点都成立。
三、算法实现
主要的数据结构
城市结点:depth 表是从开始城市到当前城市,访问的城市个数,也可以称为深度;num
表示已访问的城市结点的个数; id_list 是一个数组,表示从开始城市到当前城市的所有城
市的编号的集合,编号的值从 1 开始;isVisited 是一个布尔数组,记录当前城市结点到目标
城市结点的访问状态,布尔值为 false,表示可访问;fvalue 表示从开始城市出发回到原点的
估计值。
城市之间的距离:通过 n*n 矩阵 city_distance 表示,其中 n 表示城市的个数。编号为 k
的城市到各个城市之间的距离可以从第(k-1)行获取。
open 表:用队列表示,城市结点进入队列之前需要根据估计值 fvalue 按升序排列。