旅行商问题-4080405-师鹏飞.docx

人工智能作业系 别电子信息系专 业计算机科学与技术班级学号4080405姓 名师鹏飞2011年 05 月 04A算法解决旅行商问题一问题描述二算法描述1.输入城市的个数n，输入城市间的权值。2.获取第一个节点，然后开始扩展节点。3.将获取的节点放入openList表中,从表中选取出估值最小的节点，并从表中删除该节点。4.获取已访问过的节点的个数num，如果numn，则找到最佳路径，转向7。5.如果num=n，则还需访问一个节点到达目标节点，则转向3。6.如果numn，则转向3。7.获取最后一个节点，通过其父节点递归的打印出最佳路径等。三估值函数描述 f=h+g，h=h*;g:从开始节点到n节点的代价，等于权值的和。h:从n节点到目标节点的代价。min * (n - deep)：n代表节点的个数，deep代表当前节点的深度，min代表当前节点到目标节点所有路径的最小代价。则min * (n - deep)代表从当前节点n到目标节点的路径长度的最小估计值。四主要主句结构的描述pathLen：以二维数组的形式存放各节点路径的权值。pathcity：存放放入路径中城市的编号。openList：存放所有生成而为考察的节点。Class City：城市类：num表示已经访问过的城市节点的个数；deep表示当前节点的深度，即第几个被访问的节点；gvalue表示从出发点到当前节点的代价；hvalue表示冲当前节点到目标节点的估值；father表示当前节点的父节点，即当前节点的上一级的节点。Class Tsp：算法类inputArray()：输入数组的方法，通过键盘输入初始化一个二维n阶数组。inputN()：输入节点总数的方法。getHvalue(int i, int deep)：得到代价估值的方法，通过节点总数，当前深度和最小代价之得到代价估值。extendCity(City firstc)：扩展节点的方法。printCityway(City city)：打印路径结果方法，通过最终节点与其父节点递归的打印出结果。initOpenList()：初始化openList表的方法。五运行结果。六总结 A算法是一种启发式的算法，解决旅行商问题比较实用。A算法并没有搜索所有的解空间，而是构造了一个估值函数，通过估值函数的值来缩小解空间，效率比较高。显然构造估值函数是相当重要的。 A算法总是从open表中选取估值最小的状态进行扩展，但是有时会出现错误。但是A算法有容错的能力，当出现错误的时候，能从不理想的状态跳到正确的状态。 七源代码城市类：public class City int num = 1; / 已经访问的城市的个数 int deep = 0; /当前深度double gvalue = 0;/开始节点到当前节点的代价double fvalue = 0; /当前节点到目标节点的代价估值City father = null;/当前节点的父节点Tsp类：import java.beans.PropertyChangeEvent;import java.beans.PropertyChangeListener;import java.io.BufferedReader;import java.io.File;import java.io.FileInputStream;import java.io.FileNotFoundException;import java.io.FileWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.PrintWriter;import java.util.Vector;import javax.swing.JFileChooser;import javax.swing.JOptionPane;public class Tsp private int pathLen = null;/ 以矩阵的形式各个城市之间的路程权值private int n;/ 城市个数private int pathcity = null;/ 记录放入路径的城市编号private Vector openList = null;/保存所有已生成而未考察的节点public void inputArray() /输入数组pathLen = new intnn;for (int i = 0; i n; i+) for (int j = i + 1; j n; j+) System.out.println(请输入 + (i + 1) + 点到 + (j + 1) + 点的权值);BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in);try pathLenij = Integer.parseInt(bufferedReader.readLine();pathLenji = pathLenij; catch (NumberFormatException e) e.printStackTrace(); catch (IOException e) e.printStackTrace();for (int i = 0; i n; i+) pathLenii = 0;public void inputN() /输入节点总数BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in);try System.out.println(请输入结点个数n的值：);n = Integer.parseInt(bufferedReader.readLine(); catch (NumberFormatException e) e.printStackTrace(); catch (IOException e) e.printStackTrace();inputArray();public double getHvalue(int i, int deep) / 得到H函数double min = -1;for (int j = 0; j pathLenij)min = pathLenij;return min * (n - deep);public City extendCity(City firstc) / 对城市节点进行扩展City nextc = firstc;City tempc = null;while (true) int num = 0;/ 访问过的节点数for (int i = 0; i n)/ 如果当前节点是目标节点break;if (num n) double hvalue = this.getHvalue(nextc.num - 1, nextc.deep + 1);for (int i = 0; i n; i+) if (i = nextc.num - 1)continue;if (pathcityi = 0)continue;tempc = new City();tempc.deep = nextc.deep + 1;tempc.num = i + 1;tempc.gvalue = nextc.gvalue + pathLennextc.num - 1i;tempc.fvalue = hvalue + tempc.gvalue;tempc.father = nextc;openList.add(tempc);if (num = n) tempc = new City();tempc.deep = nextc.deep + 1;tempc.num = pathcitynum;tempc.gvalue = nextc.gvalue + pathLennextc.num - 10;tempc.fvalue = tempc.gvalue;tempc.father = nextc;openList.add(tempc);int opensize = openList.size();int minf = 0;double f = 0;City acity = (City) openList.get(0);f = acity.fvalue;for (int i = 1; i acity.fvalue) f = acity.fvalue;minf = i;acity = nextc;while (acity != null) pathcityacity.num - 1 = acity.num;acity = acity.father;nextc = (City) openList.get(minf);openList.remove(minf);acity = nextc;while (acity != null) pathcityacity.num - 1 = 0;acity = acity.father;return nextc;public void printCityway(City city) /打印结果openList.removeAllElements();city = city.father;while (city != null) openList.add(city);city = city.father;int value = new intn + 1;for (int i = openList.size() - 1; i = 0; i-) city = (City) openList.get(i);System.out.print(city.num + - );valuen - 1 - i = city.num;System.out.println(1);valuen = 1;System.out.println(最佳路径上每两个城市间的距离为：);double sumf = 0;for (int i = 0; i + valuei + 1 + : + pathLenvaluei - 1valuei + 1 - 1);sumf += pathLenvaluei - 1valuei + 1 - 1;System.out.println(最短距离为： + sumf);public void findBestways(City firstc) / 寻找最佳路径City lastc = this.extendCity(firstc);this.printCityway(lastc);public void initOpenList() / 初始化openListthis.