我有一个运输公司程序，由 Dijkstra 计算出最佳路线。城市作为顶点，路线作为边。求边缘的权重。我用线将地图中的城市连接起来并测量它。然后我接受它作为边缘的重量。但在现实生活中的路线并不直。那么我该如何解决呢？在此处输入图像描述
在我的项目中，我必须通过创建 Software 来解决后勤问题。谁能告诉我要解决什么？
user5602602
问问题
75 次
1 回答
0
正如您已经发现的那样，问题并不像看起来那么简单。首先，只连接主要城市是一个坏主意，因为它们可能没有直接与高速公路相连（如果不是美国的话）。
这是你目前的想法：
我的建议是尝试让每个小城市以有意义的方式获取，并将其作为顶点添加到您的Dijkstra:
现在，我们可以看到现实世界中实际存在的方式。从我们的图表来看，我们可能会认为使用底部路径应该更有效。但是，如果我们发现了这一点怎么办：
现在我们可以很容易地得出结论，上面的路径实际上要好得多，因为你可以实现两倍于底部路径的速度。这是非常精确的分类吗？不，这不对。我们可能想考虑每条路上的流量，并动态改变边的权重。但这对于您的基本实现来说可能太多了。
我最终会做的是想想我几乎可以单独或在很少帮助的情况下收集哪些数据。所以我绝对可以：
- 以某种方式废弃一些关于从 A 点到达 B 点的实际方式的数据；好的参考是Google Maps API或Bing Maps API；
- 沿途聚集小城市，寻找从 A 点到 B 点的真实世界道路；
- 尝试找出速度限制在哪里（如果有任何数据库）
实际上，您可能想全力以赴，Google Maps或者Bing Maps让他们为您提供最好的道路。他们都有你需要的任何道路的实际数据。您无法像他们那样收集尽可能多的数据。如果您觉得这是您可以做到的，那么您将所有东西都放在盘子上。
如果不是，我会采用混合方式——从任何地图 API 获取一些重要数据，然后将其用于我的Dijkstra算法，然后使用这些数据编写一个简单的算法，根据可能的修改器（速度限制、交通如果 API 提供它等等）。
于 2016-04-02T18:34:53.990 回答