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

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 个加油站时，它开始挣扎。

我的算法是如何工作的:

• 前往一开始可用的油 jar 站(示例中的 22l)
• 前往每个加油站并通过加满油箱列出范围内的加油站(或终点)(因为汽车可以在加油站加满油，所以你可以加满油箱)我将其保存在列表中所以它不会计算两次。
• 然后 for 循环每个可以到达的加油站并发生递归，然后我几乎保存了所需的最少停靠点并冲洗并重复，瞧，我得到了最小的答案，即(在我们的示例中)停靠100 加油 10.00 升，支付 14.5 美元，然后停在 400 加油 48 升，支付 67.20 美元

我还存在的问题:

• 我如何(甚至可能)将复杂性降低到 O(N log N) 或线性，以便可以检查所有(即使是 100 多个加油站)。目前，递归方法减少到递归中的 10 次以上递归，这使得该算法几乎无法解决超过 100 个加油站的问题。

• 目前，我的算法只提供到达下一个加油站或终点所需的燃料:如果第一个加油站比第二个便宜，那么解决问题的最佳方法是什么？加油“多 n 升”，这样您在第二个加油站购买的升数就会减少。因为在理想情况下，您在旅行结束时还剩下 0 升。

补充说明:

• 到达加油站时，燃料为 0 升，视为已到达。
• 编辑:必须找到价格相同且站点数量最少的所有路径。

我当前的代码(片段)我认为方法名称是 self 解释的，如果不是，请添加注释。，

    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# 实现(如下)在一台老化的笔记本电脑上处理 500 个随机分布站点的情况大约需要 14 毫秒，因此特别是，它处理了 100 个站点正如评论中所建议的那样，站的情况很容易，并且比使用 MIP 求解器快几个数量级。

通常，加油站问题(我们应该真正开始称其为充电站问题，但那是另一回事)假设起始燃料量为 0:更一般的情况可以通过添加新的起点站与您的初始起点有一定距离的免费燃料，使汽车到达您的初始起点，油箱中装有您给定的燃油量。这可以在不破坏下面解决方案的一般复杂性的情况下完成。

注意这一点，问题归结为 To Fill or not to Fill: The Gas Station Problem 中描述的问题, 作为 noted by @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 )。下面我们实现启动和运行算法所需的各种修复，以及一些有助于提高性能的索引。

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

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

解决方案并非一帆风顺:如上所述，存在一种具有更好复杂性的不同算法，尝试使用该算法也是很自然的；这不是特别复杂。此外，手头的实现有一个未包含的自然性能优化:没有必要为所有 $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)
{
    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();
    }
}