Нахождение пути с максимальным минимальным весом

Question

Я пытаюсь разработать алгоритм поиска пути по ориентированному графу. Это не обычный путь, и я не могу найти никаких ссылок на что-либо подобное, уже сделанное.

Я хочу найти путь с максимальным минимальным весом.

т.е. Если есть два пути с весами 10-> 1-> 10 и 2-> 2-> 2, то второй путь считается лучше первого, поскольку минимальный вес (2) больше минимального веса первого (1). ).

Если кто-нибудь может найти способ сделать это или просто указать мне направление какого-либо справочного материала, это было бы невероятно полезно:)

РЕДАКТИРОВАТЬ :: Кажется, я забыл упомянуть, что я пытаюсь перейти из определенной вершины в другую конкретную вершину. Там довольно важный момент: /

EDIT2 :: Как заметил кто-то ниже, я должен подчеркнуть, что веса ребер неотрицательны.

Answer 1

Я копирую этот ответ и добавляю также добавление моего доказательства правильности алгоритма:

Я бы использовал какой-нибудь вариант Дейкстры . Я взял псевдокод ниже прямо из Википедии и изменил только 5 маленьких вещей:

1. Переименовано dist в width (со строки 3 на)
2. Инициализируется каждый width до -infinity (строка 3)
3. Инициализировал ширину источника как infinity (строка 8)
4. Установите критерий финиша на -infinity (строка 14)
5. Изменена функция обновления и подпись (строка 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 с наибольшим значением [W]. И W исключается из очереди, и W был установлен ответ val [W].

Теперь нам нужно показать, что каждый другой путь S-W имеет ширину <= val [W]. Это будет всегда верно, потому что все другие способы достижения W пройдут через какую-то другую вершину (назовите это X) в множестве B. </p>

И для всех других вершин X в множестве B val [X] <= val [W] </p>

Таким образом, любой другой путь к W будет ограничен val [X], который никогда не превышает val [W].

Таким образом, текущая оценка val [W] является оптимальной, и, следовательно, алгоритм вычисляет правильные значения для всех вершин.

Answer 2

Вы также можете использовать парадигму «бинарный поиск по ответу». То есть выполните бинарный поиск по весам, проверяя для каждого веса w, можете ли вы найти путь в графе, используя только ребра веса, превышающие w.

Наибольший w, на который вы можете (найденный через бинарный поиск), дает ответ. Обратите внимание, что вам нужно только проверить, существует ли путь, так что просто O (| E |) поиск в ширину / глубина вначале, а не кратчайший путь. Так что это O(|E|*log(max W)) в целом, сравнимо с Dijkstra / Kruskal / Prim's O(|E|log |V|) (и я тоже не могу сразу увидеть доказательства этого).

Answer 3

Используйте алгоритм Прима или Крускала . Просто измените их, чтобы они прекратили, когда обнаружат, что вершины, о которых вы спрашиваете, связаны.

РЕДАКТИРОВАТЬ: Вы запрашиваете максимальный минимум, но ваш пример выглядит так, как будто вы хотите минимальный максимум. В случае максимального минимума алгоритм Крускала не будет работать.

РЕДАКТИРОВАТЬ: пример в порядке, моя ошибка. Тогда будет работать только алгоритм Прима.

Answer 4

Я не уверен, что 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, а расстояние max-min будет достигнуто для пути, проходящего через 4.

Answer 5

Это может быть решено с использованием алгоритма в стиле 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 и обработать все это опять соседи.

Answer 6

Вы все еще можете использовать Дейкстру!

Вместо использования + используйте оператор 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)).

РЕДАКТИРОВАТЬ: о, подождите, это в основном то, что вы отправили. LOL.

Answer 7

Хорошо, отвечая на мой собственный вопрос здесь, просто чтобы попытаться получить немного отзывов о предварительном решении, которое я разработал до публикации здесь:

Каждый узел хранит «фрагмент пути», это полный путь к себе до сих пор.

0) установить текущую вершину в начальную вершину
1) Сгенерируйте все фрагменты пути из этой вершины и добавьте их в очередь приоритетов.
2) Снимите фрагмент с вершины приоритетной очереди и установите текущую вершину в конечную вершину этого пути.
3) Если текущая вершина является целевой, то верните путь
4) Перейти к 1

Я не уверен, что это найдет лучший путь, хотя, я думаю, что условие выхода на третьем шаге немного амбициозно. Однако я не могу придумать лучшего условия выхода, так как этот алгоритм не закрывает вершины (на вершину можно ссылаться в любом количестве фрагментов пути), вы не можете просто ждать, пока все вершины будут закрыты (как Дейкстра для пример)