我正在研究一个包含以下内容的问题：您正在驾驶一辆燃油消耗量为 m 的汽车（在我们的示例中，我们将采用 8l/100km）并且您正在驾驶长度为 x 的直道（例如：1000km）。汽车以一定量的燃料 f 启动（例如：22l）。您的汽车有一个大小为 g 的油箱（例如：55 升），并且在直道周围（例如 100 公里（1.45 美元/升）、400 公里（1.40 美元/升）和 900 公里）有加油站（每升价格） (1.22$/l). 我很难创建算法的目标是：用最少的停靠点（所以不是最便宜的路线，而是在加油站停靠最少的路线）找到最便宜的方式并告诉用户他必须在哪个加油站加油多少升以及需要多少钱。
目前使用递归和for循环（大概是O（n ^ 2））我已经创建了一种算法，可以解决某些复杂度达到一定程度的问题，当有大约100个加油站时它开始挣扎。
我的算法是如何工作的：
- 转到从一开始就可用的油箱站（示例中的 22l）
- 去每个油箱站并通过加满油箱来列出范围内的油箱站（或终点）（因为汽车可以在油箱站加油，你可以加满油箱）我确实将它保存在一个列表中，所以它不是计算了两次。
- 然后 for 循环每个可以到达的油箱站并发生递归，然后我几乎保存了所需的最少停止次数并冲洗并重复，瞧我得到最小的答案，即（在我们的示例中）停止在 100 加油10.00 升，支付 14.5 美元，然后停在 400 加油 48 升，支付 67.20 美元
我仍然存在的问题：
我如何（甚至可能）将复杂性降低到 O(N log N) 或线性，以便可以检查所有（即使是 100 多个加油站）。目前，递归方法下降到 10 次以上的递归，这使得该算法几乎无法解决超过 100 个加油站的任何问题。
目前，我的算法只加油到达下一个加油站或终点所需的燃料：如果第一个加油站比第二个加油站便宜，并且你可以多加油“n升，那么解决问题的最佳方法是什么？ “所以你在第二个加油站买的少了。因为在理想情况下，您在行程结束时还剩 0 升。
额外说明：
- 到达加油站的燃油为 0 升算作已经到达。
- 编辑：必须找到价格相同且站点数量最少的所有路径。
我当前的代码（片段）我认为方法名称是自我解释的，如果不是，请添加注释。，
void findRoutes(List<GasStation> reachableStations, List<GasStation> previousStations) {
int currentSteps = previousStations.size();
if (currentSteps > leastSteps) {
return;
}
// Reached the end (reachableStations will be null if it can reach the end)
if (reachableStations == null) {
// less steps
if (currentSteps < leastSteps) {
routes.clear();
routes.add(previousStations);
leastSteps = previousStations.size();
return;
} else {
// same amount of steps
routes.add(previousStations);
return;
}
}
// would be too many steps
if (currentSteps + 1 > leastSteps) {
return;
}
// Check those further away so we get a smaller step amount quicker
Collections.reverse(reachableStations);
for (GasStation reachableStation : reachableStations) {
List<GasStation> newPrevious = new LinkedList<>(previousStations);
newPrevious.add(reachableStation);
findRoutes(reachableStation.getReachableGasStations(), newPrevious);
}
}