我想编写一个应用程序来帮助旅行推销员/音乐家计划他们的旅行。
所以这是关于制定一个高效的行程。
所以他们会输入他们的起点和终点以及他们想去的地方，程序会输出一条建议的路线，将这些点包含在 map 上。
假设为网络上的节点提供了边缘信息，建议的路线显然可以最大限度地减少时间、距离和财务成本。
有人可以发布一些伪代码或指向描述解决此问题所需的必要算法的站点的指针。
我看过 A*，但这似乎只是起点和终点。
欢迎任何想法
谢谢
亚历克斯
最佳答案
正如其他作者所写，这是一个旅行商问题。对于您的音乐家巡回演出计划，您需要(i)一种计算从一个位置到另一个位置的最低成本路径的算法 [通过物理网络] 和(ii)一种计算给定起点和终点位置的最佳位置顺序的算法以及其他限制条件，例如时间窗口。
(i) 可以用例如 Dijkstra、A*、Contraction Hierarchies 来解决
(ii) 可以用 Held-Karp、Branch and Bound/Cut [exactly] 和 Lin-Kernighan 或任何其他也适用于解决车辆路径问题 (VRP) [启发式] 的(元)启发式来解决
然而，有效地实现这些算法并不是几天的事情。因此，我建议您使用现有软件。对于 (i) GraphHopper将是一个完美的选择，对于 (ii) 您可以尝试 jsprit .两者都是用 Java 编写的并且是开源的。
关于algorithm - 寻找高效行程的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25042304/