問個問題
下面是PST 推銷員路徑的兩點距離表,由城市1開始回到城市1,經過每個城市,每個城市只能經過一次,請問最短路徑是多少 ?
16 | 5 | 1 | 35 | 31 | 5 | 29 | 17 | 12 | 25 | 5 | 24 | 23 | 36 | 44 | 23 | 5 | 24 | 3 | 33 | 22 | 33 | 44 | 43 | 28 | 50 | 38 | 26 | 5 | 15 | 20 | 2 | 38 | 17 | 43 | 47 | 42 | 49 | 24 | 16 | 22 | 17 | 21 | 23 | 35 | 1 | 43 | 3 | 37 | |
16 | 7 | 2 | 9 | 1 | 35 | 4 | 10 | 30 | 7 | 10 | 48 | 22 | 38 | 25 | 30 | 17 | 31 | 15 | 21 | 44 | 22 | 2 | 20 | 24 | 14 | 19 | 50 | 4 | 30 | 37 | 2 | 25 | 10 | 27 | 27 | 41 | 28 | 12 | 21 | 6 | 35 | 29 | 28 | 48 | 44 | 39 | 17 | 19 | |
5 | 7 | 36 | 2 | 24 | 22 | 38 | 37 | 21 | 10 | 6 | 20 | 42 | 21 | 34 | 49 | 11 | 37 | 17 | 38 | 47 | 29 | 40 | 15 | 33 | 2 | 46 | 4 | 7 | 17 | 50 | 45 | 2 | 9 | 34 | 8 | 30 | 13 | 21 | 42 | 38 | 16 | 24 | 20 | 49 | 40 | 47 | 45 | 2 | |
1 | 2 | 36 | 1 | 5 | 14 | 4 | 24 | 13 | 6 | 11 | 20 | 21 | 20 | 27 | 41 | 6 | 19 | 38 | 24 | 22 | 9 | 16 | 43 | 48 | 44 | 22 | 20 | 30 | 2 | 45 | 11 | 30 | 4 | 28 | 30 | 41 | 4 | 37 | 23 | 20 | 12 | 35 | 43 | 17 | 22 | 24 | 50 | 1 | |
35 | 9 | 2 | 1 | 48 | 26 | 2 | 26 | 30 | 22 | 27 | 1 | 12 | 43 | 29 | 30 | 8 | 16 | 38 | 36 | 19 | 42 | 4 | 35 | 28 | 34 | 46 | 33 | 21 | 49 | 42 | 30 | 23 | 17 | 42 | 34 | 49 | 5 | 16 | 47 | 35 | 1 | 36 | 2 | 30 | 6 | 21 | 9 | 18 | |
31 | 1 | 24 | 5 | 48 | 21 | 3 | 18 | 36 | 11 | 49 | 9 | 15 | 29 | 50 | 41 | 33 | 33 | 16 | 32 | 37 | 5 | 23 | 45 | 41 | 23 | 42 | 40 | 5 | 22 | 9 | 45 | 5 | 1 | 35 | 35 | 36 | 30 | 37 | 14 | 15 | 22 | 15 | 43 | 5 | 28 | 36 | 18 | 32 | |
5 | 35 | 22 | 14 | 26 | 21 | 48 | 8 | 15 | 50 | 32 | 8 | 10 | 33 | 6 | 38 | 25 | 12 | 31 | 8 | 17 | 41 | 5 | 21 | 17 | 32 | 21 | 20 | 49 | 14 | 36 | 24 | 29 | 27 | 29 | 49 | 4 | 38 | 20 | 43 | 5 | 44 | 49 | 33 | 17 | 3 | 43 | 19 | 10 | |
29 | 4 | 38 | 4 | 2 | 3 | 48 | 23 | 17 | 6 | 11 | 49 | 47 | 37 | 10 | 25 | 16 | 33 | 30 | 11 | 26 | 31 | 41 | 7 | 29 | 1 | 27 | 9 | 46 | 26 | 24 | 49 | 17 | 3 | 23 | 40 | 36 | 36 | 19 | 1 | 7 | 15 | 26 | 3 | 42 | 29 | 36 | 49 | 41 | |
17 | 10 | 37 | 24 | 26 | 18 | 8 | 23 | 13 | 45 | 17 | 9 | 20 | 18 | 25 | 41 | 23 | 25 | 11 | 1 | 16 | 42 | 8 | 4 | 3 | 37 | 1 | 6 | 19 | 17 | 8 | 37 | 4 | 19 | 9 | 7 | 31 | 30 | 11 | 9 | 5 | 50 | 42 | 45 | 16 | 22 | 23 | 6 | 3 | |
12 | 30 | 21 | 13 | 30 | 36 | 15 | 17 | 13 | 15 | 19 | 35 | 49 | 6 | 35 | 26 | 41 | 47 | 14 | 26 | 13 | 19 | 22 | 37 | 38 | 5 | 11 | 5 | 1 | 13 | 1 | 41 | 27 | 21 | 10 | 13 | 17 | 20 | 21 | 8 | 16 | 36 | 16 | 30 | 12 | 30 | 49 | 41 | 4 | |
25 | 7 | 10 | 6 | 22 | 11 | 50 | 6 | 45 | 15 | 37 | 18 | 34 | 46 | 23 | 17 | 2 | 32 | 7 | 22 | 47 | 29 | 43 | 15 | 11 | 32 | 21 | 23 | 34 | 28 | 32 | 15 | 39 | 50 | 50 | 2 | 19 | 34 | 30 | 43 | 23 | 26 | 24 | 48 | 26 | 23 | 5 | 5 | 16 | |
5 | 10 | 6 | 11 | 27 | 49 | 32 | 11 | 17 | 19 | 37 | 11 | 41 | 16 | 3 | 34 | 14 | 32 | 1 | 13 | 16 | 42 | 21 | 49 | 9 | 42 | 12 | 16 | 17 | 47 | 33 | 27 | 46 | 49 | 8 | 37 | 11 | 33 | 49 | 49 | 34 | 16 | 12 | 23 | 32 | 11 | 27 | 9 | 48 | |
24 | 48 | 20 | 20 | 1 | 9 | 8 | 49 | 9 | 35 | 18 | 11 | 7 | 46 | 49 | 26 | 39 | 10 | 16 | 43 | 23 | 28 | 28 | 2 | 43 | 43 | 37 | 26 | 25 | 38 | 46 | 30 | 50 | 21 | 32 | 18 | 20 | 10 | 39 | 7 | 3 | 23 | 38 | 14 | 8 | 43 | 31 | 15 | 28 | |
23 | 22 | 42 | 21 | 12 | 15 | 10 | 47 | 20 | 49 | 34 | 41 | 7 | 16 | 32 | 42 | 41 | 14 | 15 | 48 | 2 | 19 | 9 | 4 | 6 | 28 | 2 | 44 | 12 | 50 | 12 | 18 | 44 | 39 | 43 | 35 | 41 | 34 | 46 | 3 | 5 | 37 | 10 | 2 | 42 | 8 | 5 | 16 | 35 | |
36 | 38 | 21 | 20 | 43 | 29 | 33 | 37 | 18 | 6 | 46 | 16 | 46 | 16 | 36 | 41 | 40 | 4 | 36 | 33 | 6 | 23 | 14 | 35 | 33 | 19 | 20 | 2 | 9 | 13 | 47 | 14 | 1 | 16 | 47 | 37 | 48 | 24 | 9 | 23 | 14 | 19 | 29 | 23 | 29 | 22 | 7 | 35 | 40 | |
44 | 25 | 34 | 27 | 29 | 50 | 6 | 10 | 25 | 35 | 23 | 3 | 49 | 32 | 36 | 33 | 19 | 46 | 36 | 11 | 46 | 42 | 4 | 47 | 45 | 20 | 50 | 11 | 43 | 28 | 28 | 24 | 15 | 31 | 42 | 31 | 33 | 38 | 2 | 7 | 42 | 32 | 31 | 16 | 50 | 36 | 29 | 19 | 3 | |
23 | 30 | 49 | 41 | 30 | 41 | 38 | 25 | 41 | 26 | 17 | 34 | 26 | 42 | 41 | 33 | 24 | 6 | 34 | 45 | 16 | 48 | 32 | 45 | 9 | 27 | 8 | 42 | 36 | 26 | 28 | 42 | 31 | 18 | 25 | 23 | 48 | 19 | 31 | 22 | 49 | 41 | 26 | 38 | 12 | 12 | 4 | 40 | 27 | |
5 | 17 | 11 | 6 | 8 | 33 | 25 | 16 | 23 | 41 | 2 | 14 | 39 | 41 | 40 | 19 | 24 | 1 | 1 | 49 | 1 | 31 | 10 | 47 | 7 | 26 | 48 | 21 | 19 | 44 | 5 | 39 | 48 | 1 | 9 | 26 | 40 | 43 | 26 | 18 | 27 | 11 | 32 | 7 | 39 | 5 | 17 | 26 | 32 | |
24 | 31 | 37 | 19 | 16 | 33 | 12 | 33 | 25 | 47 | 32 | 32 | 10 | 14 | 4 | 46 | 6 | 1 | 21 | 13 | 13 | 36 | 30 | 50 | 29 | 25 | 34 | 28 | 21 | 11 | 25 | 46 | 21 | 1 | 48 | 3 | 39 | 34 | 48 | 3 | 37 | 42 | 40 | 49 | 28 | 4 | 40 | 44 | 29 | |
3 | 15 | 17 | 38 | 38 | 16 | 31 | 30 | 11 | 14 | 7 | 1 | 16 | 15 | 36 | 36 | 34 | 1 | 21 | 3 | 45 | 3 | 34 | 43 | 49 | 35 | 34 | 21 | 5 | 1 | 18 | 10 | 3 | 34 | 49 | 3 | 4 | 28 | 7 | 3 | 48 | 35 | 19 | 25 | 42 | 34 | 27 | 46 | 37 | |
33 | 21 | 38 | 24 | 36 | 32 | 8 | 11 | 1 | 26 | 22 | 13 | 43 | 48 | 33 | 11 | 45 | 49 | 13 | 3 | 3 | 22 | 9 | 15 | 22 | 14 | 45 | 26 | 19 | 23 | 21 | 30 | 39 | 23 | 1 | 45 | 38 | 33 | 10 | 3 | 15 | 12 | 31 | 2 | 37 | 37 | 25 | 25 | 9 | |
22 | 44 | 47 | 22 | 19 | 37 | 17 | 26 | 16 | 13 | 47 | 16 | 23 | 2 | 6 | 46 | 16 | 1 | 13 | 45 | 3 | 41 | 6 | 18 | 42 | 8 | 34 | 32 | 28 | 46 | 36 | 26 | 11 | 26 | 5 | 16 | 6 | 48 | 48 | 22 | 38 | 41 | 1 | 4 | 2 | 24 | 15 | 20 | 45 | |
33 | 22 | 29 | 9 | 42 | 5 | 41 | 31 | 42 | 19 | 29 | 42 | 28 | 19 | 23 | 42 | 48 | 31 | 36 | 3 | 22 | 41 | 47 | 33 | 42 | 49 | 10 | 41 | 15 | 33 | 41 | 33 | 23 | 46 | 40 | 35 | 3 | 34 | 21 | 10 | 11 | 36 | 39 | 30 | 22 | 33 | 13 | 21 | 19 | |
44 | 2 | 40 | 16 | 4 | 23 | 5 | 41 | 8 | 22 | 43 | 21 | 28 | 9 | 14 | 4 | 32 | 10 | 30 | 34 | 9 | 6 | 47 | 46 | 27 | 47 | 31 | 31 | 34 | 24 | 49 | 50 | 44 | 20 | 32 | 19 | 33 | 45 | 28 | 8 | 19 | 23 | 31 | 28 | 9 | 3 | 44 | 9 | 46 | |
43 | 20 | 15 | 43 | 35 | 45 | 21 | 7 | 4 | 37 | 15 | 49 | 2 | 4 | 35 | 47 | 45 | 47 | 50 | 43 | 15 | 18 | 33 | 46 | 12 | 27 | 37 | 23 | 49 | 48 | 22 | 48 | 5 | 28 | 32 | 9 | 12 | 39 | 3 | 1 | 13 | 37 | 16 | 19 | 30 | 27 | 14 | 16 | 26 | |
28 | 24 | 33 | 48 | 28 | 41 | 17 | 29 | 3 | 38 | 11 | 9 | 43 | 6 | 33 | 45 | 9 | 7 | 29 | 49 | 22 | 42 | 42 | 27 | 12 | 28 | 15 | 29 | 31 | 36 | 10 | 27 | 50 | 14 | 18 | 47 | 7 | 34 | 12 | 23 | 9 | 36 | 24 | 20 | 45 | 44 | 5 | 7 | 25 | |
50 | 14 | 2 | 44 | 34 | 23 | 32 | 1 | 37 | 5 | 32 | 42 | 43 | 28 | 19 | 20 | 27 | 26 | 25 | 35 | 14 | 8 | 49 | 47 | 27 | 28 | 31 | 46 | 8 | 9 | 20 | 43 | 14 | 12 | 11 | 48 | 10 | 14 | 33 | 41 | 41 | 36 | 18 | 32 | 47 | 35 | 22 | 44 | 45 | |
38 | 19 | 46 | 22 | 46 | 42 | 21 | 27 | 1 | 11 | 21 | 12 | 37 | 2 | 20 | 50 | 8 | 48 | 34 | 34 | 45 | 34 | 10 | 31 | 37 | 15 | 31 | 3 | 30 | 37 | 30 | 32 | 17 | 3 | 15 | 11 | 9 | 10 | 32 | 22 | 41 | 36 | 33 | 7 | 34 | 27 | 50 | 41 | 49 | |
26 | 50 | 4 | 20 | 33 | 40 | 20 | 9 | 6 | 5 | 23 | 16 | 26 | 44 | 2 | 11 | 42 | 21 | 28 | 21 | 26 | 32 | 41 | 31 | 23 | 29 | 46 | 3 | 19 | 2 | 25 | 7 | 37 | 31 | 30 | 6 | 23 | 23 | 18 | 4 | 1 | 30 | 12 | 34 | 14 | 9 | 10 | 7 | 8 | |
5 | 4 | 7 | 30 | 21 | 5 | 49 | 46 | 19 | 1 | 34 | 17 | 25 | 12 | 9 | 43 | 36 | 19 | 21 | 5 | 19 | 28 | 15 | 34 | 49 | 31 | 8 | 30 | 19 | 32 | 17 | 35 | 7 | 38 | 47 | 45 | 25 | 36 | 21 | 32 | 12 | 35 | 45 | 17 | 37 | 8 | 24 | 26 | 25 | |
15 | 30 | 17 | 2 | 49 | 22 | 14 | 26 | 17 | 13 | 28 | 47 | 38 | 50 | 13 | 28 | 26 | 44 | 11 | 1 | 23 | 46 | 33 | 24 | 48 | 36 | 9 | 37 | 2 | 32 | 42 | 7 | 27 | 11 | 11 | 48 | 18 | 11 | 3 | 23 | 35 | 8 | 35 | 10 | 20 | 30 | 3 | 35 | 20 | |
20 | 37 | 50 | 45 | 42 | 9 | 36 | 24 | 8 | 1 | 32 | 33 | 46 | 12 | 47 | 28 | 28 | 5 | 25 | 18 | 21 | 36 | 41 | 49 | 22 | 10 | 20 | 30 | 25 | 17 | 42 | 41 | 24 | 5 | 22 | 39 | 28 | 12 | 20 | 25 | 50 | 32 | 14 | 49 | 44 | 44 | 26 | 41 | 33 | |
2 | 2 | 45 | 11 | 30 | 45 | 24 | 49 | 37 | 41 | 15 | 27 | 30 | 18 | 14 | 24 | 42 | 39 | 46 | 10 | 30 | 26 | 33 | 50 | 48 | 27 | 43 | 32 | 7 | 35 | 7 | 41 | 33 | 34 | 15 | 5 | 26 | 34 | 49 | 36 | 50 | 37 | 6 | 29 | 20 | 15 | 33 | 22 | 42 | |
38 | 25 | 2 | 30 | 23 | 5 | 29 | 17 | 4 | 27 | 39 | 46 | 50 | 44 | 1 | 15 | 31 | 48 | 21 | 3 | 39 | 11 | 23 | 44 | 5 | 50 | 14 | 17 | 37 | 7 | 27 | 24 | 33 | 50 | 4 | 9 | 44 | 16 | 9 | 15 | 1 | 42 | 17 | 4 | 23 | 41 | 22 | 28 | 4 | |
17 | 10 | 9 | 4 | 17 | 1 | 27 | 3 | 19 | 21 | 50 | 49 | 21 | 39 | 16 | 31 | 18 | 1 | 1 | 34 | 23 | 26 | 46 | 20 | 28 | 14 | 12 | 3 | 31 | 38 | 11 | 5 | 34 | 50 | 34 | 34 | 46 | 21 | 9 | 42 | 32 | 9 | 2 | 18 | 38 | 1 | 30 | 32 | 40 | |
43 | 27 | 34 | 28 | 42 | 35 | 29 | 23 | 9 | 10 | 50 | 8 | 32 | 43 | 47 | 42 | 25 | 9 | 48 | 49 | 1 | 5 | 40 | 32 | 32 | 18 | 11 | 15 | 30 | 47 | 11 | 22 | 15 | 4 | 34 | 45 | 50 | 50 | 36 | 30 | 1 | 19 | 39 | 46 | 48 | 12 | 19 | 37 | 42 | |
47 | 27 | 8 | 30 | 34 | 35 | 49 | 40 | 7 | 13 | 2 | 37 | 18 | 35 | 37 | 31 | 23 | 26 | 3 | 3 | 45 | 16 | 35 | 19 | 9 | 47 | 48 | 11 | 6 | 45 | 48 | 39 | 5 | 9 | 34 | 45 | 35 | 27 | 37 | 40 | 21 | 21 | 48 | 20 | 39 | 42 | 20 | 29 | 17 | |
42 | 41 | 30 | 41 | 49 | 36 | 4 | 36 | 31 | 17 | 19 | 11 | 20 | 41 | 48 | 33 | 48 | 40 | 39 | 4 | 38 | 6 | 3 | 33 | 12 | 7 | 10 | 9 | 23 | 25 | 18 | 28 | 26 | 44 | 46 | 50 | 35 | 46 | 13 | 34 | 7 | 1 | 25 | 28 | 33 | 48 | 43 | 12 | 29 | |
49 | 28 | 13 | 4 | 5 | 30 | 38 | 36 | 30 | 20 | 34 | 33 | 10 | 34 | 24 | 38 | 19 | 43 | 34 | 28 | 33 | 48 | 34 | 45 | 39 | 34 | 14 | 10 | 23 | 36 | 11 | 12 | 34 | 16 | 21 | 50 | 27 | 46 | 33 | 18 | 49 | 46 | 40 | 25 | 35 | 6 | 5 | 7 | 8 | |
24 | 12 | 21 | 37 | 16 | 37 | 20 | 19 | 11 | 21 | 30 | 49 | 39 | 46 | 9 | 2 | 31 | 26 | 48 | 7 | 10 | 48 | 21 | 28 | 3 | 12 | 33 | 32 | 18 | 21 | 3 | 20 | 49 | 9 | 9 | 36 | 37 | 13 | 33 | 38 | 6 | 42 | 38 | 41 | 13 | 25 | 36 | 50 | 7 | |
16 | 21 | 42 | 23 | 47 | 14 | 43 | 1 | 9 | 8 | 43 | 49 | 7 | 3 | 23 | 7 | 22 | 18 | 3 | 3 | 3 | 22 | 10 | 8 | 1 | 23 | 41 | 22 | 4 | 32 | 23 | 25 | 36 | 15 | 42 | 30 | 40 | 34 | 18 | 38 | 35 | 27 | 44 | 23 | 32 | 12 | 46 | 4 | 24 | |
22 | 6 | 38 | 20 | 35 | 15 | 5 | 7 | 5 | 16 | 23 | 34 | 3 | 5 | 14 | 42 | 49 | 27 | 37 | 48 | 15 | 38 | 11 | 19 | 13 | 9 | 41 | 41 | 1 | 12 | 35 | 50 | 50 | 1 | 32 | 1 | 21 | 7 | 49 | 6 | 35 | 9 | 45 | 21 | 3 | 46 | 34 | 30 | 38 | |
17 | 35 | 16 | 12 | 1 | 22 | 44 | 15 | 50 | 36 | 26 | 16 | 23 | 37 | 19 | 32 | 41 | 11 | 42 | 35 | 12 | 41 | 36 | 23 | 37 | 36 | 36 | 36 | 30 | 35 | 8 | 32 | 37 | 42 | 9 | 19 | 21 | 1 | 46 | 42 | 27 | 9 | 40 | 2 | 43 | 3 | 26 | 1 | 36 | |
21 | 29 | 24 | 35 | 36 | 15 | 49 | 26 | 42 | 16 | 24 | 12 | 38 | 10 | 29 | 31 | 26 | 32 | 40 | 19 | 31 | 1 | 39 | 31 | 16 | 24 | 18 | 33 | 12 | 45 | 35 | 14 | 6 | 17 | 2 | 39 | 48 | 25 | 40 | 38 | 44 | 45 | 40 | 37 | 44 | 12 | 12 | 14 | 5 | |
23 | 28 | 20 | 43 | 2 | 43 | 33 | 3 | 45 | 30 | 48 | 23 | 14 | 2 | 23 | 16 | 38 | 7 | 49 | 25 | 2 | 4 | 30 | 28 | 19 | 20 | 32 | 7 | 34 | 17 | 10 | 49 | 29 | 4 | 18 | 46 | 20 | 28 | 25 | 41 | 23 | 21 | 2 | 37 | 42 | 32 | 16 | 45 | 15 | |
35 | 48 | 49 | 17 | 30 | 5 | 17 | 42 | 16 | 12 | 26 | 32 | 8 | 42 | 29 | 50 | 12 | 39 | 28 | 42 | 37 | 2 | 22 | 9 | 30 | 45 | 47 | 34 | 14 | 37 | 20 | 44 | 20 | 23 | 38 | 48 | 39 | 33 | 35 | 13 | 32 | 3 | 43 | 44 | 42 | 42 | 16 | 38 | 43 | |
1 | 44 | 40 | 22 | 6 | 28 | 3 | 29 | 22 | 30 | 23 | 11 | 43 | 8 | 22 | 36 | 12 | 5 | 4 | 34 | 37 | 24 | 33 | 3 | 27 | 44 | 35 | 27 | 9 | 8 | 30 | 44 | 15 | 41 | 1 | 12 | 42 | 48 | 6 | 25 | 12 | 46 | 3 | 12 | 32 | 42 | 11 | 20 | 39 | |
43 | 39 | 47 | 24 | 21 | 36 | 43 | 36 | 23 | 49 | 5 | 27 | 31 | 5 | 7 | 29 | 4 | 17 | 40 | 27 | 25 | 15 | 13 | 44 | 14 | 5 | 22 | 50 | 10 | 24 | 3 | 26 | 33 | 22 | 30 | 19 | 20 | 43 | 5 | 36 | 46 | 34 | 26 | 12 | 16 | 16 | 11 | 1 | 2 | |
3 | 17 | 45 | 50 | 9 | 18 | 19 | 49 | 6 | 41 | 5 | 9 | 15 | 16 | 35 | 19 | 40 | 26 | 44 | 46 | 25 | 20 | 21 | 9 | 16 | 7 | 44 | 41 | 7 | 26 | 35 | 41 | 22 | 28 | 32 | 37 | 29 | 12 | 7 | 50 | 4 | 30 | 1 | 14 | 45 | 38 | 20 | 1 | 7 | |
37 | 19 | 2 | 1 | 18 | 32 | 10 | 41 | 3 | 4 | 16 | 48 | 28 | 35 | 40 | 3 | 27 | 32 | 29 | 37 | 9 | 45 | 19 | 46 | 26 | 25 | 45 | 49 | 8 | 25 | 20 | 33 | 42 | 4 | 40 | 42 | 17 | 29 | 8 | 7 | 24 | 38 | 36 | 5 | 15 | 43 | 39 | 2 | 7 |
50個城市
我的解 : 216
不知如何驗證是否最優解
有人能找到更短的路徑嗎?