[谜题]求最短的距离

回复
头像
523066680
Administrator
Administrator
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

[谜题]求最短的距离

帖子 523066680 »

[[ChinaUnix]最短的距离](http://bbs.chinaunix.net/thread-4244834-1-1.html)

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

例如,给出以下距离:
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


头像
rubyish
渐入佳境
渐入佳境
帖子: 52
注册时间: 2018年04月23日 09:58
联系:

Re: [谜题]求最短的距离

帖子 rubyish »

yiyangde:

代码: 全选

X017090Y018547
X017797Y017840
X018504Y017133
X019211Y016426
X009316Y019231
X010256Y018889
X011195Y018547
X012135Y018205
X013075Y017863
X017090Y019962
X017797Y019254
X018504Y018547
X019211Y017840
X019918Y017133
X009658Y020171
X010598Y019829
X011537Y019487
X012477Y019145
X013417Y018803
X017797Y020669
X018504Y019962
X019211Y019254
X019918Y018547

将以上坐标按最优路径排序,即用最短的总行程将所有坐标走一遍。

:crazylaugh4 : 实际文件中有上万甚至十万个数据.
$_
回复

在线用户

正浏览此版面之用户: 没有注册用户 和 1 访客