algorithm - 如何找到可能的最长路线？

Question

以下问题：

发动机（例如汽车）在笔直的道路上开始其旅程。它的消耗与距离成正比（例如 480 公里使用 1 个单位的燃料，因此 48 公里使用 10 个单位的燃料）。该发动机最多可以运输一个单位的燃料。

在起点供应 n0 个燃料单位。路线上的不同点有燃料库（例如 n1 @ d1、n2 @ d2 等），驾驶员可以在路线上的任何地方卸油。例如，对于一个单位的值 480 公里，驾驶员可以驾驶 160 公里创建一个具有 1/3 单位燃料的仓库，然后开回起点给他的发动机加油。

我正在寻找一种算法（或一些想法来找到一个）来找到可以达到的最大距离，具体取决于起始燃料和路线上的站点。

Answer 1

根据直觉，贪心算法应该是最优的，即通过最大化每个站点的可用燃料量，您正在最大化可能的路线。这只是我的观点，我假设“路线上的任何地方”是“实际上在任何仓库”。

贪心算法将如何工作？在每个时间点，您只有两个决定：“继续前进”或“返回上一个仓库进行补充”。只要能增加当前的仓库储备，贪婪者总会后退。

Answer 2

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

或者添加一个逻辑参数（最佳、最差）路径。

所以你可以保持相同的路径搜索而无需重复代码。