A星算法求解旅行商问题.doc

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）如果numn，将从当前结点出发可访问的结点和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按升序排列。 close表：用向量表示。 搜索图：搜索图通过open表构建，将路径的编号保存在一个数组id_list中。 四、实验结果和分析 1、输入数据 第一行的数值8表示城市结点的个数，后面是一个8*8的数组，数组的值表示城市之间的距离。任何一个结点到自身的距离是0，数组中的第0行表示第1个城市到各个城市之间的距离，其他的可类推。 2、用户界面 3、运行结果 通过验证，运行结果和期望值一致。 由于每个城市结点需要保存之前的路径，因此增加了空间复杂度。 五、程序 一共有三个类，City，TspAStar，MyQueue，City是TspAStar的内部类。 1、City和TspAStar package hrbeu.edu.tspByHdy; import java.beans.PropertyChangeEvent; import java.beans.PropertyChangeListener; import java.io.BufferedReader; import java.io.File; import java.io.FileInputStream; import java.io.FileWriter; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.Vector; import javax.swing.JFileChooser; import javax.swing.JOptionPane; //城市结点类，表示访问到中间某个城市的状态 class City{ int depth = 0;//当前深度 int[] id_list = null;//已经访问的城市的编号 int num = 0;//已经访问的城市的个数 boolean[] isVisited = null;//城市结点访问标志 int fvalue = 0; //估计值 public City(int city_num){ id_list = new int[city_num + 1]; isVisited =