加油站问题 - 最便宜和最少的加油站

Question

我正在处理一个包含以下内容的问题：您驾驶的汽车具有一定的燃料使用量 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）
前往每个加油站并通过加满油列出范围内的加油站（或终点）（因为汽车可以在加油站加满油，所以你可以加满油）我将其保存在一个列表，因此不会计算两次。
然后循环每个可以到达的油站并发生递归，然后我几乎保存了所需的最少停靠点并冲洗并重复，瞧，我得到了最小的答案（在我们的例子中) 停在 100 加油 10.00 升，支付 14.5 美元，然后停在 400 加油 48 升，支付 67.20 美元

我还存在的问题：

如何（甚至可能）将复杂度降低到 O(N log N) 或线性，以便可以检查所有（即使是 100 多个加油站）。目前，递归方法在递归中减少到 10 次以上的递归，这使得超过 100 个加油站的任何东西对于该算法来说几乎无法解决。
目前我的算法只加到到达下一个加油站或终点所需的燃料：如果第一个加油站比第一个加油站便宜，那么处理问题的最佳方法是什么第二，你可以加油 "n liters more" 所以你在第二个加油站买的升数更少。因为在理想情况下，您在旅行结束时还剩下 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);
        }
    }

Answer 1

tl;dr：按照评论中提到的论文，求解器的 C# 实现（如下）在一台老化的笔记本电脑上处理了大约 14 毫秒内 500 个随机分布的站的情况，因此特别是，它处理100 个站的情况很容易，并且比使用 MIP 求解器快几个数量级，如评论中所建议的那样。

通常，加油站问题（我们应该真正开始称其为充电站问题，但那是另一回事）假设起始燃料量为 0：更一般的情况可能会减少到 0 的情况在距离您的初始起点一定距离处添加一个带有免费燃料的新起点，这会导致汽车使用包含您给定数量的燃料的油箱到达您的初始起点。这可以在不破坏下面解决方案的一般复杂性的情况下完成。

注意到这一点，问题归结为To Fill or not to Fill: The Gas Station Problem, as noted by @PySeeker in the comments. In particular, $O(N \log N)$ seems optimistic. In the paper, the relevant theorem handles your case in $O(\Delta N^2 \log N)$, where $\Delta$ is minimum number of stops required (which you can easily precompute in linear time if necessary). Another paper, A fast algorithm for the gas station problem中描述的问题，描述了如何解决$O(\Delta N^2 + N^2 \log N)中的问题$，但我们只关注前一篇论文。

它的定理 2.2 解决了固定 $\Delta$ 的问题，您实际上只对可能的最低值感兴趣。由于它们的递归设置是为了解决增加 $\Delta$ 的问题，这相当于一旦 $A(s, \Delta, 0)$（在论文的符号中）变得有限，就简单地停止算法。

另请注意，与处理边缘权重形成度量的一般图的一般问题相比（above-mentioned 论文的第二篇中指出的要求，但由于某种原因未在第一篇中指出），您的顶点 $0, \dots, N - 1$ 和距离 $d_{uv} = d[v] - d[u]$.

情况更简单

实现算法时需要注意的一点是，虽然论文中的描述很好，但 pseudo-code 更像是 buggy/lacking（参见 this question） .下面我们实施启动算法所需的各种修复和运行，以及一些有助于提高性能的索引。

您在编辑中提到，除了最佳解决方案的价值外，您还希望获得实际采用的路径。下面的算法只输出值，即 $A(0, \Delta, 0)$，但是只要 table 值更新，通过在单独的 table 中跟踪 argmin，你我也会立即获得所需的路径。这完全类似于您将如何实施，例如Dijkstra 算法。

你没有在问题中指定语言，所以我冒昧地用C#写了这个；代码非常 C'y，因此如果需要 (s/List/ArrayList/g)，将它移植到 Java 应该很简单。符号遵循论文，所以让我简单地参考 comments/documentation（但我也很抱歉，如果没有手头的论文，实现可能无法阅读）。

解决方案并非一帆风顺：如上所述，存在具有更好复杂性的不同算法，也很自然地尝试该算法；这不是特别复杂。此外，手头的实现有一个不包括在内的自然性能优化：没有必要为所有 $q$ 增加 table；例如，源顶点$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)
{
    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];
        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 prices = Enumerable.Range(1, n).Select(_ => rng.NextDouble()).ToArray();
        var distances = Enumerable.Range(1, n).Select(_ => rng.NextDouble() * n).OrderBy(x => x).ToArray();
        var capacity = 15;
        sw.Start();
        var result = Solve(prices, distances, capacity);
        sw.Stop();
        var time = sw.Elapsed;
        Console.WriteLine($"{time} {result}");
        sw.Reset();
    }
}

加油站问题 - 最便宜和最少的加油站

Gas Station Problem - cheapest and least amount of stations

algorithm

optimization

mathematical-optimization

shortest-path

operations-research