忘记密码   免费注册 查看新帖 |

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT 徽章 文库 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
12下一页
最近访问板块 发新帖
查看: 2631 | 回复: 11

[数值计算] 最短的距离 [复制链接]

论坛徽章:
12
射手座
日期:2014-10-02 11:31:29程序设计版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-27 06:20:00程序设计版块每日发帖之星
日期:2016-05-27 06:20:00程序设计版块每日发帖之星
日期:2016-05-25 06:20:00每日论坛发贴之星
日期:2016-05-24 06:20:00程序设计版块每日发帖之星
日期:2016-05-24 06:20:0015-16赛季CBA联赛之深圳
日期:2016-05-23 15:33:59程序设计版块每日发帖之星
日期:2016-05-20 06:20:00程序设计版块每日发帖之星
日期:2016-04-26 06:20:00神斗士
日期:2015-12-03 09:27:3215-16赛季CBA联赛之八一
日期:2016-12-29 09:56:05
发表于 2016-05-07 15:44 |显示全部楼层
遇到这个问题,没什么思路。

请问各位大圣这种情况怎么处理呢。

  • 必须拜访每个地点一次。
  • 最短的距离是?
  • 列出一条有最短距离的途径


例如,给出以下距离:

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
复制代码

论坛徽章:
1
2015亚冠之萨济拖拉机
日期:2015-09-04 10:29:22
发表于 2016-05-07 15:48 |显示全部楼层
本帖最后由 tolilong 于 2016-05-07 15:49 编辑

已经所有点的距离?

论坛徽章:
4
程序设计版块每日发帖之星
日期:2015-10-14 06:20:00每日论坛发贴之星
日期:2015-10-14 06:20:00程序设计版块每日发帖之星
日期:2016-05-02 06:20:00程序设计版块每日发帖之星
日期:2016-05-08 06:20:00
发表于 2016-05-07 17:20 |显示全部楼层
本帖最后由 mswsg 于 2016-05-07 17:26 编辑

求大神。。!这个看了一会
一共有20个点, 要求一次经过每个点(点不重复),并且总距离最短。
已经给出任意每个点之间的距离(a,b)=x
第一个点的可能性是20,依次是19 ,18 ,... 3,2,1
。。。。。

论坛徽章:
383
摩羯座
日期:2014-05-06 10:32:5315-16赛季CBA联赛之广夏
日期:2016-01-12 17:08:14狮子座
日期:2014-05-05 22:31:17金牛座
日期:2014-02-26 17:49:58水瓶座
日期:2014-02-26 18:10:15白羊座
日期:2014-04-15 19:29:52寅虎
日期:2014-04-17 19:43:21酉鸡
日期:2014-04-19 21:24:10子鼠
日期:2014-04-22 13:55:24卯兔
日期:2014-04-22 14:20:58亥猪
日期:2014-04-22 16:13:09处女座
日期:2014-05-12 09:23:11
发表于 2016-05-07 18:17 |显示全部楼层
求一条路径最短的哈密尔顿回路,这种题目用shell来解,
真的合适吗?

论坛徽章:
12
射手座
日期:2014-10-02 11:31:29程序设计版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-27 06:20:00程序设计版块每日发帖之星
日期:2016-05-27 06:20:00程序设计版块每日发帖之星
日期:2016-05-25 06:20:00每日论坛发贴之星
日期:2016-05-24 06:20:00程序设计版块每日发帖之星
日期:2016-05-24 06:20:0015-16赛季CBA联赛之深圳
日期:2016-05-23 15:33:59程序设计版块每日发帖之星
日期:2016-05-20 06:20:00程序设计版块每日发帖之星
日期:2016-04-26 06:20:00神斗士
日期:2015-12-03 09:27:3215-16赛季CBA联赛之八一
日期:2016-12-29 09:56:05
发表于 2016-05-09 18:04 |显示全部楼层
回复 2# tolilong


     谢谢大圣指导。

论坛徽章:
12
射手座
日期:2014-10-02 11:31:29程序设计版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-27 06:20:00程序设计版块每日发帖之星
日期:2016-05-27 06:20:00程序设计版块每日发帖之星
日期:2016-05-25 06:20:00每日论坛发贴之星
日期:2016-05-24 06:20:00程序设计版块每日发帖之星
日期:2016-05-24 06:20:0015-16赛季CBA联赛之深圳
日期:2016-05-23 15:33:59程序设计版块每日发帖之星
日期:2016-05-20 06:20:00程序设计版块每日发帖之星
日期:2016-04-26 06:20:00神斗士
日期:2015-12-03 09:27:3215-16赛季CBA联赛之八一
日期:2016-12-29 09:56:05
发表于 2016-05-09 18:05 |显示全部楼层
回复 3# mswsg

谢谢大神指导。
大神们什么好的代码?
   

论坛徽章:
12
射手座
日期:2014-10-02 11:31:29程序设计版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-27 06:20:00程序设计版块每日发帖之星
日期:2016-05-27 06:20:00程序设计版块每日发帖之星
日期:2016-05-25 06:20:00每日论坛发贴之星
日期:2016-05-24 06:20:00程序设计版块每日发帖之星
日期:2016-05-24 06:20:0015-16赛季CBA联赛之深圳
日期:2016-05-23 15:33:59程序设计版块每日发帖之星
日期:2016-05-20 06:20:00程序设计版块每日发帖之星
日期:2016-04-26 06:20:00神斗士
日期:2015-12-03 09:27:3215-16赛季CBA联赛之八一
日期:2016-12-29 09:56:05
发表于 2016-05-09 18:08 |显示全部楼层
回复 4# Herowinter


这数据量也不大,大圣来一发
谢谢大圣指导。

论坛徽章:
383
摩羯座
日期:2014-05-06 10:32:5315-16赛季CBA联赛之广夏
日期:2016-01-12 17:08:14狮子座
日期:2014-05-05 22:31:17金牛座
日期:2014-02-26 17:49:58水瓶座
日期:2014-02-26 18:10:15白羊座
日期:2014-04-15 19:29:52寅虎
日期:2014-04-17 19:43:21酉鸡
日期:2014-04-19 21:24:10子鼠
日期:2014-04-22 13:55:24卯兔
日期:2014-04-22 14:20:58亥猪
日期:2014-04-22 16:13:09处女座
日期:2014-05-12 09:23:11
发表于 2016-05-09 18:16 |显示全部楼层
回复 7# patagonia2

这个问题远比你想象的复杂, 我算法没学好, 写不来.

维基百科:
寻找哈密顿路的确定算法虽然很难有多项式时间的,但是这并不意味着只能进行时间复杂度为O(n!*n)暴力搜索。
利用状态压缩动态规划,可以将时间复杂度降低到O(2^n*n^3)。
n=20, 优化算法也不简单.

你可以把这题发到一些高级语言的版块(如C++  Java)等, 看看有没有大神能帮你.
   

论坛徽章:
12
射手座
日期:2014-10-02 11:31:29程序设计版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-27 06:20:00程序设计版块每日发帖之星
日期:2016-05-27 06:20:00程序设计版块每日发帖之星
日期:2016-05-25 06:20:00每日论坛发贴之星
日期:2016-05-24 06:20:00程序设计版块每日发帖之星
日期:2016-05-24 06:20:0015-16赛季CBA联赛之深圳
日期:2016-05-23 15:33:59程序设计版块每日发帖之星
日期:2016-05-20 06:20:00程序设计版块每日发帖之星
日期:2016-04-26 06:20:00神斗士
日期:2015-12-03 09:27:3215-16赛季CBA联赛之八一
日期:2016-12-29 09:56:05
发表于 2016-05-10 15:42 |显示全部楼层
回复 8# Herowinter

谢谢大圣指导。

论坛徽章:
0
发表于 2016-05-10 20:51 |显示全部楼层
百度文库中搜了一篇文章(关于物流系统方面的)可能有点帮助。
QQ20160510.png (我没有发url的权限)

这个是较为典型的哈密尔顿回路问题。
参考A*算法和Dijkstra应该会有一些提示。
严格的说,shell不说不能做,而是shell天生并不是解决这类复杂问题的。

另外针对现代物流系统,我个人认为不能只单单考虑路径长短,货物装卸,堵车概率,海拔高低,都是影响运行成本的因素。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802020122
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP