多地点最佳路线规划，有什么好程序?

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 778 天前的主题，其中的信息可能已经有所发展或是发生改变。

第 1 条附言 · 2022-10-07 11:45:33 +08:00

有现成的 app 能用吗？

11 条回复 • 2022-10-08 08:46:59 +08:00

somalia

2022-10-07 11:30:40 +08:00

没看懂问题，但是多目的地的话，高德地图不行嘛？

dcsuibian

2022-10-07 11:33:20 +08:00

没看懂，但感觉像拓扑

geelaw

2022-10-07 11:42:35 +08:00 via iPhone

大概看懂了但是你的问题大概是 NP-hard ，可以通过 Hamiltonian path 归约。

JinTianYi456

2022-10-07 11:43:42 +08:00

@somalia #1 它途径点是按顺序途径的，没法最佳路径。我举的例子有 P(1,1)*P(3,3)*P(2,2)*P(1,1)一共 12 种路线，找最短的
@dcsuibian #2

aneureka

2022-10-07 12:22:03 +08:00 via iPhone

听起来像是个能做的点🧐

SenLief

2022-10-07 13:04:26 +08:00 via iPhone

这个我也觉得可以，不知道为啥这几家地图没有做。

binux

2022-10-07 13:10:27 +08:00 via Android

我觉得没有意义，如果 234 之间距离差距很大，人眼就能看出来先后顺序，如果肉眼看不出来，距离往往不是决定性因素。

loveyu

2022-10-07 14:40:50 +08:00 via Android

之前做过行程助手应用，实际没几个人用

neptuno

2022-10-08 07:54:12 +08:00 via iPhone

挺难的，还得考虑路况，堵不堵车，限不限行，只有地图软件能做

JinTianYi456

2022-10-08 08:44:03 +08:00

@neptuno #9 感觉考虑多了，直接计算直线距离，告知先到哪再到哪就行。例子里，一共 12 种路线，告诉最短那条就行

neptuno

2022-10-08 08:46:59 +08:00 via iPhone

@JinTianYi456 #10 主要是你需求表达不是很明确，如果是导航，就得考虑这些，有些最近的不是最佳的