如何找到尽可能长的路由？

Question

以下问题：

发动机(例如汽车)在笔直的道路上开始它的旅程。它的消耗与距离成正比(例如，480公里使用一个单位的燃料，因此48公里使用十分之一的燃料)。这台发动机最多只能运输一个单位的燃料。

起始点是n0燃料单元的供应。路线上的不同地点是燃料库(例如n1 @ d1、n2 @ d2等)而且司机可以在路线上的任何地方卸油。例如，对于一个单位的值480公里，驾驶员可以驾驶160公里，创建一个有1/3单位燃料的仓库，然后开车回到起点为他的发动机补充燃料。

我正在寻找一个算法(或一些想法来找到一个)，以找到可以达到的最大距离，这取决于起始燃料和路线上的油库。

Answer 1

我认为您还可以“反转”a*，dijkstra方法中使用的"<=“比较。

或添加逻辑参数(最佳、最差)路径。

因此，您可以保持相同的路径搜索，而无需重复代码。

Answer 2

凭直觉，贪婪的算法应该是最优的，即通过最大化每个油库可用的燃油量，你就是在最大化可能的路线。这只是我的观点，我假设“路线上的任何地方”就是“实际上在任何站点”。

贪婪算法是如何工作的？在每个时间点，您只有两个决定要做：“继续前进”或“返回到前一个仓库重新填充”。贪婪的总是会搬回来，只要它会增加目前的仓库储备。