旅行商問題分析（分支限界法）

一、題目二、思路 1、dfs 實驗要求用多種思路完成，所以一開始就沿用了上一個實驗馬走棋盤的思路，添加了鄰接矩陣來記錄有向網的權值。總體思路還是DFS遍歷搜索。過程剪枝： 1、因為要求為最短路徑，而一般情況總會存在多條可行路徑，在判斷過程中需要走過每一條路徑才能知道該路徑的長度，但如果已知一條可 ...

一、題目

二、思路

1、dfs

實驗要求用多種思路完成，所以一開始就沿用了上一個實驗馬走棋盤的思路，添加了鄰接矩陣來記錄有向網的權值。總體思路還是DFS遍歷搜索。

過程剪枝：

1、因為要求為最短路徑，而一般情況總會存在多條可行路徑，在判斷過程中需要走過每一條路徑才能知道該路徑的長度，但如果已知一條可行路徑的長度，在計算另一條路徑的時候，若還未完成巡迴但此時路徑長度已經大於已知最短可行路徑，那麼這條路的最終長度就必定大於已知最短路徑，此時就可以不必接下去計算當前路徑。

2、之前得出的路徑長度可以幫助之後的路徑進行快速判斷，如果我們儘早得出較短的可行路徑，之後的工作也會進行得更快，由剪枝1引出剪枝2，每次選擇到下一點路徑長度最短的點前進，這樣就能較快得到較短的可行路徑。

2、分支限界法

　　按照書本上教我們的思路來實現分支限界法，首先對鄰接矩陣進行初始化，求出其的最小下界和對應的矩陣，然後以這個矩陣為根節點，開始進行類似二叉樹的遍歷。

　　在這個過程中，需要保持矩陣每行或每列都必須有一個以上的0，還需要一個函數來找出所有行中最小數中最大的。然後下一步就要決定是否走該行距離為0的點，如果選擇走，就將點對應的行和列去掉，若不選擇該點，則將該點置為無窮大。並比較選與不選情況下的下界變化，選擇下界較小的情況繼續進行遞歸處理，直到矩陣消失或剩下全為無窮大的不可到達點。

　　遇到問題：根據以上的邏輯，在實際解決過程中，出現了爆棧的情況，通過調試發現程式運行情況和書本上不一樣，書本上有一些變化並沒有說明清楚，那麼就需要重新考慮程式的遞歸出口解決爆棧問題。

最後根據書上的情況得修改為一共三種遞歸出口判斷：

1、若剩下的全是無窮遠或0（預設跳過-1即不存在的）

2、若剩下全是無窮遠

3、若剩下全是0

若滿足以上任意一種判斷，可以直接得出當前下界即為最短路徑。

三、複雜度分析

以DFS為主要演算法，O(e+v)

時間複雜度（V邊數+ E頂點數）

實際複雜度比上述要小，因為在實際中並不會完整遍歷所有可行路徑。

分支限界法完成比較匆忙，代碼中要多次迴圈遍曆數組，存在諸多冗餘，若不急迴圈，程式需要的步數及為頂點數，當不斷的迴圈判斷使得複雜度難以估計。

三、實現代碼

1、DFS

 1 public class Sell {
 2     static int[][] byGroup;// 鄰接矩陣
 3     static int[] visit;// 0表示未訪問 1表示訪問
 4     static int N;// 點的個數
 5     static int minstep = 10000;// 最小步數
 6 
 7     class ToNode {
 8         int n;// 第n個點
 9         int L;//// 當前點到第n個點的距離
10 
11         public ToNode(int n, int l) {
12             this.n = n;
13             this.L = l;
14         }
15     }
16 
17     public static Comparator<ToNode> LComparator = new Comparator<ToNode>() {// 優先隊列的比較方法（到下一點的距離近到遠
18         @Override
19         public int compare(ToNode tn1, ToNode tn2) {
20             return tn1.L - tn2.L;
21         }
22     };
23 
24     public void init() {
25         Scanner sc = new Scanner(System.in);
26         System.out.println("please int N:");
27         N = sc.nextInt();
28         byGroup = new int[N][N];
29         visit = new int[N];
30         for (int i = 0; i < N; i++) {
31             for (int j = 0; j < N; j++) {
32                 System.out.println("please int " + i + "-->" + j + " weight:");
33                 byGroup[i][j] = sc.nextInt();
34             }
35         }
36         DFS(0, 0);// 從0點開始
37     }
38 
39     public void DFS(int n, int step) {
40         if (visit[n] != 0 || step >= minstep) {// 當前點走過或當前已走長度大於已知最小可行長度
41             return;
42         }
43         if (step != 0) {// 第一次不賦值
44             visit[n] = 1;
45         }
46         int flag = 1;
47         for (int k = 0; k < visit.length; k++) {//判斷是否走完所有點
48             if (visit[n] == 0) {
49                 flag = 0;
50                 break;
51             }
52         }
53         if (flag == 1 && n == 0) {// 巡迴完成的判斷
54             System.out.println("巡迴完成");
55             if (step < minstep) {// 修改最短可行路徑長度
56                 minstep = step;
57             }
58             System.out.println("now donestep is:" + step);
59         }
60         Queue<ToNode> nodePriorityQueue = new PriorityQueue<>(N, LComparator);// 每次來個優先隊列從小到大
61         for (int i = 0; i < byGroup[0].length; i++) {
62             if (i != n) {
63                 nodePriorityQueue.add(new ToNode(i, byGroup[n][i]));
64             }
65         }
66         while (!nodePriorityQueue.isEmpty()) {// 回溯
67             ToNode tn = nodePriorityQueue.poll();
68             DFS(tn.n, step + tn.L);
69         }
70     }
71 
72     public static void main(String[] args) {
73         Sell s = new Sell();
74         s.init();
75         System.out.println("mini step is: " + minstep);
76     }
77 }

2、分支限界法

  1 public class Sell2 {
  2     static int[][] group = { { -2, 17, 7, 35, 18 }, { 9, -2, 5, 14, 19 }, { 29, 24, -2, 30, 12 },
  3             { 27, 21, 25, -2, 48 }, { 15, 16, 28, 18, -2 } };
  4     //-1表示不存在 -2表示無窮大到不了
  5     //static int[] flag;//初始化時判斷
  6     static int[] hmin;// 每行對應的最小值
  7     static int bound;
  8     static int N = 5;
  9     static int[] hz = new int[5];// 用來記錄該行是否已經全為-1
 10 
 11     public void init() {// 初始化分支界限樹的根節點
 12         Scanner sc = new Scanner(System.in);
 13         System.out.println("please int N:");
 14         // N = sc.nextInt();
 15         // group = new int[N][N];
 16         // group
 17         int[] flag = new int[N];
 18         hmin = new int[N];
 19         /*
 20          * for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) {
 21          * System.out.println("please int " + i + "-->" + j + " weight:"); group[i][j] =
 22          * sc.nextInt(); } }
 23          */
 24         int minh;
 25         for (int i = 0; i < group[0].length; i++) {// 對行找最小並減去
 26             minh = 10000;
 27             for (int j = 0; j < group[0].length; j++) {// 找當前行的最小值
 28                 if (group[i][j] != -1 && group[i][j] != -2 && group[i][j] < minh) {
 29                     minh = group[i][j];
 30                 }
 31             }
 32             bound += minh;
 33             for (int j = 0; j < group[0].length; j++) {// 對每個數減去最小值並給flag賦值
 34                 if (group[i][j] != -1 && group[i][j] != -2) {
 35                     group[i][j] -= minh;
 36                     if (group[i][j] == 0) {
 37                         flag[j] = 1;
 38                     }
 39                 }
 40             }
 41         }
 42         int minl;
 43         for (int i = 0; i < flag.length; i++) {
 44             if (flag[i] != 1) {// 第i列
 45                 minl = 10000;
 46                 for (int j = 0; j < group[0].length; j++) {// 找當前列的最小值
 47                     if (group[j][i] != -1 && group[j][i] != -2 && group[j][i] < minl) {
 48                         minl = group[j][i];
 49                     }
 50                 }
 51                 bound += minl;
 52                 for (int j = 0; j < group[0].length; j++) {// 對每個數減去最小值並給flag賦值
 53                     if (group[j][i] != -1 && group[i][j] != -2) {
 54                         group[j][i] -= minl;
 55                     }
 56                 }
 57             }
 58         }
 59     }
 60 
 61     int minh = 10000;
 62     int bigMin = 0;// 所有行的最小數中最大的
 63 
 64     public void tree() {
 65         System.out.println(bound);
 66         int x, y = 0;// 每次對應的要或不要的點(x,y)
 67         // ********************************************************如果
 68         if (isDone1() == 1 || isDone2() == 0 || isDone3() == 0) {// 判斷完成
 69             System.out.println("okk");
 70             System.exit(1);
 71         }
 72         x = findh();// 每行最小中最大的那個數的行
 73         for (int i = 0; i < N; i++) {
 74             if (group[x][i] == 0) {
 75                 y = i;
 76             }
 77         }
 78         if (need(x, y) > dontneed(x, y)) {// 不要這個點
 79             group[x][y] = -2;
 80             // 檢測每行是否都有0
 81             int havaz = 0;
 82             for (int i = 0; i < N; i++) {
 83                 havaz = 0;
 84                 for (int j = 0; j < N; j++) {
 85                     if (group[i][j] == 0) {
 86                         havaz = 1;// 有0
 87                     }
 88                 }
 89                 if (havaz == 0) {// 第i行沒0
 90                     bound += hmin[i];
 91                     for (int t = 0; t < N; t++) {
 92                         if (group[i][t] != -2 && group[i][t] != -1) {
 93                             group[i][t] -= hmin[i];
 94                         }
 95                     }
 96                 }
 97             }
 98             tree();// 遞歸
 99         } else {// 要這個點
100             hz[x] = 1;
101             if (group[y][x] != -1) {
102                 group[y][x] = -2;
103             }
104             for (int i = 0; i < N; i++) {// 把行消除
105                 group[x][i] = -1;
106             }
107             for (int i = 0; i < N; i++) {// 把列消除
108                 group[i][y] = -1;
109             }
110             // 檢測每行是否都有0
111             int havaz = 0;
112             for (int i = 0; i < N; i++) {
113                 if (hz[i] != 1) {
114                     havaz = 0;
115                     for (int j = 0; j < N; j++) {
116                         if (group[i][j] == 0) {
117                             havaz = 1;// 有0
118                         }
119                     }
120                     if (havaz == 0) {
121                         bound += hmin[i];
122                         for (int t = 0; t < N; t++) {
123                             if (group[i][t] != -2 && group[i][t] != -1) {
124                                 group[i][t] -= hmin[i];
125                             }
126                             // group[i][t] -= hmin[i];
127                         }
128                     }
129                 }
130 
131             }
132             tree();// 遞歸
133         }
134     }
135 
136     // 要和不要這個點對應的bound
137     private int need(int x, int y) {
138         int needbound = bound;
139         for (int i = 0; i < N; i++) {// 去掉行
140             group[x][i] = -1;
141         }
142         for (int i = 0; i < N; i++) {// 去掉列
143             group[i][y] = -1;
144         }
145         // 檢測每行是否都有0
146         int havaz;
147         for (int i = 0; i < N; i++) {
148             if (hz[i] != 1) {
149                 havaz = 0;
150                 for (int j = 0; j < N; j++) {
151                     if (group[i][j] == 0) {
152                         havaz = 1;// 有0
153                     }
154                 }
155                 if (havaz == 0) {
156                     needbound += hmin[i];
157                 }
158             }
159 
160         }
161         return needbound;
162     }
163 
164     private int dontneed(int x, int y) {
165         int dontneedbound = bound;
166         // 檢測每行是否都有0 (去掉xy點)
167         int havaz;
168         for (int i = 0; i < N; i++) {
169             if (hz[i] != 1) {
170                 havaz = 0;
171                 for (int j = 0; j < N; j++) {
172                     if (i != x && j != y && group[i][j] == 0) {
173                         havaz = 1;// 有0
174                     }
175                 }
176                 if (havaz == 0) {// 這行沒0
177                     dontneedbound += hmin[i];
178                 }
179             }
180         }
181         return dontneedbound;
182     }
183 
184     private int findh() {// 找出每行最小中最大的那個數在哪一行
185         int bigMin = 0;// 所有行的最小數中最大的
186         int minh, h = 0;
187         for (int i = 0; i < group[0].length; i++) {// 對行找最小並減去
188             if (hz[i] != 1) {
189                 minh = 10000;
190                 for (int j = 0; j < group[0].length; j++) {// 找當前行的最小值
191                     if (group[i][j] != -1 && group[i][j] != -2 && group[i][j] != 0 && group[i][j] < minh) {
192                         minh = group[i][j];
193                     }
194                 }
195                 hmin[i] = minh;// 更新當前行的最小值
196                 if (minh >= bigMin) {
197                     bigMin = minh;
198                     h = i;
199                 }
200             }
201 
202         }
203         return h;
204     }
205 
206     private int isDone1() {// 判斷是否完成
207         int zn = 0;// 0的個數 如果只剩一個0就完成
208         for (int i = 0; i < N; i++) {
209             for (int j = 0; j < N; j++) {
210                 if (group[i][j] == 0) {
211                     ++zn;
212                 }
213             }
214         }
215         return zn;// 返回當前一共有幾個0
216     }
217 
218     private int isDone2() {// 判斷是否完成 如果除了-2就是0或-1 也算完成
219         int haszt = 0;// 不是0和-2的個數
220         for (int i = 0; i < N; i++) {
221             for (int j = 0; j < N; j++) {
222                 if (group[i][j] != 0 || group[i][j] != -2 || group[i][j] != -1) {
223                     ++haszt;
224                 }
225             }
226         }
227         return haszt;
228     }
229 
230     private int isDone3() {// 判斷3
231         int haszt = 0;// 不是-2的個數
232         for (int i = 0; i < N; i++) {
233             for (int j = 0; j < N; j++) {
234                 if (group[i][j] != -2) {
235                     ++haszt;
236                 }
237             }
238         }
239         return haszt;
240     }
241 
242     public static void main(String[] args) {
243         Sell2 s2 = new Sell2();
244         s2.init();
245         s2.tree();
246         System.out.println("bound:" + bound);
247     }
248 }