|
|
回溯法有“通用的解題法”之稱。應(yīng)用回溯法解問題時(shí)，首先應(yīng)該明確問題的解空間。一個(gè)復(fù)雜問題的解決往往由多部分構(gòu)成，即，一個(gè)大的解決方案可以看作是由若干個(gè)小的決策組成。很多時(shí)候它們構(gòu)成一個(gè)決策序列。解決一個(gè)問題的所有可能的決策序列構(gòu)成該問題的解空間。解空間中滿足約束條件的決策序列稱為可行解。一般說來，解任何問題都有一個(gè)目標(biāo)，在約束條件下使目標(biāo)達(dá)優(yōu)的可行解稱為該問題的最優(yōu)解。在解空間中，前 k 項(xiàng)決策已經(jīng)確定的所有決策序列之集稱為 k 定子解空間。 0 定子解空間即是該問題的解空間。
旅行商問題：某售貨員要到若干個(gè)城市去推銷商品。已知各個(gè)城市之間的路程（或旅費(fèi)）。他要選定一條從駐地出發(fā)，經(jīng)過每個(gè)城市一次，最后回到駐地的路線，使得總的路程（或總旅費(fèi)）最短。
我們用一個(gè)帶權(quán)圖 G(V, E) 來表示，頂點(diǎn)代表城市，邊表示城市之間的道路。圖中各邊所帶的權(quán)即是城市間的距離（或城市間的旅費(fèi)）。則旅行商問題即是：在帶權(quán)圖 G 中找到一條路程最短的周游路線，即權(quán)值之和最小的 Hamilton 圈。
如果假定城市 A 是駐地。則推銷員從 A 地出發(fā)，第一站有 3 種選擇：城市 B 、 C 或城市 D ；第一站選定后，第二站有兩種選擇：如第一站選定 B ，則第二站只能選 C 、 D 兩者之一。當(dāng)?shù)谝弧⒌诙䞍烧径歼x定時(shí)，第三站只有一種選擇：比如，當(dāng)?shù)谝弧⒌诙䞍烧鞠群筮x擇了 B 和 C 時(shí)，第三站只能選擇 D 。最后推銷員由城市 D 返回駐地 A 。
用JAVA解決，代碼如下：- public class Traveling {
- public static int NUM = 4;
- public static int n = NUM;
- public static int NoEdge=1000;
- public static int x[] = new int [NUM+1];
- public static int bestx[] = new int [NUM+1];
- public static int a[][] ={{},
- {0,0 , 30 , 6 , 4 } ,
- {0,30 , 0 , 5 , 10 } ,
- {0,6 , 5 , 0 , 20 } ,
- {0,4 , 10 , 20, 0} ,
- };
- public static int cc =0;
- public static int bestc=1000;
-
- public static int TSP(int a[][],int v[],int n,int NoEdge){
- return 0 ;
-
- }
- private static void Backtrack(int i){
- if(i==n){
- if(a[x[n-1]][x[n]] != NoEdge &&
- a[x[n]][1] != NoEdge &&
- (cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc||bestc == NoEdge)){
- for(int j=1 ; j<=n; j++)
- bestx[j] = x[j];
- bestc = cc+ a[x[n-1]][x[n]] + a[x[n]][1];
- }
- }
- else{
- for(int j = i ; j<=n ;j++)
- if(a[x[i-1]][x[j]]!= NoEdge && (cc+a[x[i-1]][x[i]] < bestc||bestc == NoEdge)){
- int t = x[i];x[i]=x[j];x[j]=t;
- cc+=a[x[i-1]][x[i]];
- Backtrack(i+1);
- cc -= a[x[i-1]][x[i]];
- t = x[i];x[i]=x[j];x[j]=t;
- }
- }
- }
- public static void main(String[] args) {
- // TODO Auto-generated method stub
- for(int i=1;i<=n;i++)
- x[i] = i;
- Backtrack(2);
- for(int i=1;i<=n;i++){
- for(int j=1;j<=n;j++)
- System.out.print(a[i][j]+"\t");
- System.out.println();
- }
-
- System.out.println("最小費(fèi)用為:"+Traveling.bestc);
- System.out.println("所經(jīng)節(jié)點(diǎn)為：");
- for(int i=1;i<=n;i++)
- System.out.print(+Traveling.bestx [i]+"\t");
- System.out.print("1");
- }
-
- }
|
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
