2011-09-17 07:21:31Morris
[想出題目 on ZJ] 旅行業務員問題 Traveling Salesman Problem (TSP)
內容 :
旅行業務員問題 (Traveling Salesman Problem) 是個有名的難題，旅行業務員要到 n 個城市推展業務，n 個城市以 1,2,…,n 表示，從 1 出發，經過每個城市恰只一次，再回到 1，令 Cij 表城市 i 到城市 j 的旅行成本，問題為找出一個最小成本的路徑。
輸入說明 :
有多筆測資，每組第一行有一個數字 n (1 ≦ n ≦ 20) 代表有編號 1 ~ n 的城市，
接下來有 n 行，每行上有 n 個數字 C (1 ≦ C ≦ 100,0000)，
第 i 行上的第 j 的數字代表城市 i 到城市 j 的旅行成本
輸出說明 :
輸出最小成本
範例輸入 :
5
0 3 4 2 6
5 0 3 5 1
0 5 0 6 9
5 3 0 0 5
9 0 6 4 0
範例輸出 :
19
旅行業務員問題 (Traveling Salesman Problem) 是個有名的難題，旅行業務員要到 n 個城市推展業務，n 個城市以 1,2,…,n 表示，從 1 出發，經過每個城市恰只一次，再回到 1，令 Cij 表城市 i 到城市 j 的旅行成本，問題為找出一個最小成本的路徑。
輸入說明 :
有多筆測資，每組第一行有一個數字 n (1 ≦ n ≦ 20) 代表有編號 1 ~ n 的城市，
接下來有 n 行，每行上有 n 個數字 C (1 ≦ C ≦ 100,0000)，
第 i 行上的第 j 的數字代表城市 i 到城市 j 的旅行成本
輸出說明 :
輸出最小成本
範例輸入 :
5
0 3 4 2 6
5 0 3 5 1
0 5 0 6 9
5 3 0 0 5
9 0 6 4 0
範例輸出 :
19
下一篇：[2011/9/29] 大學生活