Редактирование: Использование потенциалов Джонсона при поиске потока минимальной стоимости

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 10: Строка 10:
  
 
{{Определение
 
{{Определение
|definition=Пусть дана транспортная сеть <tex>\,G(V,E)</tex>, где <tex>V</tex> — множество вершин графа, а <tex>E</tex> — множество рёбер. Введем в каждой вершине потенциал <tex>p(v)</tex>. Тогда потенциальный вес (то есть стоимость) ребра <tex>(u, v)</tex> определяется как
+
|definition=Пусть дана транспортная сеть <tex>\,G(V,E)</tex>, где <tex>V</tex> — множество вершин графа, а <tex>E</tex> — множество рёбер. Введем в каждой вершине потенциал <tex>\,p_i</tex>. Тогда остаточная стоимость ребра <tex>\,c_{p_{ij}}</tex> определяется как
<tex>w_p(u, v) = w(u, v) + p(u) - p(v) </tex>
+
<tex>\,c_{p_{ij}} = c_{ij} + p_i - p_j </tex>
 
}}
 
}}
Заметим, что сумма потенциальных весов ребер вдоль любого пути отличается от суммы весов вдоль того же самого пути на разность между потенциалом первой и последней вершины.
+
Заметим, что сумма остаточных стоимостей ребер вдоль любого пути отличается от суммы стоимостей вдоль того же самого пути на разность между потенциалом первой и последней вершины.
  
 
== Использование потенциалов Джонсона ==
 
== Использование потенциалов Джонсона ==
Возьмём значения потенциалов в вершинах равными минимальному расстоянию от истока до них, а расстояния найдём с помощью [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]]. Таким образом, нам его придётся запустить всего один раз, а не на каждом шаге алгоритма. Однако, после добавления потока вдоль кратчайшего увеличивающего пути в сети могут появиться новые ребра, равно как и исчезнуть старые, и будет необходимо пересчитать потенциалы, чтобы они оставались корректными, то есть <tex>p(v)</tex> - длина кратчайшего пути от истока в вершину <tex>v</tex> в новой сети. Научимся делать это, не запуская каждый раз Форда-Беллмана.
+
Возьмём значения потенциалов в вершинах равными минимальному по цене расстоянию от стока до них или <tex>+\infty</tex>, если она недостижима. Так как <tex>\,c_{ij} + p_i</tex> — это длина какого-то пути до вершины <tex>\,j</tex>, а <tex>\,p_j</tex> — длина минимального пути, то <tex>c_{p_{ij}} \geqslant 0</tex>, что от нас и требовалось.
 +
Значения потенциалов найдём с помощью [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]]. Таким образом, нам его придётся запустить всего один раз, а не на каждом шаге алгоритма. Однако, после добавления потока вдоль кратчайшего увеличивающего пути в сети могут появиться новые ребра, равно как и исчезнуть старые, и будет необходимо пересчитать потенциалы, чтобы они оставались корректными, то есть <tex>p_v</tex> - длина кратчайшего пути от истока в вершину <tex>v</tex> в новой сети.
  
Для начала докажем, что в сети с корректными потенциалами <tex>w_p(u, v) = 0</tex> для любого ребра <tex>(u, v)</tex>, лежащего на кратчайшем пути из <tex>s</tex> в <tex>t</tex>.
+
Для начала докажем, что в сети с корректными потенциалами <tex>w_p(u, v) = 0</tex> для любого ребра <tex>(u, v)</tex>, лежащего на пути <tex>s \leadsto t</tex>.
 
 
Пусть <tex>s, v_1, v_2, \ldots, v_k, t</tex> - кратчайший путь из <tex>s</tex> в <tex>t</tex>, и <tex>d(u, v)</tex> - длина кратчайшего пути между вершинами <tex>u</tex> и <tex>v</tex> в исходной сети без потенциалов. Тогда <tex>w(s, v_1) + w(v_1, v_2) + \ldots + w(v_k, t) = d(s, t)</tex> и <tex>w_p(s, v_1) + w_p(v_1, v_2) + \ldots + w_p(v_k, t) = p(s) + w(s, v_1) + w(v_1, v_2) + \ldots + w(v_k, t) - p(t) = p(s) + d(s, t) - p(t) = p(s) + p(t) - p(t) = p(s) = 0</tex>. Таким образом, сумма всех потенциальных весов ребер на кратчайшем пути из <tex>s</tex> в <tex>t</tex> равна нулю. Кроме того, для любого ребра <tex>(u, v)</tex> <tex>w_p(u, v) \geq 0</tex>. Следственно, <tex>w_p(u, v) = 0</tex> для любого ребра <tex>(u, v)</tex>, лежащего на кратчайшем пути из <tex>s</tex> в <tex>t</tex>.
 
 
 
Более того, потенциальный вес всех ребер, обратных ребрам из кратчайшего пути, тоже равен <tex>0</tex>. И правда, <tex>w_p(u, v) = w(u, v) + d(s, u) - d(s, v) = 0</tex>. Умножив на <tex>-1</tex>, получаем <tex>0 = -w(u, v) - d(s, u) + d(s, v) = w(v, u) + d(s, v) - d(s, u) = w_p(v, u)</tex>
 
 
 
Из доказанных выше фактов следует, что при добавлении потока вдоль кратчайшего пути в сети с корректными потенциалами не появляется ребер с отрицательным весом (однако сами потенциалы уже становятся некорректными). Но так как ребер отрицательного веса нет, то мы можем пустить алгоритм Дейкстры из <tex>s</tex>, чтобы насчитать новые потенциалы. Пусть <tex>d_1(u, v)</tex> - кратчайшее расстояние, найденное алгоритмом Дейкстры, из <tex>u</tex> в <tex>v</tex> в сети с появившимися новыми ребрами, но старыми потенциалами, а <tex>d(u, v)</tex> - кратчайшее расстояние в новой сети без потенциалов. Нетрудно заметить, что <tex>d_1(s, v) = d(s, v) - p(v)</tex>, следственно, <tex>d(s, v) = d_1(s, v) + p(v)</tex>. Зная настоящие расстояния от истока до каждой вершины, мы теперь можем проставить новые потенциалы. Для каждой вершины <tex>v</tex> <tex>p(v) \gets d(s, v) = d_1(s, v) + p(v)</tex>.
 
 
 
Кроме того, мы также нашли новый кратчайший путь из истока из сток - а значит, на следующей итерации алгоритма мы можем пустить поток по нему и повторить все заново.
 
  
 
==Реализация==
 
==Реализация==
 
Модифицируем псевдокод из статьи про [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]:
 
Модифицируем псевдокод из статьи про [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]:
 +
<font size=30> НЕ ЧИТАЙТЕ, В РЕАЛИЗАЦИИ НАПИСАНА ПОЛНАЯ ЧУШЬ, после второй итерации, скорее всего, появятся ребра отрицательного веса </font>
  
 
  '''for''' <tex>e \in E</tex> {
 
  '''for''' <tex>e \in E</tex> {
 
       <tex>f[e] \leftarrow 0</tex>
 
       <tex>f[e] \leftarrow 0</tex>
 
  }
 
  }
  Запустим алгоритм Форда-Беллмана, в результате для каждой вершины: <tex>p[v] </tex> — кратчайшее расстояние <tex>s \leadsto v</tex>,  
+
  Запустим алгоритм Форда-Беллмана, в результате для каждой вершины: <tex>p[v] </tex> — расстояние <tex>s \leadsto e</tex>,  
 
  если за длину ребра принимается его стоимость.
 
  если за длину ребра принимается его стоимость.
 +
'''for''' <tex>e \in E</tex> {
 +
      <tex>c[e] \leftarrow c[e] + p[e.from] - p[e.to]</tex>
 +
}
 
  '''while''' (существует путь <tex>s \leadsto t</tex> в остаточной сети <tex>G_f</tex>) {
 
  '''while''' (существует путь <tex>s \leadsto t</tex> в остаточной сети <tex>G_f</tex>) {
       Восстановить <tex>P </tex> — кратчайший в смысле стоимости путь <tex>s \leadsto t</tex>, найденный на предыдущем шаге
+
       Найти <tex>P </tex> — кратчайший в смысле стоимости путь <tex>s \leadsto t</tex> с помощью алгоритма Дейкстры
 
       дополнить поток <tex>f</tex> вдоль <tex>P</tex>
 
       дополнить поток <tex>f</tex> вдоль <tex>P</tex>
      Запустить алгоритм Дейкстры из <tex>s</tex>, чтобы насчитать <tex>d_1</tex>
 
      '''for''' <tex>v \in V</tex> {
 
            <tex>p[v] \leftarrow p[v] + d_1[v]</tex>
 
      }
 
 
  }
 
  }
  

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: