最短的距離

patagonia2

遇到這個(gè)問題，沒什么思路。

請問各位大圣這種情況怎么處理呢。

• 必須拜訪每個(gè)地點(diǎn)一次。
• 最短的距離是？
• 列出一條有最短距離的途徑
  

例如，給出以下距離：

pit-01 ->  pit-02 = 464
pit-01 ->  pit-03 = 518
pit-02 ->  pit-03 = 141

因此，可能的途徑有：

pit-01 ->  pit-02 ->  pit-03 = 605
pit-01 ->  pit-03 ->  pit-02 = 659
pit-02 ->  pit-01 ->  pit-03 = 982
pit-02 ->  pit-03 ->  pit-01 = 659
pit-03 ->  pit-02 ->  pit-01 = 605
pit-03 ->  pit-01 ->  pit-02 = 982

所以答案是

pit-01 ->  pit-02 ->  pit-03 = 605


請問各位大圣這種情況怎么處理呢。

1. PIT-001        PIT-002        9665
   
2. PIT-001        PIT-003        5794
   
3. PIT-001        PIT-004        96
   
4. PIT-001        PIT-005        5750
   
5. PIT-001        PIT-006        6394
   
6. PIT-001        PIT-007        5750
   
7. PIT-001        PIT-008        3478
   
8. PIT-001        PIT-009        262
   
9. PIT-001        PIT-010        8954
   
10. PIT-001        PIT-011        3751
    
11. PIT-001        PIT-012        5253
    
12. PIT-001        PIT-013        6988
    
13. PIT-001        PIT-014        1364
    
14. PIT-001        PIT-015        9415
    
15. PIT-001        PIT-016        6156
    
16. PIT-001        PIT-017        6015
    
17. PIT-001        PIT-018        7931
    
18. PIT-001        PIT-019        5082
    
19. PIT-001        PIT-020        9891
    
20. PIT-002        PIT-003        6580
    
21. PIT-002        PIT-004        4325
    
22. PIT-002        PIT-005        5355
    
23. PIT-002        PIT-006        7221
    
24. PIT-002        PIT-007        4093
    
25. PIT-002        PIT-008        6098
    
26. PIT-002        PIT-009        2720
    
27. PIT-002        PIT-010        4662
    
28. PIT-002        PIT-011        9336
    
29. PIT-002        PIT-012        378
    
30. PIT-002        PIT-013        4632
    
31. PIT-002        PIT-014        3403
    
32. PIT-002        PIT-015        6736
    
33. PIT-002        PIT-016        7797
    
34. PIT-002        PIT-017        5479
    
35. PIT-002        PIT-018        9189
    
36. PIT-002        PIT-019        1372
    
37. PIT-002        PIT-020        4367
    
38. PIT-003        PIT-004        9601
    
39. PIT-003        PIT-005        6529
    
40. PIT-003        PIT-006        1255
    
41. PIT-003        PIT-007        2524
    
42. PIT-003        PIT-008        5562
    
43. PIT-003        PIT-009        5222
    
44. PIT-003        PIT-010        998
    
45. PIT-003        PIT-011        8214
    
46. PIT-003        PIT-012        3623
    
47. PIT-003        PIT-013        5083
    
48. PIT-003        PIT-014        470
    
49. PIT-003        PIT-015        6274
    
50. PIT-003        PIT-016        7125
    
51. PIT-003        PIT-017        6897
    
52. PIT-003        PIT-018        1281
    
53. PIT-003        PIT-019        9852
    
54. PIT-003        PIT-020        8675
    
55. PIT-004        PIT-005        6886
    
56. PIT-004        PIT-006        456
    
57. PIT-004        PIT-007        4762
    
58. PIT-004        PIT-008        5580
    
59. PIT-004        PIT-009        5893
    
60. PIT-004        PIT-010        3720
    
61. PIT-004        PIT-011        6098
    
62. PIT-004        PIT-012        8211
    
63. PIT-004        PIT-013        7543
    
64. PIT-004        PIT-014        6081
    
65. PIT-004        PIT-015        9590
    
66. PIT-004        PIT-016        4647
    
67. PIT-004        PIT-017        5801
    
68. PIT-004        PIT-018        9606
    
69. PIT-004        PIT-019        2766
    
70. PIT-004        PIT-020        5154
    
71. PIT-005        PIT-006        7815
    
72. PIT-005        PIT-007        3318
    
73. PIT-005        PIT-008        2698
    
74. PIT-005        PIT-009        8343
    
75. PIT-005        PIT-010        3150
    
76. PIT-005        PIT-011        8051
    
77. PIT-005        PIT-012        5387
    
78. PIT-005        PIT-013        5225
    
79. PIT-005        PIT-014        3237
    
80. PIT-005        PIT-015        6158
    
81. PIT-005        PIT-016        2743
    
82. PIT-005        PIT-017        8072
    
83. PIT-005        PIT-018        2154
    
84. PIT-005        PIT-019        7430
    
85. PIT-005        PIT-020        3015
    
86. PIT-006        PIT-007        3927
    
87. PIT-006        PIT-008        970
    
88. PIT-006        PIT-009        5107
    
89. PIT-006        PIT-010        9473
    
90. PIT-006        PIT-011        771
    
91. PIT-006        PIT-012        6491
    
92. PIT-006        PIT-013        33
    
93. PIT-006        PIT-014        5768
    
94. PIT-006        PIT-015        1480
    
95. PIT-006        PIT-016        2144
    
96. PIT-006        PIT-017        3695
    
97. PIT-006        PIT-018        8603
    
98. PIT-006        PIT-019        2669
    
99. PIT-006        PIT-020        4192
    
100. PIT-007        PIT-008        8087
     
101. PIT-007        PIT-009        3979
     
102. PIT-007        PIT-010        3726
     
103. PIT-007        PIT-011        2743
     
104. PIT-007        PIT-012        9232
     
105. PIT-007        PIT-013        217
     
106. PIT-007        PIT-014        4633
     
107. PIT-007        PIT-015        1088
     
108. PIT-007        PIT-016        2993
     
109. PIT-007        PIT-017        3154
     
110. PIT-007        PIT-018        8646
     
111. PIT-007        PIT-019        2484
     
112. PIT-007        PIT-020        4101
     
113. PIT-008        PIT-009        8297
     
114. PIT-008        PIT-010        9313
     
115. PIT-008        PIT-011        4124
     
116. PIT-008        PIT-012        8629
     
117. PIT-008        PIT-013        4267
     
118. PIT-008        PIT-014        7456
     
119. PIT-008        PIT-015        9067
     
120. PIT-008        PIT-016        4293
     
121. PIT-008        PIT-017        7649
     
122. PIT-008        PIT-018        7310
     
123. PIT-008        PIT-019        8391
     
124. PIT-008        PIT-020        3848
     
125. PIT-009        PIT-010        3381
     
126. PIT-009        PIT-011        6493
     
127. PIT-009        PIT-012        4667
     
128. PIT-009        PIT-013        2612
     
129. PIT-009        PIT-014        7146
     
130. PIT-009        PIT-015        9488
     
131. PIT-009        PIT-016        678
     
132. PIT-009        PIT-017        8957
     
133. PIT-009        PIT-018        8025
     
134. PIT-009        PIT-019        1089
     
135. PIT-009        PIT-020        2631
     
136. PIT-010        PIT-011        4976
     
137. PIT-010        PIT-012        5045
     
138. PIT-010        PIT-013        5178
     
139. PIT-010        PIT-014        8014
     
140. PIT-010        PIT-015        5851
     
141. PIT-010        PIT-016        357
     
142. PIT-010        PIT-017        5471
     
143. PIT-010        PIT-018        4935
     
144. PIT-010        PIT-019        9617
     
145. PIT-010        PIT-020        2907
     
146. PIT-011        PIT-012        1515
     
147. PIT-011        PIT-013        1778
     
148. PIT-011        PIT-014        1773
     
149. PIT-011        PIT-015        8704
     
150. PIT-011        PIT-016        3318
     
151. PIT-011        PIT-017        5180
     
152. PIT-011        PIT-018        582
     
153. PIT-011        PIT-019        9573
     
154. PIT-011        PIT-020        7458
     
155. PIT-012        PIT-013        6710
     
156. PIT-012        PIT-014        2171
     
157. PIT-012        PIT-015        9788
     
158. PIT-012        PIT-016        2127
     
159. PIT-012        PIT-017        7630
     
160. PIT-012        PIT-018        8959
     
161. PIT-012        PIT-019        5590
     
162. PIT-012        PIT-020        7108
     
163. PIT-013        PIT-014        9409
     
164. PIT-013        PIT-015        9030
     
165. PIT-013        PIT-016        3654
     
166. PIT-013        PIT-017        714
     
167. PIT-013        PIT-018        118
     
168. PIT-013        PIT-019        7472
     
169. PIT-013        PIT-020        1517
     
170. PIT-014        PIT-015        890
     
171. PIT-014        PIT-016        2776
     
172. PIT-014        PIT-017        7240
     
173. PIT-014        PIT-018        2120
     
174. PIT-014        PIT-019        3314
     
175. PIT-014        PIT-020        7544
     
176. PIT-015        PIT-016        6725
     
177. PIT-015        PIT-017        587
     
178. PIT-015        PIT-018        9877
     
179. PIT-015        PIT-019        1254
     
180. PIT-015        PIT-020        3023
     
181. PIT-016        PIT-017        9444
     
182. PIT-016        PIT-018        5608
     
183. PIT-016        PIT-019        3084
     
184. PIT-016        PIT-020        4228
     
185. PIT-017        PIT-018        7387
     
186. PIT-017        PIT-019        8076
     
187. PIT-017        PIT-020        6686
     
188. PIT-018        PIT-019        5275
     
189. PIT-018        PIT-020        816
     
190. PIT-019        PIT-020        7673
     

復(fù)制代碼

tolilong

已經(jīng)所有點(diǎn)的距離？

mswsg

求大神。。！這個(gè)看了一會(huì)
一共有20個(gè)點(diǎn)， 要求一次經(jīng)過每個(gè)點(diǎn)（點(diǎn)不重復(fù)），并且總距離最短。
已經(jīng)給出任意每個(gè)點(diǎn)之間的距離（a,b）=x
第一個(gè)點(diǎn)的可能性是20，依次是19 ，18 ，... 3,2,1
。。。。。

Herowinter

求一條路徑最短的哈密爾頓回路，這種題目用shell來解，
真的合適嗎？

patagonia2

回復(fù) 2# tolilong


     謝謝大圣指導(dǎo)。

patagonia2

回復(fù) 3# mswsg

謝謝大神指導(dǎo)。
大神們什么好的代碼？
   

patagonia2

回復(fù) 4# Herowinter


這數(shù)據(jù)量也不大，大圣來一發(fā)
謝謝大圣指導(dǎo)。

Herowinter

回復(fù) 7# patagonia2

這個(gè)問題遠(yuǎn)比你想象的復(fù)雜, 我算法沒學(xué)好, 寫不來.

維基百科:
尋找哈密頓路的確定算法雖然很難有多項(xiàng)式時(shí)間的，但是這并不意味著只能進(jìn)行時(shí)間復(fù)雜度為O(n!*n)暴力搜索。
利用狀態(tài)壓縮動(dòng)態(tài)規(guī)劃，可以將時(shí)間復(fù)雜度降低到O(2^n*n^3)。
n=20, 優(yōu)化算法也不簡單.

你可以把這題發(fā)到一些高級(jí)語言的版塊(如C++  Java)等, 看看有沒有大神能幫你.
   

patagonia2

回復(fù) 8# Herowinter

謝謝大圣指導(dǎo)。

lll1985911

百度文庫中搜了一篇文章（關(guān)于物流系統(tǒng)方面的）可能有點(diǎn)幫助。
（我沒有發(fā)url的權(quán)限）

這個(gè)是較為典型的哈密爾頓回路問題。
參考A*算法和Dijkstra應(yīng)該會(huì)有一些提示。
嚴(yán)格的說，shell不說不能做，而是shell天生并不是解決這類復(fù)雜問題的。

另外針對(duì)現(xiàn)代物流系統(tǒng)，我個(gè)人認(rèn)為不能只單單考慮路徑長短，貨物裝卸，堵車概率，海拔高低，都是影響運(yùn)行成本的因素。