回溯法有“通用的解题法”之称。应用回溯法解问题时，首先应该明确问题的解空间。一个复杂问题的解决往往由多部分构成，即，一个大的解决方案可以看作是由若干个小的决策组成。很多时候它们构成一个决策序列。解决一个问题的所有可能的决策序列构成该问题的解空间。解空间中满足约束条件的决策序列称为可行解。一般说来，解任何问题都有一个目标，在约束条件下使目标达优的可行解称为该问题的最优解。在解空间中，前 k 项决策已经确定的所有决策序列之集称为 k 定子解空间。 0 定子解空间即是该问题的解空间。
旅行商问题：某售货员要到若干个城市去推销商品。已知各个城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使得总的路程（或总旅费）最短。
我们用一个带权图 G(V, E) 来表示，顶点代表城市，边表示城市之间的道路。图中各边所带的权即是城市间的距离（或城市间的旅费）。则旅行商问题即是：在带权图 G 中找到一条路程最短的周游路线，即权值之和最小的 Hamilton 圈。
如果假定城市 A 是驻地。则推销员从 A 地出发，第一站有 3 种选择：城市 B 、 C 或城市 D ；第一站选定后，第二站有两种选择：如第一站选定 B ，则第二站只能选 C 、 D 两者之一。当第一、第二两站都选定时，第三站只有一种选择：比如，当第一、第二两站先后选择了 B 和 C 时，第三站只能选择 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("最小费用为:"+Traveling.bestc);
- System.out.println("所经节点为：");
- for(int i=1;i<=n;i++)
- System.out.print(+Traveling.bestx [i]+"\t");
- System.out.print("1");
- }
-
- }
|
