Нахождение пути с максимально минимальным весом
https://stackoverflow.com/questions/873126
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я пытаюсь разработать алгоритм поиска пути по ориентированному графу.Это необычный путь, и я не могу найти никаких упоминаний о том, что что-то подобное уже делается.
Я хочу найти путь, который имеет максимальный минимальный вес.
Т.е.Если существуют два пути с весами 10->1->10 и 2->2->2, то второй путь считается лучшим, чем первый, поскольку минимальный вес (2) больше минимального веса первого (1 ).
Если кто-нибудь сможет найти способ сделать это или просто указать мне направление какого-нибудь справочного материала, это будет невероятно полезно :)
РЕДАКТИРОВАТЬ::Кажется, я забыл упомянуть, что пытаюсь попасть из конкретной вершины в другую конкретную вершину.Очень важный момент :/
РЕДАКТИРОВАТЬ2::Как заметил кто-то ниже, я должен подчеркнуть, что веса ребер неотрицательны.
Решение
Используйте либо Прим или Крускала алгоритм.Просто измените их, чтобы они останавливались, когда обнаруживают, что вершины, о которых вы спрашиваете, связаны.
РЕДАКТИРОВАТЬ:Вы просите максимальный минимум, но ваш пример выглядит так, будто вы хотите минимальный максимум.В случае максимального минимума алгоритм Краскала не будет работать.
РЕДАКТИРОВАТЬ:Пример правильный, моя ошибка.Тогда сработает только алгоритм Прима.
Другие советы
я копирую этот ответ и добавление, а также добавление моего доказательства правильности алгоритма:
Я бы использовал какой-нибудь вариант Дейкстры.Псевдокод ниже я взял прямо из Википедии и изменил всего 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(V-W)))
Индуктивный шаг:Предположим, 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)) в целом сравнимо с Дейкстрой/Краскалом/Примом O(|E|log |V|) (и я тоже не могу сразу увидеть этому подтверждение).
Эту проблему можно решить с помощью алгоритма в стиле 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 и обработать всех его соседей. снова.
Я не уверен, что Прим будет здесь работать.Возьмем этот контрпример:
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, будет выбран путь maxmin. 1 --> 2 --> 3 путь, а максимальное и минимальное расстояние достигается для пути, проходящего через 4.
Хорошо, отвечаю здесь на свой вопрос, просто чтобы попытаться получить отзыв о предварительном решении, которое я разработал перед публикацией здесь:
Каждый узел хранит «фрагмент пути», это пока весь путь до него самого.
0) установить текущую вершину в качестве начальной вершины
1) Сгенерировать все фрагменты пути из этой вершины и добавить их в приоритетную очередь.
2) Возьмите фрагмент сверху из приоритетной очереди и установите текущую вершину в конечную вершину этого пути.
3) Если текущая вершина является целевой вершиной, верните путь
4) перейти к 1
Однако я не уверен, что это будет лучший путь, я думаю, что условие выхода на третьем этапе немного амбициозно.Однако я не могу придумать лучшего условия выхода, поскольку этот алгоритм не закрывает вершины (на вершину можно ссылаться в любом количестве фрагментов пути), вы не можете просто ждать, пока все вершины будут закрыты (как у Дейкстры для пример)
Вы все еще можете использовать Дейкстру!
Вместо использования + используйте оператор 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)).
РЕДАКТИРОВАТЬ:ой, подождите, это в основном то, что вы опубликовали.РЖУ НЕ МОГУ.
