Использование потенциалов Джонсона при поиске потока минимальной стоимости — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
== Потенциал Джонсона ==
 
== Потенциал Джонсона ==
 
{{Определение
 
{{Определение
|definition=Пусть дана транспортная сеть <math>\,G(V,E)</math>. Введем в каждой вершине потенциал <math>\,P_i</math>. Тогда остаточная стоимость ребра <math>\,C_{P_{ij}}</math> определяется как
+
|definition=Пусть дана транспортная сеть <tex>\,G(V,E)</tex>. Введем в каждой вершине потенциал <tex>\,P_i</tex>. Тогда остаточная стоимость ребра <tex>\,C_{P_{ij}}</tex> определяется как
<math>\,C_{P_{ij}} = C_{ij} + P_i - P_j </math>
+
<tex>\,C_{P_{ij}} = C_{ij} + P_i - P_j </tex>
 
}}
 
}}
 
Заметим что сумма остаточных стоимостей ребер вдоль любого пути отличается от суммы стоимостей вдоль того же самого пути на разность между потенциалом первой и последней вершины.
 
Заметим что сумма остаточных стоимостей ребер вдоль любого пути отличается от суммы стоимостей вдоль того же самого пути на разность между потенциалом первой и последней вершины.
  
 
== Использование потенциалов Джонсона ==
 
== Использование потенциалов Джонсона ==
Если <math>\forall i, j \,C_{P_{ij}} \geqslant 0</math> то при поиске минимального по стоимости пути от истока до стока можно пользоваться алгоритмом Дейкстры, а не алгоритмом Форда-Беллмана, что сильно улучшает ассимптотику алгоритма.  
+
Если <tex>\forall i, j \,C_{P_{ij}} \geqslant 0</tex> то при поиске минимального по стоимости пути от истока до стока можно пользоваться алгоритмом Дейкстры, а не алгоритмом Форда-Беллмана, что сильно улучшает ассимптотику алгоритма.  
  
Пусть каждом шаге алгоритма значения потенциалов в вершинах будут равны минимальному по цене расстоянию от стока до них, или <math>+\infty</math> если она недостижима. Так как <math>\,C_{ij} + P_i</math> это длина какого-то пути до вершины <math>\,j</math>, а <math>\,P_j</math> - длина минимального пути, то <math>C_{P_{ij}} \geqslant 0</math>, что от нас и требовалось.
+
Пусть каждом шаге алгоритма значения потенциалов в вершинах будут равны минимальному по цене расстоянию от стока до них, или <tex>+\infty</tex> если она недостижима. Так как <tex>\,C_{ij} + P_i</tex> это длина какого-то пути до вершины <tex>\,j</tex>, а <tex>\,P_j</tex> - длина минимального пути, то <tex>C_{P_{ij}} \geqslant 0</tex>, что от нас и требовалось.

Версия 01:29, 16 января 2011

Потенциал Джонсона

Определение:
Пусть дана транспортная сеть [math]\,G(V,E)[/math]. Введем в каждой вершине потенциал [math]\,P_i[/math]. Тогда остаточная стоимость ребра [math]\,C_{P_{ij}}[/math] определяется как [math]\,C_{P_{ij}} = C_{ij} + P_i - P_j [/math]

Заметим что сумма остаточных стоимостей ребер вдоль любого пути отличается от суммы стоимостей вдоль того же самого пути на разность между потенциалом первой и последней вершины.

Использование потенциалов Джонсона

Если [math]\forall i, j \,C_{P_{ij}} \geqslant 0[/math] то при поиске минимального по стоимости пути от истока до стока можно пользоваться алгоритмом Дейкстры, а не алгоритмом Форда-Беллмана, что сильно улучшает ассимптотику алгоритма.

Пусть каждом шаге алгоритма значения потенциалов в вершинах будут равны минимальному по цене расстоянию от стока до них, или [math]+\infty[/math] если она недостижима. Так как [math]\,C_{ij} + P_i[/math] это длина какого-то пути до вершины [math]\,j[/math], а [math]\,P_j[/math] - длина минимального пути, то [math]C_{P_{ij}} \geqslant 0[/math], что от нас и требовалось.