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

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

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

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

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

7、= null;/城市結(jié)點(diǎn)訪問標(biāo)志int fvalue = 0;/估計(jì)值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();/文件選擇對(duì)話框fc.setCurrentDirectory(new File(.);/從當(dāng)前目錄選擇文件/獲取輸入源，輸入源為選取的文件fc.addPropertyChangeListener(new PropertyChangeListener() /注冊(cè)監(jiān)聽器public void propertyChange(PropertyChangeEvent arg0) /屬性改變事件if (arg0.getPropertyName() = JFileChooser.SELECTED_F

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

11、取異常，檢查文件內(nèi)容是否全為數(shù)字！););fc.showOpenDialog(null);/彈出打開文件對(duì)話框/將字符串形式的整數(shù)構(gòu)成的數(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;/隊(duì)列，隊(duì)列中的元素按升序排列，用隊(duì)列表示open表MyQueue open = new MyQueue(city_num);/向量，用向量表示close表Vector close = new Vector();/初始的城市結(jié)點(diǎn)City

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

15、/如果當(dāng)前結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)if(head_elem.num = city_num+1)break;if(head_elem.num = city_num)head_elem.isVisited0 = false;/如果不是目標(biāo)結(jié)點(diǎn)，擴(kuò)展當(dāng)前結(jié)點(diǎn)Vector v = new Vector();for(i = 0; i 0 & !head_elem.isVisitedi) /生成新的結(jié)點(diǎn)City new_city = new City(city_num);/新結(jié)點(diǎn)的深度new_city.depth = head_elem.depth + 1;/新結(jié)點(diǎn)的已訪問結(jié)點(diǎn)列表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個(gè)結(jié)點(diǎn)/各個(gè)結(jié)點(diǎn)的訪問狀態(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é)點(diǎn)的估計(jì)值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();/對(duì)City數(shù)組按city.fvalue升序進(jìn)行排列public MyQueue sort(Vector v)int i, j;/獲取對(duì)應(yīng)的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的元素升序排列后的下標(biāo)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ù)的個(gè)數(shù)if(i != j & fvalue_arrj = fvalue_arri)count +;while(boolcount)count -;index_of_fvaluei = count;/第i個(gè)城市結(jié)點(diǎn)排序后的下

20、標(biāo)boolcount = true;/*System.out.println(index_of_fvaluei);*/對(duì)City數(shù)組按city.fvalue升序進(jìn)行排列City city_array = new Citysize;for(i = 0; i size; i +)city_arrayindex_of_fvaluei = v.get(i);/將排好序的city_arr的元素俺從小到大的循序進(jìn)入隊(duì)列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);/最佳路徑上每?jī)蓚€(gè)城市間的距離pw.println();pw.println();pw.write(最佳路徑上每?jī)蓚€(gè)城市間的距離為：);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ā)城市編號(hào)TspAStar tsp = new TspAStar();City city = tsp.AStar(start);tsp.output(city);2、MyQueuepackage .tspByHdy;public class MyQueue private int capacity = 0;/隊(duì)列的容量private int size = 0;/隊(duì)列的元素個(gè)數(shù)private int head = 0;/隊(duì)列的首元素下標(biāo)private int tail = 0;/(隊(duì)列的尾元素下標(biāo)+1)%sizeprivate T pointer = null;/存放隊(duì)列元素的下標(biāo)/構(gòu)造函數(shù)public MyQueue(int capacity)this.capacity = capacity;pointer = (T) new Objectcapacity;/判斷隊(duì)列是否為空public boolean isEmpty()if(head = tail)return true;return fal