我正在解决以下问题：您正在开车时使用了一定的燃油量m（在我们的示例中，我们将乘8l / 100km），并且您正在驾驶长度x的直线（示例：1000km）。汽车以一定量的燃料f（例如22l）起跑。您的汽车有一个尺寸为g的油箱（例如：55l），并且在直线路（例如100km（1.45 $ / l），400km（1.40 $ / l）和900km）周围绘制了加油站（每升价格） （1.22 $ / l）。我很难创建的算法的目的是：用最少的停靠点（不是最便宜的路线，而是在加油站停靠最少的路线）找到最便宜的方法并告诉用户他必须在哪个加油站加油多少升，费用是多少。
[当前使用递归和for循环（大概是O（n ^ 2）），我已经创建了一种算法，可以解决某些问题，直到达到一定的复杂度，当有大约100个加油站时，它就开始陷入困境。
我的算法如何工作：
我仍然有的问题：
我如何（甚至有可能）将复杂度降低为O（N log N）或线性，以便可以检查所有（即使有100多个加油站）。目前，递归方法在递归中下降到10多个递归，这使得该算法无法解决100个加油站以上的问题。
目前，我的算法仅加油到到达下一个加油站或终点所需的燃料：如果第一个加油站比第二个加油站便宜，那么解决该问题的最佳方法是什么“增加n升”，因此您在第二个加油站购买的升数更少。因为在理想情况下，旅行结束时还剩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);
}
}
tl; dr：通过遵循注释中提到的文章，求解器的C＃实现（如下）在老化的笔记本电脑上大约14毫秒内处理500个随机分布的工作站的情况，因此，特别是，此操作处理了100个工作站如注释中所建议的，这种情况很容易实现，并且比使用MIP求解器要快（且便宜）几个数量级。
[通常，加油站问题（我们应该真正开始将其称为充电站问题，但这是另一回事）假定起始燃料量为0：更一般的情况可以通过添加新的在距您的初始起点一定距离处有免费燃料的起步站，导致汽车使用装有给定数量的燃油的油箱到达您的初始起点。可以做到这一点，而不会破坏下面解决方案的一般复杂性。
注意，问题归结为在填充或不填充：加油站问题中描述的问题，如@PySeeker在评论中指出的。特别是$ O（N \ log N）$似乎是乐观的。在本文中，相关定理以$ O（\ Delta N ^ 2 \ log N）$处理您的情况，其中$ \ Delta $是所需的最小停靠点数（如有必要，您可以在线性时间轻松地进行预计算）。另一篇论文[[A fast algorithm for the gas station problem描述了如何解决$ O（\ Delta N ^ 2 + N ^ 2 \ log N）$中的问题，但在这里仅关注前一篇论文。
它的定理2.2解决了固定的$ \ Delta $问题，您实际上只对最低的感兴趣。由于设置它们的递归是为了解决增加$ \ Delta $的问题，因此，一旦在本文中用符号表示的$ A（s，\ Delta，0）$变为有限，就等于简单地停止了算法。也请注意，与处理边缘权重形成度量的一般图形的一般问题相比（上述第二篇文章中提到的要求，但由于某种原因在第一篇论文中没有提到），使用顶点的情况会更简单$ 0，\ dots，N-1 $和距离$ d_ {uv} = d [v]-d [u] $。
实现该算法时需要注意的一点是，尽管论文中的描述很好，但伪代码却有很多错误/缺失（例如this question）。下面我们实现启动和运行算法所需的各种修复程序，以及一些索引以帮助提高性能。
您在编辑中提到，除了最佳解决方案的价值之外，您还希望获得实际的路径。下面的算法仅输出值，即$ A（0，\ Delta，0）$，但是只要在值表更新时就在单独的表中跟踪argmin，您也会立即获得所需的路径。这完全类似于您将如何实现Dijkstra的算法。
您没有在问题中指定语言，所以我自由地用C＃编写了这种语言；该代码非常C'y，因此如有必要（s / List / ArrayList / g），应将其直接移植到Java。该符号紧随本文之后，因此我仅将其用于注释/文档（但我也很抱歉没有手头的论文，可能无法阅读该实现）。
解决方案并非一路走来：如上所述，存在一种具有更好复杂性的不同算法，当然也可以尝试这种算法；它并不特别复杂。而且，手头的实现具有自然的性能优化，该性能不包括在内：不必为所有$ q $增加表；例如，源顶点$ u = 0 $将仅取决于通过R[0]的前一行，因此，通过预先计算$ \ Delta $的最小值，我们可以避免一些多余的计算。
private static double Solve(double[] c, double[] d, double U)
{
int n = d.Length;
int t = n - 1;
var R = new int[n][];
var indep = new double[n][];
var GV = new List<List<double>>();
var GVar = new List<Dictionary<int, int>>();
for (int u = 0; u < n; u++)
{
var l = new List<int>();
for (int v = u + 1; v < n; v++)
{
if (d[v] - d[u] <= U)
l.Add(v);
else break;
}
R[u] = l.ToArray();
indep[u] = new double[l.Count];
}
for (int u = 0; u < n; u++)
{
var l = new List<double> { 0 };
var gvar = new Dictionary<int, int>();
int i = 1;
for (int w = 0; w < u; w++)
{
if (c[w] < c[u] && d[u] - d[w] <= U)
{
l.Add(U - (d[u] - d[w]));
gvar[w] = i++;
}
}
GV.Add(l);
GVar.Add(gvar);
}
int q = 0;
var Cq1 = new double[n][];
var Cq2 = new double[n][];
for (int i = 0; i < n; i++)
{
Cq1[i] = new double[GV[i].Count];
Cq2[i] = new double[GV[i].Count];
for (int j = 0; j < GV[i].Count; j++)
{
Cq1[i][j] = double.PositiveInfinity;
Cq2[i][j] = double.PositiveInfinity;
}
}
var toggle = true;
while (true)
{
var Cq = toggle ? Cq1 : Cq2;
var prev = !toggle ? Cq1 : Cq2;
toggle = !toggle;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < GV[i].Count; j++)
Cq[i][j] = double.PositiveInfinity;
}
for (int u = 0; u < n; u++)
{
Grow(u, q, t, c, d, U, R[u], GV[u], q == 0 ? null : prev, Cq, indep[u], GVar);
if (u == 0 && !double.IsPositiveInfinity(Cq[u][0]))
return Cq[u][0];
}
q++;
}
}
private static void Grow(int u, int q, int t, double[] c, double[] d, double U,
int[] r, List<double> gv, double[][] prev, double[][] ret, double[] indep,
List<Dictionary<int, int>> GVar)
{
int n = c.Length;
double cost = c[u];
if (q == 0 || u == t)
{
for (int i = 0; i < gv.Count; i++)
{
var g = gv[i];
if (q == 0 && g <= d[t] - d[u] && d[t] - d[u] <= U)
ret[u][i] = (d[t] - d[u] - g) * cost;
}
return;
}
for (var i = 0; i < r.Length; i++)
{
var v = r[i];
indep[i] = c[v] <= cost ? prev[v][0] + (d[v] - d[u]) * cost : prev[v][GVar[v][u]] + U * cost;
}
Array.Sort(indep, r);
var j = 0;
var w = r[j];
for (int gi = 0; gi < gv.Count; gi++)
{
var g = gv[gi];
if (j == r.Length) return;
while (g > d[w] - d[u] && c[w] <= cost)
{
j++;
if (j == r.Length) return;
w = r[j];
}
ret[u][gi] = indep[j] - g * cost;
}
}
示例用法和在500站情况下的基准测试：
static void Main(string[] args) { var rng = new Random(); var sw = new Stopwatch(); for (int k = 0; k < 100; k++) { int n = 500; var c = Enumerable.Range(1, n).Select(_ => rng.NextDouble()).ToArray(); var d = Enumerable.Range(1, n).Select(_ => rng.NextDouble() * n).OrderBy(x => x).ToArray(); var U = 15; sw.Start(); var result = Solve(c, d, U); sw.Stop(); var time = sw.Elapsed; Console.WriteLine($"{time} {result}"); sw.Reset(); } }