tl; dr: следуя статье, упомянутой в комментариях, реализация решателя на C # (ниже) обрабатывает случай 500 случайно распределенных станций примерно за 14 мс на устаревшем ноутбуке, поэтому, в частности, это обрабатывает 100случай станции, и это на несколько порядков быстрее, чем с помощью MIP-решателя, как это предлагается в комментариях.
Как правило, проблема заправочной станции (которую мы действительно должны начать называть проблемой зарядной станции, но это другоеstory) предполагает, что начальное количество топлива равно 0: более общий случай можно свести к случаю 0, добавив новую стартовую станцию со свободным топливом на расстоянии до начальной начальной точки, в результате чего автомобиль достигает начальной начальной точки сбак, содержащий указанное вами количество топлива. Это можно сделать, не нарушая общей сложности решения, приведенного ниже.
С учетом этого проблема сводится к описанной в Заполнять или не заполнять: Проблема АЗС , какотметил @PySeeker в комментариях. В частности, $ O (N \ log N) $ выглядит оптимистично. В статье соответствующая теорема обрабатывает ваш случай в $ O (\ Delta N ^ 2 \ log N) $, где $ \ Delta $ - минимальное количество требуемых остановок (которое вы можете легко предварительно вычислить за линейное время, если это необходимо). В другой статье, Быстрый алгоритм для задачи заправки , описывается, как решить эту проблему в $ 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] $.
При реализации алгоритма нужно соблюдать осторожность, покаописание в статье хорошо, псевдокод довольно глючит / отсутствует (см. например этот вопрос ). Ниже мы реализуем различные исправления, необходимые для запуска и работы алгоритма, а также некоторое количество индексации для повышения производительности.
Вы упоминаете в своих изменениях, что помимо значения оптимального решения, вы бытакже хотел бы получить фактические пути приняты. Приведенный ниже алгоритм выводит только значение, то есть $ A (0, \ Delta, 0) $, но, отслеживая argmin в отдельной таблице при каждом обновлении таблицы значений, вы сразу же получите нужный путь,Это полностью аналогично тому, как вы будете реализовывать, например, алгоритм Дейкстры.
Вы не указываете язык в вопросе, поэтому я позволил себе написать это на 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();
}
}