Нахождение пути с максимальным минимальным весом
Я пытаюсь разработать алгоритм поиска пути через ориентированный граф. Это не обычный путь, и я не могу найти никаких ссылок на что-то подобное, что уже сделано.
Я хочу найти путь, который имеет максимальный минимальный вес.
Т.е. если есть два пути с весами 10->1->10 и 2->2->2, то второй путь считается лучше первого, потому что минимальный вес (2) больше минимального веса первого (1).
Если кто-то может найти способ сделать это, или просто указать мне направление некоторых справочных материалов, это было бы невероятно полезно:)
РЕДАКТИРОВАТЬ:: Кажется, я забыл упомянуть, что я пытаюсь перейти от определенной вершины к другой конкретной вершине. Весьма важный момент: /
EDIT2:: Как кто-то ниже указал, я должен подчеркнуть, что граничные веса не являются отрицательными.
7 ответов
Используйте алгоритм Прима или Крускала. Просто измените их, чтобы они остановились, когда обнаружили, что вершины, о которых вы спрашиваете, связаны.
РЕДАКТИРОВАТЬ: Вы запрашиваете максимальный минимум, но ваш пример выглядит так, как будто вы хотите минимальный максимум. В случае максимального минимума алгоритм Крускала не будет работать.
РЕДАКТИРОВАТЬ: Пример в порядке, моя ошибка. Тогда будет работать только алгоритм Прима.
Я копирую этот ответ и добавляю также свое доказательство правильности алгоритма:
Я бы использовал какой-нибудь вариант Дейкстры. Я взял псевдокод ниже прямо из Википедии и изменил только 5 маленьких вещей:
- переименованный
distвwidth(из строки 3 и далее) - Инициализировал каждый
widthв-infinity(строка 3) - Инициализировал ширину источника
infinity(строка 8) - Установите критерий финиша на
-infinity(строка 14) - Модифицированы функция обновления и знак (строка 20 + 21)
1 function Dijkstra(Graph, source):
2 for each vertex v in Graph: // Initializations
3 width[v] := -infinity ; // Unknown width function from
4 // source to v
5 previous[v] := undefined ; // Previous node in optimal path
6 end for // from source
7
8 width[source] := infinity ; // Width from source to source
9 Q := the set of all nodes in Graph ; // All nodes in the graph are
10 // unoptimized – thus are in Q
11 while Q is not empty: // The main loop
12 u := vertex in Q with largest width in width[] ; // Source node in first case
13 remove u from Q ;
14 if width[u] = -infinity:
15 break ; // all remaining vertices are
16 end if // inaccessible from source
17
18 for each neighbor v of u: // where v has not yet been
19 // removed from Q.
20 alt := max(width[v], min(width[u], width_between(u, v))) ;
21 if alt > width[v]: // Relax (u,v,a)
22 width[v] := alt ;
23 previous[v] := u ;
24 decrease-key v in Q; // Reorder v in the Queue
25 end if
26 end for
27 end while
28 return width;
29 endfunction
Некоторое (ручное) объяснение, почему это работает: вы начинаете с источника. Оттуда у вас есть бесконечная способность к себе. Теперь вы проверяете всех соседей по источнику. Предположим, что края не все имеют одинаковую емкость (в вашем примере, скажем, (s, a) = 300). Тогда нет лучшего способа достичь b затем через (s, b), так что вы знаете лучший объем b, Вы продолжаете идти к лучшим соседям из известного набора вершин, пока не достигнете всех вершин.
Доказательство правильности алгоритма:
В любой точке алгоритма будет 2 набора вершин A и B. Вершины в A будут вершинами, к которым был найден правильный путь максимальной минимальной емкости. И множество B имеет вершины, на которые мы не нашли ответа.
Индуктивная гипотеза: На любом этапе все вершины в множестве A имеют правильные значения пути максимального минимального объема к ним. т.е. все предыдущие итерации верны.
Корректность базового случая: когда множество A имеет только вершину S. Тогда значение S равно бесконечности, что является правильным.
В текущей итерации мы устанавливаем
val[W] = max(val[W], min(val[V], width_between(VW)))
Шаг индукции. Предположим, W - вершина множества B с наибольшим значением val[W]. И W исключается из очереди, и W был установлен ответ val[W].
Теперь нам нужно показать, что каждый второй путь SW имеет ширину <= val[W]. Это будет всегда верно, потому что все другие способы достижения W пройдут через какую-то другую вершину (назовите это X) в множестве B.
А для всех остальных вершин X в множестве B val[X] <= val[W]
Таким образом, любой другой путь к W будет ограничен val[X], который никогда не будет больше val[W].
Таким образом, текущая оценка val [W] является оптимальной, и, следовательно, алгоритм вычисляет правильные значения для всех вершин.
Вы также можете использовать парадигму "бинарный поиск по ответу". То есть сделать бинарный поиск по весам, тестируя для каждого веса w можете ли вы найти путь в графе, используя только ребра с весом больше w,
Самый большой w на который вы можете (найденный через бинарный поиск) дает ответ. Обратите внимание, что вам нужно только проверить, существует ли путь, так что просто O(|E|) поиск в ширину / глубина вначале, а не кратчайший путь. Так что это O(|E|*log(max W)) в целом, сравнимо с Dijkstra / Kruskal / Prim's O(|E|log |V|) (и я не могу сразу увидеть доказательства этого тоже).
Я не уверен, что Prim будет работать здесь. Возьмите этот контрпример:
V = {1, 2, 3, 4}
E = {(1, 2), (2, 3), (1, 4), (4, 2)}
weight function w:
w((1,2)) = .1,
w((2,3)) = .3
w((1,4)) = .2
w((4,2)) = .25
Если вы примените Prim, чтобы найти путь maxmin от 1 до 3, то, начиная с 1, выберете 1 --> 2 --> 3 путь, в то время как максимальное-минимальное расстояние достигается для пути, который проходит через 4.
Это может быть решено с использованием алгоритма в стиле BFS, однако вам нужно два варианта:
- Вместо того, чтобы отмечать каждый узел как "посещенный", вы отмечаете его минимальным весом на пути, который вы выбрали, чтобы достичь его.
Например, если I и J являются соседями, I имеет значение w1, а вес ребра между ними равен w2, тогда J=min(w1, w2).
- Если вы достигнете отмеченного узла со значением w1, вам может потребоваться отметить и обработать его снова, если присваивается новое значение w2 (и w2>w1). Это необходимо, чтобы убедиться, что вы получите максимум всех минимумов.
Например, если I и J являются соседями, у I есть значение w1, J имеет значение w2, а вес ребра между ними равен w3, тогда, если min(w2, w3) > w1, вы должны заметить J и обработать всех его соседей. снова.
Хорошо, отвечая на мой собственный вопрос здесь, просто чтобы попытаться получить немного отзывов о предварительном решении, которое я выработал до публикации здесь:
Каждый узел хранит "фрагмент пути", это полный путь к себе до сих пор.
0) установить текущую вершину в начальную вершину
1) Генерация всех фрагментов пути из этой вершины и добавление их в очередь приоритетов
2) Снимите фрагмент с вершины приоритетной очереди и установите текущую вершину в конечную вершину этого пути.
3) Если текущая вершина является целевой, то верните путь
4) Перейти к 1
Я не уверен, что это найдет лучший путь, хотя, я думаю, что условие выхода на третьем шаге немного амбициозно. Хотя я не могу придумать лучшего условия выхода, так как этот алгоритм не закрывает вершины (на вершину можно ссылаться в любом количестве фрагментов пути), вы не можете просто подождать, пока все вершины будут закрыты (как Дейкстра для пример)
Вы все еще можете использовать Dijkstra's!
Вместо использования + используйте оператор min().
Кроме того, вы захотите сориентировать кучу /priority_queue так, чтобы самые большие вещи были на вершине.
Нечто подобное должно работать: (возможно, я пропустил некоторые детали реализации)
let pq = priority queue of <node, minimum edge>, sorted by min. edge descending
push (start, infinity) on queue
mark start as visited
while !queue.empty:
current = pq.top()
pq.pop()
for all neighbors of current.node:
if neighbor has not been visited
pq.decrease_key(neighbor, min(current.weight, edge.weight))
Гарантируется, что всякий раз, когда вы добираетесь до узла, вы выбираете оптимальный путь (поскольку вы найдете все возможности в порядке убывания, и вы никогда не сможете улучшить свой путь, добавив ребро)
Границы времени такие же, как у Дейкстры - O(Vlog(E)).
РЕДАКТИРОВАТЬ: о, подождите, это в основном то, что вы отправили. ЛОЛ.