当前位置:首页 > 行业资料 > 交通运输 > 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)如果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和TspAStarpackagehrbeu.edu.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_distanceStringstr_line=null;for(inti=0;icity_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;isize;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;irow_num;i++){for(intj=0;jcol_num;j++){if(city_distance[i][j]0){//城市i和j不相同,并且存在路径if(min==0||(city_distance[i][j]min)){min=city_distance[i][j];}}}}returnmin;}//获取gvaluepublicintget_gvalue(Citycity){intgvalue=0;for(inti=1;icity.num;i++){gvalue+=city_distance[city.id_list[i]-1][city.id_list[i-1]-1];}returngvalue;}//获取hvaluepublicintget_hvalue(intdepth){return(city_num-depth)*min_distance;}//A*算法publicCityAStar(intstart){inti,j;//队列,队列中的元素按升序排列,用队列表示open表MyQueueCityopen=newMyQueueCity(city_num);//向量,用向量表示close表VectorCityclose=newVectorCity();//初始的城市结点Citycity=newCity(city_num);city.id_list[city.num++]=start;city.isVisited[start-1]=true;//如果城市编号为1,在数组的位置为0city.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;}//如果不是目标结点,扩展当前结点VectorCityv=newVectorCity();for(i=0;icity_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;jhead_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;jlen;j++){new_city.isVisited[j]=head_elem.isVisited[j];}new_city.isVisited[i]=true;//新结点的估计值fvaluenew_city.fvalue=get_gvalue(new_city)+get_hvalue(new
本文标题:A星算法求解旅行商问题
链接地址:https://www.777doc.com/doc-5657346 .html