A星算法求解旅行商問題

1、Astar算法求解旅行商問題一、問題描述一共有n個城市，某推銷員從其中的一個城市A出發(fā)經(jīng)過每個城市一次且僅一次后回到A，求代價最小的路徑。二、知識表示1、狀態(tài)表示初始狀態(tài)，目標狀態(tài)。初始狀態(tài)：A（出發(fā)城市）目標狀態(tài)：A，（n-1）個城市），A2、算法描述（1）設城市結(jié)點的個數(shù)為n，獲取開始結(jié)點，計算所有成員變量的值，將開始結(jié)點放入open表（open表用隊列實現(xiàn)）；（2）如果 open表不為空，轉(zhuǎn)（3），否則轉(zhuǎn)（7）；（3）將open表中的首元素放入close表，并將該首元素從open表中刪除。（4）獲取已訪問結(jié)點的個數(shù)num，如果num n+1，則找到最佳路徑，轉(zhuǎn)（7）；（5）如果num=n

2、，還訪問一個結(jié)點到達目標結(jié)點，設置初始結(jié)點的訪問狀態(tài)isVisited0的值為false，表示初始結(jié)點沒有被訪問，即可以回到出發(fā)點；（6）如果numn，將從當前結(jié)點出發(fā)可訪問的結(jié)點和open表中剩余的結(jié)點放入一個向量vector中，根據(jù)每個結(jié)點的fvalue值按升序排列，排列的結(jié)果按升序放入open表，轉(zhuǎn)（2）； （7）獲取close表中的最后一個元素，打印最佳路徑，相鄰城市之間的距離，最短的距離值。3、估價函數(shù)f(n)=g(n)+h(n) ，h(n)h*(n)。g(n)：從開始結(jié)點到當前結(jié)點n的實際距離，等于路徑的權值的和。h(n)：假設城市結(jié)點n的深度為depth，城市的個數(shù)為city_n

3、um，(city_num-depth)表示從n到目標城市還需要的路徑個數(shù)，min表示所有路徑長度的最小值，則h(n)=min*(city_num-deep)表示從當前城市結(jié)點n到目標結(jié)點的路徑長度的最小估計值，h(n)h*(n)顯然對于任意的一個城市結(jié)點都成立。三、算法實現(xiàn)主要的數(shù)據(jù)結(jié)構城市結(jié)點：depth表是從開始城市到當前城市，訪問的城市個數(shù)，也可以稱為深度；num表示已訪問的城市結(jié)點的個數(shù)； id_list是一個數(shù)組，表示從開始城市到當前城市的所有城市的編號的集合，編號的值從1開始；isVisited是一個布爾數(shù)組，記錄當前城市結(jié)點到目標城市結(jié)點的訪問狀態(tài)，布爾值為false，表示可訪問

4、；fvalue表示從開始城市出發(fā)回到原點的估計值。城市之間的距離：通過n*n矩陣city_distance表示，其中n表示城市的個數(shù)。編號為k的城市到各個城市之間的距離可以從第（k-1）行獲取。open表：用隊列表示，城市結(jié)點進入隊列之前需要根據(jù)估計值fvalue按升序排列。 close表：用向量表示。搜索圖：搜索圖通過open表構建，將路徑的編號保存在一個數(shù)組id_list中。四、實驗結(jié)果和分析1、輸入數(shù)據(jù)第一行的數(shù)值8表示城市結(jié)點的個數(shù)，后面是一個8*8的數(shù)組，數(shù)組的值表示城市之間的距離。任何一個結(jié)點到自身的距離是0，數(shù)組中的第0行表示第1個城市到各個城市之間的距離，其他的可類推。2、用戶

5、界面3、運行結(jié)果通過驗證，運行結(jié)果和期望值一致。由于每個城市結(jié)點需要保存之前的路徑，因此增加了空間復雜度。五、程序一共有三個類，City，TspAStar，MyQueue，City是TspAStar的內(nèi)部類。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;/城市結(jié)點類，表示訪問到中間某個城市的狀態(tài)class Cityint depth = 0;/當前深度int id_list = null;/已經(jīng)訪問的城市的編號int num = 0;/已經(jīng)訪問的城市的個數(shù)boolean isVisited

7、= null;/城市結(jié)點訪問標志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() /注冊監(jiān)聽器public void propertyChange(PropertyChangeEvent arg0) /屬性改變事件if (arg0.getPropertyName() = JFileChooser.SELECTED_F

9、ILE_CHANGED_PROPERTY) /選擇單個文件try File file = (File) arg0.getNewValue();/獲取屬性的新值，轉(zhuǎn)換為文件對象/-FileInputStream fi = new FileInputStream(file);InputStreamReader ir = new InputStreamReader(fi);BufferedReader br = new BufferedReader(ir);/-city_num = Integer.parseInt(br.readLine().trim();/讀取城市的個數(shù)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) /如果文件的內(nèi)容不是全為數(shù)字，則彈出對話框JOptionPane.showMessageDialog(null,文件讀

11、取異常，檢查文件內(nèi)容是否全為數(shù)字！););fc.showOpenDialog(null);/彈出打開文件對話框/將字符串形式的整數(shù)構成的數(shù)組轉(zhuǎn)換為整數(shù)數(shù)組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();/初始的城市結(jié)點City

14、 city = new City(city_num);city.id_listcity.num + = start;city.isVisitedstart - 1 = true;/如果城市編號為1，在數(shù)組的位置為0city.fvalue = get_gvalue(city) + get_hvalue(city.depth);/將開始結(jié)點放入open表open.queueIn(city);/如果open表不為空while(!open.isEmpty()/將open表的首元素放入close表City head_elem = open.queueOut();close.add(head_elem);

15、/如果當前結(jié)點是目標結(jié)點if(head_elem.num = city_num+1)break;if(head_elem.num = city_num)head_elem.isVisited0 = false;/如果不是目標結(jié)點，擴展當前結(jié)點Vector v = new Vector();for(i = 0; i 0 & !head_elem.isVisitedi) /生成新的結(jié)點City new_city = new City(city_num);/新結(jié)點的深度new_city.depth = head_elem.depth + 1;/新結(jié)點的已訪問結(jié)點列表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個結(jié)點/各個結(jié)點的訪問狀態(tài)int len = head_elem.isVisited.length;for(j = 0; j len; j +)new_city.isVisitedj = head_elem.isVisitedj;new_city.isVisitedi = true;/新結(jié)點的估計值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數(shù)組按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小或與之相等的數(shù)的個數(shù)if(i != j & fvalue_arrj = fvalue_arri)count +;while(boolcount)count -;index_of_fvaluei = count;/第i個城市結(jié)點排序后的下

20、標boolcount = true;/*System.out.println(index_of_fvaluei);*/對City數(shù)組按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;/輸出結(jié)果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();/主函數(shù)public static void main(String args)int start = 5;/出發(fā)城市編號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;/隊列的元素個數(shù)private int head = 0;/隊列的首元素下標private int tail = 0;/(隊列的尾元素下標+1)%sizeprivate T pointer = null;/存放隊列元素的下標/構造函數(shù)public MyQueue(int capacity)this.capacity = capacity;pointer = (T) new Objectcapacity;/判斷隊列是否為空public boolean isEmpty()if(head = tail)return true;return fal