最短的距离

patagonia2 发表于 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

请问各位大圣这种情况怎么处理呢。PIT-001 PIT-002 9665
PIT-001 PIT-003 5794
PIT-001 PIT-004 96
PIT-001 PIT-005 5750
PIT-001 PIT-006 6394
PIT-001 PIT-007 5750
PIT-001 PIT-008 3478
PIT-001 PIT-009 262
PIT-001 PIT-010 8954
PIT-001 PIT-011 3751
PIT-001 PIT-012 5253
PIT-001 PIT-013 6988
PIT-001 PIT-014 1364
PIT-001 PIT-015 9415
PIT-001 PIT-016 6156
PIT-001 PIT-017 6015
PIT-001 PIT-018 7931
PIT-001 PIT-019 5082
PIT-001 PIT-020 9891
PIT-002 PIT-003 6580
PIT-002 PIT-004 4325
PIT-002 PIT-005 5355
PIT-002 PIT-006 7221
PIT-002 PIT-007 4093
PIT-002 PIT-008 6098
PIT-002 PIT-009 2720
PIT-002 PIT-010 4662
PIT-002 PIT-011 9336
PIT-002 PIT-012 378
PIT-002 PIT-013 4632
PIT-002 PIT-014 3403
PIT-002 PIT-015 6736
PIT-002 PIT-016 7797
PIT-002 PIT-017 5479
PIT-002 PIT-018 9189
PIT-002 PIT-019 1372
PIT-002 PIT-020 4367
PIT-003 PIT-004 9601
PIT-003 PIT-005 6529
PIT-003 PIT-006 1255
PIT-003 PIT-007 2524
PIT-003 PIT-008 5562
PIT-003 PIT-009 5222
PIT-003 PIT-010 998
PIT-003 PIT-011 8214
PIT-003 PIT-012 3623
PIT-003 PIT-013 5083
PIT-003 PIT-014 470
PIT-003 PIT-015 6274
PIT-003 PIT-016 7125
PIT-003 PIT-017 6897
PIT-003 PIT-018 1281
PIT-003 PIT-019 9852
PIT-003 PIT-020 8675
PIT-004 PIT-005 6886
PIT-004 PIT-006 456
PIT-004 PIT-007 4762
PIT-004 PIT-008 5580
PIT-004 PIT-009 5893
PIT-004 PIT-010 3720
PIT-004 PIT-011 6098
PIT-004 PIT-012 8211
PIT-004 PIT-013 7543
PIT-004 PIT-014 6081
PIT-004 PIT-015 9590
PIT-004 PIT-016 4647
PIT-004 PIT-017 5801
PIT-004 PIT-018 9606
PIT-004 PIT-019 2766
PIT-004 PIT-020 5154
PIT-005 PIT-006 7815
PIT-005 PIT-007 3318
PIT-005 PIT-008 2698
PIT-005 PIT-009 8343
PIT-005 PIT-010 3150
PIT-005 PIT-011 8051
PIT-005 PIT-012 5387
PIT-005 PIT-013 5225
PIT-005 PIT-014 3237
PIT-005 PIT-015 6158
PIT-005 PIT-016 2743
PIT-005 PIT-017 8072
PIT-005 PIT-018 2154
PIT-005 PIT-019 7430
PIT-005 PIT-020 3015
PIT-006 PIT-007 3927
PIT-006 PIT-008 970
PIT-006 PIT-009 5107
PIT-006 PIT-010 9473
PIT-006 PIT-011 771
PIT-006 PIT-012 6491
PIT-006 PIT-013 33
PIT-006 PIT-014 5768
PIT-006 PIT-015 1480
PIT-006 PIT-016 2144
PIT-006 PIT-017 3695
PIT-006 PIT-018 8603
PIT-006 PIT-019 2669
PIT-006 PIT-020 4192
PIT-007 PIT-008 8087
PIT-007 PIT-009 3979
PIT-007 PIT-010 3726
PIT-007 PIT-011 2743
PIT-007 PIT-012 9232
PIT-007 PIT-013 217
PIT-007 PIT-014 4633
PIT-007 PIT-015 1088
PIT-007 PIT-016 2993
PIT-007 PIT-017 3154
PIT-007 PIT-018 8646
PIT-007 PIT-019 2484
PIT-007 PIT-020 4101
PIT-008 PIT-009 8297
PIT-008 PIT-010 9313
PIT-008 PIT-011 4124
PIT-008 PIT-012 8629
PIT-008 PIT-013 4267
PIT-008 PIT-014 7456
PIT-008 PIT-015 9067
PIT-008 PIT-016 4293
PIT-008 PIT-017 7649
PIT-008 PIT-018 7310
PIT-008 PIT-019 8391
PIT-008 PIT-020 3848
PIT-009 PIT-010 3381
PIT-009 PIT-011 6493
PIT-009 PIT-012 4667
PIT-009 PIT-013 2612
PIT-009 PIT-014 7146
PIT-009 PIT-015 9488
PIT-009 PIT-016 678
PIT-009 PIT-017 8957
PIT-009 PIT-018 8025
PIT-009 PIT-019 1089
PIT-009 PIT-020 2631
PIT-010 PIT-011 4976
PIT-010 PIT-012 5045
PIT-010 PIT-013 5178
PIT-010 PIT-014 8014
PIT-010 PIT-015 5851
PIT-010 PIT-016 357
PIT-010 PIT-017 5471
PIT-010 PIT-018 4935
PIT-010 PIT-019 9617
PIT-010 PIT-020 2907
PIT-011 PIT-012 1515
PIT-011 PIT-013 1778
PIT-011 PIT-014 1773
PIT-011 PIT-015 8704
PIT-011 PIT-016 3318
PIT-011 PIT-017 5180
PIT-011 PIT-018 582
PIT-011 PIT-019 9573
PIT-011 PIT-020 7458
PIT-012 PIT-013 6710
PIT-012 PIT-014 2171
PIT-012 PIT-015 9788
PIT-012 PIT-016 2127
PIT-012 PIT-017 7630
PIT-012 PIT-018 8959
PIT-012 PIT-019 5590
PIT-012 PIT-020 7108
PIT-013 PIT-014 9409
PIT-013 PIT-015 9030
PIT-013 PIT-016 3654
PIT-013 PIT-017 714
PIT-013 PIT-018 118
PIT-013 PIT-019 7472
PIT-013 PIT-020 1517
PIT-014 PIT-015 890
PIT-014 PIT-016 2776
PIT-014 PIT-017 7240
PIT-014 PIT-018 2120
PIT-014 PIT-019 3314
PIT-014 PIT-020 7544
PIT-015 PIT-016 6725
PIT-015 PIT-017 587
PIT-015 PIT-018 9877
PIT-015 PIT-019 1254
PIT-015 PIT-020 3023
PIT-016 PIT-017 9444
PIT-016 PIT-018 5608
PIT-016 PIT-019 3084
PIT-016 PIT-020 4228
PIT-017 PIT-018 7387
PIT-017 PIT-019 8076
PIT-017 PIT-020 6686
PIT-018 PIT-019 5275
PIT-018 PIT-020 816
PIT-019 PIT-020 7673

tolilong 发表于 2016-05-07 15:48

本帖最后由 tolilong 于 2016-05-07 15:49 编辑

已经所有点的距离？

mswsg 发表于 2016-05-07 17:20

本帖最后由 mswsg 于 2016-05-07 17:26 编辑

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

Herowinter 发表于 2016-05-07 18:17

求一条路径最短的哈密尔顿回路，这种题目用shell来解，
真的合适吗？

patagonia2 发表于 2016-05-09 18:04

回复 2# tolilong

谢谢大圣指导。

patagonia2 发表于 2016-05-09 18:05

回复 3# mswsg

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

patagonia2 发表于 2016-05-09 18:08

回复 4# Herowinter

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

Herowinter 发表于 2016-05-09 18:16

回复 7# patagonia2

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

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

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

patagonia2 发表于 2016-05-10 15:42

回复 8# Herowinter

谢谢大圣指导。{:yxh110:}

lll1985911 发表于 2016-05-10 20:51

百度文库中搜了一篇文章（关于物流系统方面的）可能有点帮助。
（我没有发url的权限）

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

另外针对现代物流系统，我个人认为不能只单单考虑路径长短，货物装卸，堵车概率，海拔高低，都是影响运行成本的因素。

页: [1] 2

Chinaunix's Archiver

最短的距离