Я полагаю, что вы можете решить эту проблему, используя модифицированную версию алгоритма Беллмана-Форда.
Беллман-Форд основан на следующем повторении динамического программирования, которое пытается найти кратчайший путь от некоторого начального узла s.друг другу узел, длина которого не превышает m для некоторого m.В качестве базового случая, когда вы рассматриваете пути нулевой длины, единственным достижимым узлом является s, а начальные значения равны
BF(s, t, 0) = infinity
BF(s, s, 0) = 0
Тогда, если мы знаем значения для пути длиной m, мы можем найтиэто для путей длиной m + 1, отметив, что старый путь все еще может быть действительным, или мы хотим расширить некоторый путь на длину один:
BF(s, t, m + 1) = min {
BF(s, t, m),
BF(s, u, m) + d(u, t) for any node u connected to t
}
Алгоритм в целом работает, отмечая, что любой кратчайшийпуть должен иметь длину не более n, а затем использовать вышеупомянутые рекуррентность и динамическое программирование для вычисления значения BF (s, t, n) для всех t.Общее время выполнения - O (EV), поскольку на каждом шаге нужно рассмотреть E ребер, а V вершин - всего.
Давайте посмотрим, как мы можем изменить этот алгоритм для решения вашей задачи.Во-первых, чтобы ограничить это путями длины k, мы можем просто отрезать итерацию Беллмана-Форда после нахождения всех кратчайших путей длины до k.Найти путь с наименьшей средней стоимостью немного сложнее.В каждой точке мы будем отслеживать две величины - длину кратчайшего пути, достигающего узла t, и среднюю длину этого пути.При рассмотрении новых путей, которые могут достигнуть t, наши варианты заключаются в том, чтобы либо сохранить ранее найденный путь (стоимость которого определяется кратчайшим путем, деленным на количество узлов в нем), либо расширить какой-либо другой путь на один шаг.Новая стоимость этого пути затем дается общей стоимостью до плюс длина ребра, деленная на количество ребер в старом пути плюс один.Если мы возьмем самый дешевый из них, а затем запишем как его стоимость, так и количество ребер, в конце мы вычислим путь с наименьшей средней стоимостью длины, не превышающей k за время O (kE).В качестве инициализации мы скажем, что путь от начального узла к себе имеет длину 0 и среднюю стоимость 0 (средняя стоимость не имеет значения, поскольку всякий раз, когда мы умножаем ее на количество ребер, мы получаем 0).Мы также скажем, что каждый второй узел находится на бесконечности расстояния, говоря, что средняя стоимость ребра равна бесконечности и что число ребер равно единице.Таким образом, если мы когда-нибудь попробуем вычислить стоимость пути, образованного путем расширения пути, он будет иметь среднюю бесконечность стоимости и не будет выбран.
Математически решение выглядит следующим образом.В каждой точке мы храним среднюю стоимость ребер и общее количество ребер в каждом узле:
BF(s, t, 0).edges = 1
BF(s, t, 0).cost = infinity
BF(s, s, 0).edges = 0
BF(s, s, 0).cost = 0
BF(s, t, m + 1).cost = min {
BF(s, t, m).cost,
(BF(s, u, m).cost * BF(s, u, m).edges + d(u, t)) / (BF(s, u, m).edges + 1)
}
BF(s, t, m + 1).edges = {
BF(s, t, m).edges if you chose the first option above.
BF(s, u, m).edges + 1 else, where u is as above
}
Обратите внимание, что это может не найти простой путь длины k, поскольку для минимизации средней стоимости может потребоваться, чтобы выВозьмите цикл с низкой (положительной или отрицательной) стоимостью несколько раз, чтобы снизить среднее значение.Например, если на графике есть цикл с нулевой стоимостью, вы должны просто брать его столько раз, сколько сможете.
РЕДАКТИРОВАТЬ : В ответ на ваши новые вопросы этот подход выигралне работает, если вы не хотите дублировать узлы на пути.Как указал @comestibles, эта версия проблемы является NP-трудной, поэтому, если P = NP, вы не должны ожидать, что найдете какой-либо хороший алгоритм с полиномиальным временем для этой проблемы.
Что касается времени выполнения,алгоритм, который я описал выше, работает за общее время O (кЕ).Это связано с тем, что каждая итерация вычисления повторения занимает время O (E), и существует всего k итераций.
Наконец, давайте посмотрим на предложенный вами код.Я перепечатал это здесь:
for (i = 0; i < n - 1; ++i) {
steps = 0;
for (j = 0; j < e; ++j) {
if ( (d[edges[j].u]+ edges[j].w)/(steps+1) < d[edges[j].v]/steps){
d[edges[j].v] = d[edges[j].u] + edges[j].w;
p[edges[j].v] = u;
steps++;
}
}
}
Ваш первый вопрос был о том, как принять во внимание k.Это можно легко сделать, переписав внешний цикл для подсчета до k, а не n - 1. Это дает нам такой код:
for (i = 0; i < k; ++i) {
steps = 0;
for (j = 0; j < e; ++j) {
if ( (d[edges[j].u]+ edges[j].w)/(steps+1) < d[edges[j].v]/steps){
d[edges[j].v] = d[edges[j].u] + edges[j].w;
p[edges[j].v] = u;
steps++;
}
}
}
Одна проблема, которую я замечаю, заключается в том, что в модифицированном алгоритме Беллмана-Форда каждый кандидат должен выбрать наилучший путь для независимого хранения своего числа ребер, поскольку оптимальный путь каждого узла может быть достигнут разным числом ребер. Чтобы исправить это, я бы предложил, чтобы массив d содержал два значения - количество ребер, необходимых для достижения узла, и среднюю стоимость узла по этому пути. Затем вы обновите свой код, заменив переменную steps в этих уравнениях на длины кэшированных путей.
Надеюсь, это поможет!