Редактирование: Алгоритм Штор-Вагнера нахождения минимального разреза

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
  
 
== Необходимые определения ==
 
== Необходимые определения ==
<tex>G</tex> - неориентированный взвешенный граф с <tex>n</tex> вершинами и <tex>m</tex> рёбрами.
+
<tex>G</tex> - неориентированный взвешенный граф с <tex>n</tex> вершинами и <tex>m</tex> ребрами.
 
{{Определение |definition=
 
{{Определение |definition=
 
'''Разрезом''' называется такое разбиение множества <tex>V</tex> на два подмножества <tex>A</tex> и <tex>B</tex>, что:
 
'''Разрезом''' называется такое разбиение множества <tex>V</tex> на два подмножества <tex>A</tex> и <tex>B</tex>, что:
Строка 17: Строка 17:
 
Эту задачу называют "глобальным минимальным разрезом". Глобальный минимальный разрез равен минимуму среди разрезов минимальной стоимости по всевозможным парам исток-сток. Хотя эту задачу можно решить с помощью любого алгоритма нахождения максимального потока (запуская его <tex>O(n^2)</tex> раз для всевозможных пар истока и стока), однако ниже описан гораздо более простой и быстрый алгоритм, предложенный Матильдой Штор (Mechthild Stoer) и Франком Вагнером (Frank Wagner) в 1994 г.
 
Эту задачу называют "глобальным минимальным разрезом". Глобальный минимальный разрез равен минимуму среди разрезов минимальной стоимости по всевозможным парам исток-сток. Хотя эту задачу можно решить с помощью любого алгоритма нахождения максимального потока (запуская его <tex>O(n^2)</tex> раз для всевозможных пар истока и стока), однако ниже описан гораздо более простой и быстрый алгоритм, предложенный Матильдой Штор (Mechthild Stoer) и Франком Вагнером (Frank Wagner) в 1994 г.
  
В общем случае допускаются петли и кратные рёбра, все кратные рёбра можно заменить одним ребром с их суммарным весом а петли не влияют на решение. Поэтому будем считать, что кратных рёбер и петель во входном графе нет.
+
В общем случае допускаются петли и кратные рёбра, все кратные рёбра можно заменить одним ребром с их суммарным весом а петли не влияют на решение. Поэтому будем считать, что кратных ребер и петель во входном графе нет.
  
 
== Алгоритм ==  
 
== Алгоритм ==  
Строка 26: Строка 26:
  
  
  minCut(граф G):
+
  minCut():
   v[i] - список вершин, которые были сжаты в i-тую (сначала заполняется i);
+
   v[i] - список вершин, которые были сжаты в i-тую(сначала заполняется i);
 
   for i = 1..n-1
 
   for i = 1..n-1
     A = Ø;
+
     обнуляем мн-во A;
     fill(w, 0);
+
     обнуляем w(связности всех вершин);
 
     for j = 1..n-1
 
     for j = 1..n-1
       s = {s <tex>\in</tex> V | s <tex>\notin</tex> A, w[s] - max};
+
       s = вершина не из A, для которой w[s] - максимальна;
 
       if (j != n-1)
 
       if (j != n-1)
         A += s;
+
         добавляем s в A;
 
         пересчитываем связность w[i] для остальных вершин;  
 
         пересчитываем связность w[i] для остальных вершин;  
 
         prev = s;
 
         prev = s;
Строка 41: Строка 41:
 
           minCost = w[s];
 
           minCost = w[s];
 
           minCut = v[s];
 
           minCut = v[s];
         s' = s <tex>\cup</tex> prev;
+
         s и prev объединяются в одну вершину;
  return minCut - список вершин в минимальном разрезе;
 
  
 
== Корректность алгоритма ==
 
== Корректность алгоритма ==
Строка 51: Строка 50:
 
Рассмотрим произвольный <tex>s</tex>-<tex>t</tex> разрез <tex>C</tex> и покажем, что его вес не может быть меньше веса разреза, состоящего из единственной вершины <tex>t</tex>:
 
Рассмотрим произвольный <tex>s</tex>-<tex>t</tex> разрез <tex>C</tex> и покажем, что его вес не может быть меньше веса разреза, состоящего из единственной вершины <tex>t</tex>:
 
   
 
   
: <tex dpi = '130'>w (\{t\}) \le w (C)</tex>.  
+
<tex dpi = '130'>w(\{t\}) \le w(C)</tex>.  
  
 
Пусть <tex>v</tex> - вершина, которую мы хотим добавить в <tex>A</tex>, тогда <tex>A_v</tex> - состояние множества <tex>A</tex> в этот момент. Пусть <tex>C_v</tex> - разрез множества <tex>A_v \cup v</tex>, индуцированный разрезом <tex>C</tex>. Вершина <tex>v</tex> - активная, если она и предыдущая добавленная вершина в <tex>A</tex> принадлежат разным частям разреза <tex>C</tex>, тогда для любой такой вершины:
 
Пусть <tex>v</tex> - вершина, которую мы хотим добавить в <tex>A</tex>, тогда <tex>A_v</tex> - состояние множества <tex>A</tex> в этот момент. Пусть <tex>C_v</tex> - разрез множества <tex>A_v \cup v</tex>, индуцированный разрезом <tex>C</tex>. Вершина <tex>v</tex> - активная, если она и предыдущая добавленная вершина в <tex>A</tex> принадлежат разным частям разреза <tex>C</tex>, тогда для любой такой вершины:
  
: <tex dpi = '130'>w (v, A_v) \le w (C_v)</tex>.  
+
<tex dpi = '130'>w(v, A_v) \le w(C_v)</tex>.  
  
<tex>t</tex> - активная вершина, для неё выполняется:
+
<tex>t</tex> - активная вершина, для нее выполняется:
  
: <tex dpi = '130'>w (t,A_t) \le w (C_t)</tex>  
+
<tex dpi = '130'>w(t,A_t) \le w(C_t)</tex>  
: <tex dpi = '130'>w (t,A_t) = w (\{t\}), w (C_t) = w (C)</tex>
+
<tex dpi = '130'>w(t,A_t) = w(\{t\}), w(C_t) = w(C)</tex>
  
 
Получили утверждение теоремы.
 
Получили утверждение теоремы.
Строка 66: Строка 65:
 
Для первой активной вершины <tex>v</tex> это неравенство верно, так как все вершины <tex>A_v</tex> принадлежат одной части разреза, а <tex>v</tex> -  другой. Пусть неравенство выполнено для всех активных вершин до <tex>v</tex>, включая <tex>v</tex>, докажем его для следующей активной вершины <tex>u</tex>.
 
Для первой активной вершины <tex>v</tex> это неравенство верно, так как все вершины <tex>A_v</tex> принадлежат одной части разреза, а <tex>v</tex> -  другой. Пусть неравенство выполнено для всех активных вершин до <tex>v</tex>, включая <tex>v</tex>, докажем его для следующей активной вершины <tex>u</tex>.
  
: <tex dpi = '130'> w (u,A_u) \equiv w (u,A_v) + w (u,A_u \setminus A_v)</tex> (*)
+
<tex dpi = '130'> w(u,A_u) \equiv w(u,A_v) + w(u,A_u \setminus A_v)</tex> (*)
  
 
Заметим, что  
 
Заметим, что  
  
: <tex dpi = '130'>w (u,A_v) \le w (v,A_v)</tex> (**)
+
<tex dpi = '130'>w(u,A_v) \le w(v,A_v)</tex> (**)
  
 
вершина <tex>v</tex> имела большее значение <tex>w</tex>, чем <tex>u</tex>, так как была добавлена в <tex>A</tex> раньше.
 
вершина <tex>v</tex> имела большее значение <tex>w</tex>, чем <tex>u</tex>, так как была добавлена в <tex>A</tex> раньше.
 
По предположению индукции:
 
По предположению индукции:
  
: <tex dpi = '130'>w (v,A_v) \le w (C_v)</tex>
+
<tex dpi = '130'>w(v,A_v) \le w(C_v)</tex>
  
 
Следовательно из (**):
 
Следовательно из (**):
  
: <tex dpi = '130'>w(u,A_v) \le w(C_v)</tex>
+
<tex dpi = '130'>w(u,A_v) \le w(C_v)</tex>
  
 
А из (*) имеем:
 
А из (*) имеем:
  
: <tex dpi = '130'>w (u,A_u) \le w (C_v) + w (u,A_u \setminus A_v)</tex>  
+
<tex dpi = '130'>w(u,A_u) \le w(C_v) + w(u,A_u \setminus A_v)</tex>  
  
Вершина <tex>u</tex> и <tex>A_u \setminus A_v</tex> находятся в разных частях разреза <tex>C</tex>, значит <tex>w (u,A_u \setminus A_v)</tex> равна сумме весов рёбер, которые не входят в <tex>C_v</tex>, но входят в <tex>C_u</tex>.
+
Вершина <tex>u</tex> и <tex>A_u \setminus A_v</tex> находятся в разных частях разреза <tex>C</tex>, значит <tex>w(u,A_u \setminus A_v)</tex> равна сумме весов ребер, которые не входят в <tex>C_v</tex>, но входят в <tex>C_u</tex>.
  
: <tex dpi = '130'>w (u,A_u) \le w (C_v) + w (u,A_u \setminus A_v) \le w (C_u)</tex>
+
<tex dpi = '130'>w(u,A_u) \le w(C_v) + w(u,A_u \setminus A_v) \le w(C_u)</tex>
  
 
Что и требовалось доказать.
 
Что и требовалось доказать.
Строка 93: Строка 92:
  
 
== Асимптотика ==
 
== Асимптотика ==
#Нахождение вершины с наибольшей <tex>w</tex> за <tex>O (n)</tex>, <tex>n-1</tex> фаза по <tex>n-1</tex> итерации в каждой. В итоге имеем <tex>O (n^3)</tex>
+
1) Нахождение вершины с наибольшей <tex>w</tex> за <tex>O(n)</tex>, <tex>n-1</tex> фаза по <tex>n-1</tex> итерации в каждой. В итоге имеем <tex>O(n^3)</tex>
#Если использовать фибоначчиевы кучи для нахождения вершины с наибольшей <tex>w</tex>, то асимптотика составит <tex>O (nm + n^2 \log n)</tex>
 
#Если использовать двоичные кучи, то асимптотика составит <tex>O (nm \log n + n^2)</tex>
 
  
== Применение ==
+
2) Если использовать Фибоначчиевы кучи для нахождения вершины с наибольшей <tex>w</tex>, то асимптотика составит <tex>O(nm + n^2 \log n)</tex>
Нахождение разреза минимальной стоимости является основой в одном из методов сегментации изображений (сегментацией изображения называется разбиение его на некоторые области, непохожие по некоторому признаку).
 
  
Изображение представляется в виде взвешенного графа, вершинами которого являются точки изображения (как правило, пиксели, но, возможно, и большие области, от этого зависит качество сегментации, а также скорость её построения). Вес ребра представляет отражает "разницу" между точками (расстояние в некоторой метрике). Разбиение изображения на однородные области сводится к задаче поиска минимального разреза в графе. Специально для такого рода задач был предложен метод нахождения разреза минимальной стоимости [https://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0CDQQFjAB&url=http%3A%2F%2Fwww.cs.berkeley.edu%2F~malik%2Fpapers%2FSM-ncut.pdf&ei=cP2-UuqhAuSJ4gTnhYCwAg&usg=AFQjCNFn9GZPlFjDUgDofCScu6Wm47qMWQ&sig2=Yufd8LreEQKHe3NGnFVm7A&bvm=bv.58187178,d.bGE&cad=rjt Normalized Cut (J. Shi, J. Malik (1997))]
+
3) Если использовать Двоичные кучи, то асимптотика составит <tex>O(nm \log n + n^2)</tex>
  
 
== Источники ==
 
== Источники ==
 
* [http://e-maxx.ru/bookz/files/stoer_wagner_mincut.pdf Mechthild Stoer, Frank Wagner. A Simple Min-Cut Algorithm]
 
* [http://e-maxx.ru/bookz/files/stoer_wagner_mincut.pdf Mechthild Stoer, Frank Wagner. A Simple Min-Cut Algorithm]
 
* [http://e-maxx.ru/algo/stoer_wagner_mincut Алгоритм Штор-Вагнера]
 
* [http://e-maxx.ru/algo/stoer_wagner_mincut Алгоритм Штор-Вагнера]
* [http://cgm.computergraphics.ru/content/view/147 Методы сегментации изображения]
 
  
 
== Ссылки ==
 
== Ссылки ==
*[[Алгоритм Каргера для нахождения минимального разреза]]
+
*[http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Каргера_для_нахождения_минимального_разреза Алгоритм Каргера нахождения минимального разреза]
*[https://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0CDQQFjAB&url=http%3A%2F%2Fwww.cs.berkeley.edu%2F~malik%2Fpapers%2FSM-ncut.pdf&ei=cP2-UuqhAuSJ4gTnhYCwAg&usg=AFQjCNFn9GZPlFjDUgDofCScu6Wm47qMWQ&sig2=Yufd8LreEQKHe3NGnFVm7A&bvm=bv.58187178,d.bGE&cad=rjt Метод Normalized Cut]
 
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Задача о максимальном потоке]]
 
[[Категория: Задача о максимальном потоке]]

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

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

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

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