我正在研究一个问题，这个问题包括：你开的车有一定的油耗
m（在我们的示例中，我们将行驶8l/100km），而您正行驶x长度的直线（示例：1000km）汽车以一定量的燃油f（例如：22l）起步你的车有一个G大小的油箱（例如：55L），还有加油站（每升价格）在直线上（例如100公里（1.45美元/升）、400公里（1.40美元/升）和900公里（1.22美元/升）。我很难创建的算法的目的是：用最少的站点（所以不是最便宜的路线，而是在加油站最少的站点）找到最便宜的方法，告诉用户在哪个加油站要装多少升汽油，要多少钱。
目前使用递归和for循环（假设O（n ^ 2）），我已经创建了一种算法，可以解决一些问题到一定的复杂性，它开始挣扎时，大约有100个加油站。
我的算法工作原理：
前往从一开始就可用的加油站（示例中的22L）
去每个加油站，列出加油站（或终点）的范围内有一个完整的油箱（因为汽车可以在加油站加油你可以有一个完整的油箱）我保存在一个列表中，所以它不计算两次。
然后对于循环，每一个可以到达的加油站，循环发生，我几乎节省了所需的最少的加油站，冲洗和重复，然后我得到了最小的答案，即（在我们的例子中）停止加油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);
}
}
最佳答案
tl；dr：根据评论中提到的论文，解算器的c实现（如下）在老化的笔记本电脑上处理大约14ms内的500个随机分布站的情况，因此特别是，这很容易处理100个站的情况，并且比使用mip解算器快几个数量级，如评论中所建议的。
一般来说，加油站问题（我们应该开始称之为充电站问题，但这是另一种情况）假设起始燃油量为0：更一般的情况下，可以通过在距离您的起始点一定距离处添加一个新的带有免费燃油的起始站，使汽车达到你最初的出发点是一个油箱，里面装着你的燃料。这可以在不破坏下面的解决方案的一般复杂性的情况下完成。
注意到这一点，这个问题可以归结为@pyseeker在评论中提到的“加油站问题”中所描述的要加油还是不加油。尤其是，$o（n\logn）$看起来很乐观。在本文中，相关定理在$o（\delta n^2\logn）$中处理您的情况，其中$\delta$是所需的最少停止次数（如果需要，您可以很容易地在线性时间中预计算）。另一篇文章A fast algorithm for the gas station problem描述了如何在$o（\delta n^2+n^2\logn）$中解决这个问题，但我们只关注前面的文章。
它的定理2.2解决了一个固定的$\delta$的问题，在这个问题中，您实际上只对最小的可能值感兴趣。由于它们的递归设置是为了解决增加$\Delta$的问题，这就相当于在论文符号中的$A（s、\Delta，0）$变为有限值时停止算法。
还要注意的是，与处理边权形成度量的一般图的一般问题（在上述论文的第二篇中指出了这一要求，但由于某些原因没有在第一篇中提到）相比，使用顶点$0、\dots、n-1$和距离$d{u v}=d[v]-d[u]$的情况更简单。
在实现该算法时有一点需要注意的是，虽然本文中的描述很好，但伪代码相当有缺陷/缺乏（参见this question）。下面我们实现算法的运行和运行所需的各种修复，以及一些索引以帮助提高性能。
您在编辑中提到，除了最优解的值之外，您还希望获得实际路径下面的算法只输出值，即$a（0，，，delta，0）$，但是只要在值表更新时在单独的表中跟踪argmin，就可以立即获得所需的路径。这完全类似于dijkstra算法的实现方式。
你没有在问题中指定一种语言，所以我冒昧地用c编写了这段代码，代码非常简洁，因此如果需要的话，应该很容易将它移植到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();
}
}