A星算法求解旅行商问题

精选优质文档-----倾情为你奉上精选优质文档-----倾情为你奉上专心---专注---专业专心---专注---专业精选优质文档-----倾情为你奉上专心---专注---专业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，还访问一个结点到达目标结点，设置初始结点的访问状态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按升序排列。close表：用向量表示。搜索图：搜索图通过open表构建，将路径的编号保存在一个数组id_list中。四、实验结果和分析1、输入数据 第一行的数值8表示城市结点的个数，后面是一个8*8的数组，数组的值表示城市之间的距离。任何一个结点到自身的距离是0，数组中的第0行表示第1个城市到各个城市之间的距离，其他的可类推。2、用户界面3、运行结果通过验证，运行结果和期望值一致。由于每个城市结点需要保存之前的路径，因此增加了空间复杂度。五、程序一共有三个类，City，TspAStar，MyQueue，City是TspAStar的内部类。1、City和TspAS.tspByHdy;importjava.beans.PropertyChangeEvent;importjava.beans.PropertyChangeListener;importjava.io.BufferedReader;importjava.io.File;importjava.io.FileInputStream;importjava.io.FileWriter;importjava.io.InputStreamReader;importjava.io.PrintWriter;importjava.util.Vector;importjavax.swing.JFileChooser;importjavax.swing.JOptionPane;//城市结点类，表示访问到中间某个城市的状态classCity{ intdepth=0;//当前深度 int[]id_list=null;//已经访问的城市的编号 intnum=0;//已经访问的城市的个数 boolean[]isVisited=null;//城市结点访问标志 intfvalue=0; //估计值 publicCity(intcity_num){ id_list=newint[city_num+1]; isVisited=newboolean[city_num]; }}//主类publicclassTspAStar{ privateintcity_num=0; privateint[][]city_distance=null; privateintmin_distance=0; publicTspAStar(){ input(); min_distance=get_min_distance(); } //获取输入 privatevoidinput(){ JFileChooserfc=newJFileChooser();//文件选择对话框 fc.setCurrentDirectory(newFile("."));//从当前目录选择文件 //获取输入源，输入源为选取的文件 fc.addPropertyChangeListener(newPropertyChangeListener(){//注册监听器 publicvoidpropertyChange(PropertyChangeEventarg0){//属性改变事件 if(arg0.getPropertyName()==JFileChooser.SELECTED_FILE_CHANGED_PROPERTY){//选择单个文件 try{ Filefile=(File)arg0.getNewValue();//获取属性的新值，转换为文件对象 //------------------------------------ FileInputStreamfi=newFileInputStream(file); InputStreamReaderir=newInputStreamReader(fi); BufferedReaderbr=newBufferedReader(ir); //------------------------------------ city_num=Integer.parseInt(br.readLine().trim());//读取城市的个数 city_distance=newint[city_num][city_num];//城市之间的距离 //读取城市之间的距离，保存在city_distance Stringstr_line=null; for(inti=0;i<city_num;i++){ str_line=br.readLine(); city_distance[i]=transfer(str_line.split("")); } fi.close(); ir.close(); br.close(); }catch(Exceptionep){//如果文件的内容不是全为数字，则弹出对话框 JOptionPane.showMessageDialog(null, "文件读取异常，检查文件内容是否全为数字！"); } } } }); fc.showOpenDialog(null);//弹出"打开文件"对话框 } //将字符串形式的整数构成的数组转换为整数数组 privateint[]transfer(String[]str_arr){ intsize=str_arr.length; int[]int_arr=newint[size]; for(inti=0;i<size;i++){ int_arr[i]=Integer.valueOf(str_arr[i]); } returnint_arr; } //获取所有路径中最短的路径 privateintget_min_distance(){ introw_num=city_distance.length; intcol_num=city_distance[0].length; intmin=0; for(inti=0;i<row_num;i++){ for(intj=0;j<col_num;j++){ if(city_distance[i][j]>0){//城市i和j不相同，并且存在路径 if(min==0||(city_distance[i][j]<min)){ min=city_distance[i][j]; } } } } returnmin; } //获取gvalue publicintget_gvalue(Citycity){ intgvalue=0; for(inti=1;i<city.num;i++){ gvalue+=city_distance[city.id_list[i]-1][city.id_list[i-1]-1]; } returngvalue; } //获取hvalue publicintget_hvalue(intdepth){ return(city_num-depth)*min_distance; } //A*算法 publicCityAStar(intstart){ inti,j; //队列，队列中的元素按升序排列，用队列表示open表 MyQueue<City>open=newMyQueue<City>(city_num); //向量，用向量表示close表 Vector<City>close=newVector<City>(); //初始的城市结点 Citycity=newCity(city_num); city.id_list[city.num++]=start; city.isVisited[start-1]=true;//如果城市编号为1，在数组的位置为0 city.fvalue=get_gvalue(city)+get_hvalue(city.depth); //将开始结点放入open表 open.queueIn(city); //如果open表不为空 while(!open.isEmpty()){ //将open表的首元素放入close表 Cityhead_elem=open.queueOut(); close.add(head_elem); //如果当前结点是目标结点 if(head_elem.num>=city_num+1){ break; } if(head_elem.num==city_num){ head_elem.isVisited[0]=false; } //如果不是目标结点，扩展当前结点 Vector<City>v=newVector<City>(); for(i=0;i<city_num;i++){ intid=head_elem.num-1; //扩展存在路径并且没有被访问过的结点 if(city_distance[head_elem.id_list[id]-1][i]>0&&!head_elem.isVisited[i]){ //生成新的结点 Citynew_city=newCity(city_num); //新结点的深度 new_city.depth=head_elem.depth+1; //新结点的已访问结点列表 for(j=0;j<head_elem.num;j++){ new_city.id_list[j]=head_elem.id_list[j]; } new_city.num=head_elem.num; new_city.id_list[new_city.num++]=i+1;//0行表示第1个结点 //各个结点的访问状态 intlen=head_elem.isVisited.length; for(j=0;j<len;j++){ new_city.isVisited[j]=head_elem.isVisited[j]; } new_city.isVisited[i]=true; //新结点的估计值fvalue new_city.fvalue=get_gvalue(new_city)+get_hvalue(new_city.depth); v.addElement(new_city); /*System.out.print(new_city.id_list[new_city.num-1]+"");*/ } } while(!open.isEmpty()){ v.addElement(open.queueOut()); } /*intsize=v.size(); System.out.println(size); for(i=0;i<size;i++){ Cityc=v.get(i); System.out.print(c.id_list[c.num-1]+""); }*/ open=sort(v); } returnclose.lastElement(); } //对City数组按city.fvalue升序进行排列 publicMyQueue<City>sort(Vector<City>v){ inti,j; //获取对应的fvalue的值 intsize=v.size(); /*System.out.println("size="+size);*/ int[]fvalue_arr=newint[size]; for(i=0;i<size;i++){ fvalue_arr[i]=v.get(i).fvalue; /*System.out.println(i+""+fvalue_arr[i]);*/ } //获取fvalue_arr的元素升序排列后的下标 intcount=0; int[]index_of_fvalue=newint[size]; boolean[]bool=newboolean[size]; for(i=0;i<size;i++){ count=0; for(j=0;j<size;j++){//比fvalue_arr[i]小或与之相等的数的个数 if(i!=j&&fvalue_arr[j]<=fvalue_arr[i]){ count++; } } while(bool[count]){ count--; } index_of_fvalue[i]=count; //第i个城市结点排序后的下标 bool[count]=true; /*System.out.println(index_of_fvalue[i]);*/ } //对City数组按city.fvalue升序进行排列 City[]city_array=newCity[size]; for(i=0;i<size;i++){ city_array[index_of_fvalue[i]]=v.get(i); } //将排好序的city_arr的元素俺从小到大的循序进入队列 MyQueue<City>queue=newMyQueue<City>(city_num); for(i=0;i<size;i++){ queue.queueIn(city_array[i]); } returnqueue; } //输出结果 publicvoidoutput(Citycity){ intsize=city.num; Cityfinal_city=city; Filef=null; FileWriterfw=null; PrintWriterpw=null; try{ f=newFile("./tspByAStar.txt"); fw=newFileWriter(f); pw=newPrintWriter(fw); //获取最佳路径 pw.write("最佳路径："); pw.println(); for(inti=0;i<city_num;i++){ pw.write(final_city.id_list[i]+"--->"); } pw.write(""+final_city.id_list[0]); //最佳路径上每两个城市间的距离 pw.println(); pw.println(); pw.write("最佳路径上每两个城市间的距离为："); pw.println(); intsum=0,start=0,end=0; for(inti=1;i<size;i++){ start=final_city.id_list[i-1]; end=final_city.id_list[i]; pw.write(start+"--->"+end+":"+city_distance[start-1][end-1]); pw.println(); sum+=city_distance[start-1][end-1]; } //最短距离 pw.println(); pw.write("最短距离为："+sum); pw.close(); fw.close(); }catch(Exceptione){ e.printStackTrace(); } } //主函数 publicstaticvoidmain(String[]args){ intstart=5; //出发城市编号 TspAStartsp=newTspAStar(); Citycity=tsp.AStar(start); tsp.output(city); }}2、MyQ.tspByHdy;publicclassMyQueue<T>{ privateintcapacity=0; //队列的容量 privateintsize=0; //队列的元素个数 privateinthead=0; //队列的首元素下标 privateinttail=0; //(队列的尾元素下标+1)%size privateT[]pointer=null; //存放队列元素的下标 //构造函数 publicMyQueue(intcapacity){ this.capacity=capacity; pointer=(T[])newObject[capacity]; } //判断队列是否为空 publicbooleanisEmpty(){ if(head==tail) returntru