A星算法求解旅行商问题

1、Astar算法求解旅行商问题一、问题描述一共有n个城市，某推销员从其中的一个城市A出发经过每个城市一次且仅一次后回到A，求代价最小的路径。二、知识表示1、状态表示初始状态，目标状态。初始状态：A（出发城市）目标状态：A，（n-1）个城市），A2、算法描述（1）设城市结点的个数为n，获取开始结点，计算所有成员变量的值，将开始结点放入open表（open表用队列实现）；（2）如果 open表不为空，转（3），否则转（7）；（3）将open表中的首元素放入close表，并将该首元素从open表中删除。（4）获取已访问结点的个数num，如果num n+1，则找到最佳路径，转（7）；（5）如果num=n

2、，还访问一个结点到达目标结点，设置初始结点的访问状态isVisited0的值为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_n

3、um，(city_num-depth)表示从n到目标城市还需要的路径个数，min表示所有路径长度的最小值，则h(n)=min*(city_num-deep)表示从当前城市结点n到目标结点的路径长度的最小估计值，h(n)h*(n)显然对于任意的一个城市结点都成立。三、算法实现主要的数据结构城市结点：depth表是从开始城市到当前城市，访问的城市个数，也可以称为深度；num表示已访问的城市结点的个数； id_list是一个数组，表示从开始城市到当前城市的所有城市的编号的集合，编号的值从1开始；isVisited是一个布尔数组，记录当前城市结点到目标城市结点的访问状态，布尔值为false，表示可访问

4、；fvalue表示从开始城市出发回到原点的估计值。城市之间的距离：通过n*n矩阵city_distance表示，其中n表示城市的个数。编号为k的城市到各个城市之间的距离可以从第（k-1）行获取。open表：用队列表示，城市结点进入队列之前需要根据估计值fvalue按升序排列。 close表：用向量表示。搜索图：搜索图通过open表构建，将路径的编号保存在一个数组id_list中。四、实验结果和分析1、输入数据第一行的数值8表示城市结点的个数，后面是一个8*8的数组，数组的值表示城市之间的距离。任何一个结点到自身的距离是0，数组中的第0行表示第1个城市到各个城市之间的距离，其他的可类推。2、用户

5、界面3、运行结果通过验证，运行结果和期望值一致。由于每个城市结点需要保存之前的路径，因此增加了空间复杂度。五、程序一共有三个类，City，TspAStar，MyQueue，City是TspAStar的内部类。1、City和TspAStarpackage .tspByHdy;import java.beans.PropertyChangeEvent;import java.beans.PropertyChangeListener;import java.io.BufferedReader;import java.io.File;import java.io.FileInputS

6、tream;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 Cityint depth = 0;/当前深度int id_list = null;/已经访问的城市的编号int num = 0;/已经访问的城市的个数boolean isVisited

7、= null;/城市结点访问标志int fvalue = 0;/估计值public City(int city_num)id_list = new intcity_num + 1;isVisited = new booleancity_num;/主类public class TspAStar private int city_num = 0;private int city_distance = null;private int min_distance = 0;public TspAStar()input();min_distance = get_min_distance();/获取输入pr

8、ivate void input()JFileChooser fc = new JFileChooser();/文件选择对话框fc.setCurrentDirectory(new File(.);/从当前目录选择文件/获取输入源，输入源为选取的文件fc.addPropertyChangeListener(new PropertyChangeListener() /注册监听器public void propertyChange(PropertyChangeEvent arg0) /属性改变事件if (arg0.getPropertyName() = JFileChooser.SELECTED_F

9、ILE_CHANGED_PROPERTY) /选择单个文件try File file = (File) arg0.getNewValue();/获取属性的新值，转换为文件对象/-FileInputStream fi = new FileInputStream(file);InputStreamReader ir = new InputStreamReader(fi);BufferedReader br = new BufferedReader(ir);/-city_num = Integer.parseInt(br.readLine().trim();/读取城市的个数city_distance

10、 = new intcity_numcity_num;/城市之间的距离/读取城市之间的距离，保存在city_distanceString str_line = null;for (int i = 0; i city_num; i+) str_line = br.readLine();city_distancei = transfer(str_line.split( );fi.close();ir.close();br.close(); catch (Exception ep) /如果文件的内容不是全为数字，则弹出对话框JOptionPane.showMessageDialog(null,文件读

11、取异常，检查文件内容是否全为数字！););fc.showOpenDialog(null);/弹出打开文件对话框/将字符串形式的整数构成的数组转换为整数数组private int transfer(String str_arr)int size = str_arr.length;int int_arr = new intsize;for(int i = 0; i size; i +)int_arri = Integer.valueOf(str_arri);return int_arr;/获取所有路径中最短的路径private int get_min_distance()int row_num =

12、 city_distance.length;int col_num = city_distance0.length;int min = 0;for(int i = 0; i row_num; i +)for(int j = 0; j 0)/城市i和j不相同，并且存在路径if(min = 0 | (city_distanceij min)min = city_distanceij;return min;/获取gvaluepublic int get_gvalue(City city)int gvalue = 0;for(int i = 1; i city.num; i +)gvalue += c

13、ity_distancecity.id_listi-1city.id_listi-1-1;return gvalue;/获取hvaluepublic int get_hvalue(int depth) return (city_num - depth)*min_distance;/A*算法public City AStar(int start)int i, j;/队列，队列中的元素按升序排列，用队列表示open表MyQueue open = new MyQueue(city_num);/向量，用向量表示close表Vector close = new Vector();/初始的城市结点City

14、 city = new City(city_num);city.id_listcity.num + = start;city.isVisitedstart - 1 = true;/如果城市编号为1，在数组的位置为0city.fvalue = get_gvalue(city) + get_hvalue(city.depth);/将开始结点放入open表open.queueIn(city);/如果open表不为空while(!open.isEmpty()/将open表的首元素放入close表City head_elem = open.queueOut();close.add(head_elem);

15、/如果当前结点是目标结点if(head_elem.num = city_num+1)break;if(head_elem.num = city_num)head_elem.isVisited0 = false;/如果不是目标结点，扩展当前结点Vector v = new Vector();for(i = 0; i 0 & !head_elem.isVisitedi) /生成新的结点City new_city = new City(city_num);/新结点的深度new_city.depth = head_elem.depth + 1;/新结点的已访问结点列表for(j = 0; j head

16、_elem.num; j +)new_city.id_listj = head_elem.id_listj;new_city.num = head_elem.num;new_city.id_listnew_city.num + = i+1;/0行表示第1个结点/各个结点的访问状态int len = head_elem.isVisited.length;for(j = 0; j len; j +)new_city.isVisitedj = head_elem.isVisitedj;new_city.isVisitedi = true;/新结点的估计值fvaluenew_city.fvalue =

17、 get_gvalue(new_city) + get_hvalue(new_city.depth);v.addElement(new_city);/*System.out.print(new_city.id_listnew_city.num-1 + );*/while(!open.isEmpty()v.addElement(open.queueOut();/*int size = v.size();System.out.println(size);for(i = 0; i size; i +)City c = v.get(i);System.out.print(c.id_listc.num-

18、1 + );*/open = sort(v);return close.lastElement();/对City数组按city.fvalue升序进行排列public MyQueue sort(Vector v)int i, j;/获取对应的fvalue的值int size = v.size();/*System.out.println(size = + size);*/int fvalue_arr = new intsize;for(i = 0; i size; i +)fvalue_arri = v.get(i).fvalue;/*System.out.println(i + +fvalue

19、_arri);*/获取fvalue_arr的元素升序排列后的下标int count = 0;int index_of_fvalue = new intsize;boolean bool = new booleansize; for(i = 0; i size; i +)count = 0;for(j = 0; j size; j +)/比fvalue_arri小或与之相等的数的个数if(i != j & fvalue_arrj = fvalue_arri)count +;while(boolcount)count -;index_of_fvaluei = count;/第i个城市结点排序后的下

20、标boolcount = true;/*System.out.println(index_of_fvaluei);*/对City数组按city.fvalue升序进行排列City city_array = new Citysize;for(i = 0; i size; i +)city_arrayindex_of_fvaluei = v.get(i);/将排好序的city_arr的元素俺从小到大的循序进入队列MyQueue queue = new MyQueue(city_num);for(i = 0; i size; i +)queue.queueIn(city_arrayi);return

21、queue;/输出结果public void output(City city)int size = city.num;City final_city = city;File f = null;FileWriter fw = null;PrintWriter pw = null;try f = new File(./tspByAStar.txt);fw = new FileWriter(f);pw = new PrintWriter(fw);/获取最佳路径pw.write(最佳路径：);pw.println();for(int i = 0; i );pw.write( + final_city

22、.id_list0);/最佳路径上每两个城市间的距离pw.println();pw.println();pw.write(最佳路径上每两个城市间的距离为：);pw.println();int sum = 0, start = 0, end = 0;for (int i = 1; i + end + : + city_distancestart-1end-1);pw.println();sum += city_distancestart-1end-1;/最短距离pw.println();pw.write(最短距离为： + sum);pw.close();fw.close(); catch (Ex

23、ception e) e.printStackTrace();/主函数public static void main(String args)int start = 5;/出发城市编号TspAStar tsp = new TspAStar();City city = tsp.AStar(start);tsp.output(city);2、MyQueuepackage .tspByHdy;public class MyQueue private int capacity = 0;/队列的容量private int size = 0;/队列的元素个数private int head = 0;/队列的首元素下标private int tail = 0;/(队列的尾元素下标+1)%sizeprivate T pointer = null;/存放队列元素的下标/构造函数public MyQueue(int capacity)this.capacity = capacity;pointer = (T) new Objectcapacity;/判断队列是否为空public boolean isEmpty()if(head = tail)return true;return fal