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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 50: Строка 50:
  
 
Время, затраченное на одну итерацию, определяется скоростью поиска кратчайшего пути.
 
Время, затраченное на одну итерацию, определяется скоростью поиска кратчайшего пути.
Если для этой цели использовать [[Алгоритм Дейкстры|алгоритм Дейкстры]] с Фиббоначевыми кучами, то поиск мы осуществим за <tex>O(V \log V + E)</tex>.
+
Если для этой цели использовать [[Алгоритм Дейкстры|алгоритм Дейкстры]] с Фиббоначевыми кучами, то поиск мы осуществим за <tex>O(V log V + E)</tex>.
  
 
Не стоит так же забывать, что для расчёта потенциалов мы один раз запустили Алгоритм Форда-Беллмана.
 
Не стоит так же забывать, что для расчёта потенциалов мы один раз запустили Алгоритм Форда-Беллмана.
В результате получим время работы <tex>O((V \log V + E) \cdot |f| + V E)</tex>.  
+
В результате получим время работы <tex>O((V log V + E) \cdot |f| + V E)</tex>.  
  
 
Это лучше, чем <tex>O((V E) \cdot |f|)</tex>, что получается при использовании [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]] для поиска кратчайшего пути на каждой итерации.
 
Это лучше, чем <tex>O((V E) \cdot |f|)</tex>, что получается при использовании [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]] для поиска кратчайшего пути на каждой итерации.
  
  
В применении к [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости|задаче о назначениях]]: пусть у нас есть <tex>N</tex> назначений. Построим специальным образом граф. Искомый поток в нём имеет имеет мощность <tex>N</tex>. Количество вершин  — <tex>O(N)</tex>, рёбер — <tex>O(N^2)</tex>. Итого получаем асимптотику <tex>O(N^2 \log N + 2N^3) = O(N^3)</tex>.
+
В применении к задаче [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости|о назначениях]]: пусть у нас есть <tex>N</tex> назначений. Построим специальным образом граф. Искомый поток в нём имеет имеет мощность <tex>N</tex>. Количество вершин  — <tex>O(N)</tex>, рёбер — <tex>O(N^2)</tex>. Итого получаем асимптотику <tex>O(N^3)</tex>.
  
 
== Литература ==
 
== Литература ==

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

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

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

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