Алгоритм Штор-Вагнера нахождения минимального разреза — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 17 промежуточных версий 4 участников)
Строка 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>, что:
Строка 15: Строка 15:
 
}}
 
}}
  
Эту задачу называют "глобальным минимальным разрезом". Глобальный минимальный разрез равен минимуму среди разрезов минимальной стоимости по всевозможным парам исток-сток. Хотя эту задачу можно решить с помощью любого алгоритма нахождения максимального потока (запуская его O(n^2) раз для всевозможных пар истока и стока), однако ниже описан гораздо более простой и быстрый алгоритм, предложенный Матильдой Штор (Mechthild Stoer) и Франком Вагнером (Frank Wagner) в 1994 г.
+
Эту задачу называют "глобальным минимальным разрезом". Глобальный минимальный разрез равен минимуму среди разрезов минимальной стоимости по всевозможным парам исток-сток. Хотя эту задачу можно решить с помощью любого алгоритма нахождения максимального потока (запуская его <tex>O(n^2)</tex> раз для всевозможных пар истока и стока), однако ниже описан гораздо более простой и быстрый алгоритм, предложенный Матильдой Штор (Mechthild Stoer) и Франком Вагнером (Frank Wagner) в 1994 г.
  
В общем случае допускаются петли и кратные рёбра, все кратные рёбра можно заменить одним ребром с их суммарным весом а петли не влияют на решение. Поэтому будем считать, что кратных ребер и петель во входном графе нет.
+
В общем случае допускаются петли и кратные рёбра, все кратные рёбра можно заменить одним ребром с их суммарным весом а петли не влияют на решение. Поэтому будем считать, что кратных рёбер и петель во входном графе нет.
  
 
== Алгоритм ==  
 
== Алгоритм ==  
 
Идея алгоритма довольно проста. Будем <tex>n-1</tex> раз повторять следующий процесс: находить минимальный разрез между какой-нибудь парой вершин <tex>s</tex> и <tex>t</tex>, а затем объединять эти две вершины в одну (создавать новую вершину, список смежности которой равен объединению списков смежности <tex>s</tex> и <tex>t</tex>). В конце концов, после <tex>n-1</tex> итерации, останется одна вершина. После этого ответом будет являться минимальный среди всех <tex>n-1</tex> найденных разрезов. Действительно, на каждой <tex>i</tex>-ой стадии найденный минимальный разрез <tex>\langle A,B \rangle</tex> между вершинами <tex>s_i</tex> и <tex>t_i</tex> либо окажется искомым глобальным минимальным разрезом, либо же, напротив, вершины <tex>s_i</tex> и <tex>t_i</tex> невыгодно относить к разным множествам, поэтому мы ничего не ухудшаем, объединяя эти две вершины в одну.
 
Идея алгоритма довольно проста. Будем <tex>n-1</tex> раз повторять следующий процесс: находить минимальный разрез между какой-нибудь парой вершин <tex>s</tex> и <tex>t</tex>, а затем объединять эти две вершины в одну (создавать новую вершину, список смежности которой равен объединению списков смежности <tex>s</tex> и <tex>t</tex>). В конце концов, после <tex>n-1</tex> итерации, останется одна вершина. После этого ответом будет являться минимальный среди всех <tex>n-1</tex> найденных разрезов. Действительно, на каждой <tex>i</tex>-ой стадии найденный минимальный разрез <tex>\langle A,B \rangle</tex> между вершинами <tex>s_i</tex> и <tex>t_i</tex> либо окажется искомым глобальным минимальным разрезом, либо же, напротив, вершины <tex>s_i</tex> и <tex>t_i</tex> невыгодно относить к разным множествам, поэтому мы ничего не ухудшаем, объединяя эти две вершины в одну.
  
Следовательно нам необходимо для данного графа найти минимальный разрез между какой-нибудь парой вершин <tex>s</tex> и <tex>t</tex>. Для этого вводим некоторое множество вершин <tex>A</tex>, которое изначально содержит единственную произвольную вершину <tex>s</tex>. На каждом шаге находится вершина, наиболее сильно связанная с множеством <tex>A</tex>, т.е. вершина <tex>v \not\in A</tex>, для которой следующая величина <tex dpi = "140">w(v,A) = \sum\limits_{(v,u) \in E, \atop u \in A} w(v,u)</tex> максимальна (максимальна сумма весов рёбер, один конец которых <tex>v</tex>, а другой принадлежит <tex>A</tex>).
+
Следовательно нам необходимо для данного графа найти минимальный разрез между какой-нибудь парой вершин <tex>s</tex> и <tex>t</tex>. Для этого вводим некоторое множество вершин <tex>A</tex>, которое изначально содержит единственную произвольную вершину <tex>s</tex>. На каждом шаге находится вершина, наиболее сильно связанная с множеством <tex>A</tex>, т.е. вершина <tex>v \not\in A</tex>, для которой следующая величина <tex dpi = "140">w(v,A) = \sum\limits_{(v,u) \in E, \atop u \in A} w(v,u)</tex> максимальна (максимальна сумма весов рёбер, один конец которых <tex>v</tex>, а другой принадлежит <tex>A</tex>). Этот процесс завершится, когда все вершины перейдут в множество <tex>A</tex>.
 +
 
 +
 
 +
 
 +
minCut(граф G):
 +
  v[i] - список вершин, которые были сжаты в i-тую (сначала заполняется i);
 +
  for i = 1..n-1
 +
    A = Ø;
 +
    fill(w, 0);
 +
    for j = 1..n-1
 +
      s = {s <tex>\in</tex> V | s <tex>\notin</tex> A, w[s] - max};
 +
      if (j != n-1)
 +
        A += s;
 +
        пересчитываем связность w[i] для остальных вершин;
 +
        prev = s;
 +
      else
 +
        if (w[s] < minCost)
 +
          minCost = w[s];
 +
          minCut = v[s];
 +
        s' = s <tex>\cup</tex> prev;
 +
  return minCut - список вершин в минимальном разрезе;
 +
 
 +
== Корректность алгоритма ==
 +
{{Теорема
 +
|statement=
 +
Если добавить в множество <tex>A</tex> по очереди все вершины, каждый раз добавляя вершину, наиболее сильно связанную с <tex>A</tex>, то пусть предпоследняя добавленная вершина {{---}} <tex>s</tex>, а последняя {{---}} <tex>t</tex>. Тогда минимальный <tex>s</tex>-<tex>t</tex> разрез состоит из единственной вершины {{---}} <tex>t</tex>
 +
|proof=
 +
Рассмотрим произвольный <tex>s</tex>-<tex>t</tex> разрез <tex>C</tex> и покажем, что его вес не может быть меньше веса разреза, состоящего из единственной вершины <tex>t</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 dpi = '130'>w (v, A_v) \le w (C_v)</tex>.
 +
 
 +
<tex>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>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_v) \le w (v,A_v)</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(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>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>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>
 +
 
 +
== Применение ==
 +
Нахождение разреза минимальной стоимости является основой в одном из методов сегментации изображений (сегментацией изображения называется разбиение его на некоторые области, непохожие по некоторому признаку).
 +
 
 +
Изображение представляется в виде взвешенного графа, вершинами которого являются точки изображения (как правило, пиксели, но, возможно, и большие области, от этого зависит качество сегментации, а также скорость её построения). Вес ребра представляет отражает "разницу" между точками (расстояние в некоторой метрике). Разбиение изображения на однородные области сводится к задаче поиска минимального разреза в графе. Специально для такого рода задач был предложен метод нахождения разреза минимальной стоимости [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))]
 +
 
 +
== Источники ==
 +
* [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://cgm.computergraphics.ru/content/view/147 Методы сегментации изображения]
 +
 
 +
== Ссылки ==
 +
*[[Алгоритм Каргера для нахождения минимального разреза]]
 +
*[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]
 +
 
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Задача о максимальном потоке]]

Текущая версия на 19:26, 4 сентября 2022

Необходимые определения

[math]G[/math] - неориентированный взвешенный граф с [math]n[/math] вершинами и [math]m[/math] рёбрами.

Определение:
Разрезом называется такое разбиение множества [math]V[/math] на два подмножества [math]A[/math] и [math]B[/math], что:
  • [math]A, B \subset V[/math];
  • [math]A, B \neq \emptyset[/math];
  • [math]A \cap B = \emptyset[/math];
  • [math]A \cup B = V[/math].


Определение:
Весом разреза называется сумма весов рёбер, проходящих через разрез, т.е. таких рёбер, один конец которых принадлежит [math]A[/math], а второй конец - [math]B[/math].
  • [math]w(A, B) =[/math] [math]\sum\limits_{uv \in E, u \in A, v \in B} w(u, v)[/math]


Эту задачу называют "глобальным минимальным разрезом". Глобальный минимальный разрез равен минимуму среди разрезов минимальной стоимости по всевозможным парам исток-сток. Хотя эту задачу можно решить с помощью любого алгоритма нахождения максимального потока (запуская его [math]O(n^2)[/math] раз для всевозможных пар истока и стока), однако ниже описан гораздо более простой и быстрый алгоритм, предложенный Матильдой Штор (Mechthild Stoer) и Франком Вагнером (Frank Wagner) в 1994 г.

В общем случае допускаются петли и кратные рёбра, все кратные рёбра можно заменить одним ребром с их суммарным весом а петли не влияют на решение. Поэтому будем считать, что кратных рёбер и петель во входном графе нет.

Алгоритм

Идея алгоритма довольно проста. Будем [math]n-1[/math] раз повторять следующий процесс: находить минимальный разрез между какой-нибудь парой вершин [math]s[/math] и [math]t[/math], а затем объединять эти две вершины в одну (создавать новую вершину, список смежности которой равен объединению списков смежности [math]s[/math] и [math]t[/math]). В конце концов, после [math]n-1[/math] итерации, останется одна вершина. После этого ответом будет являться минимальный среди всех [math]n-1[/math] найденных разрезов. Действительно, на каждой [math]i[/math]-ой стадии найденный минимальный разрез [math]\langle A,B \rangle[/math] между вершинами [math]s_i[/math] и [math]t_i[/math] либо окажется искомым глобальным минимальным разрезом, либо же, напротив, вершины [math]s_i[/math] и [math]t_i[/math] невыгодно относить к разным множествам, поэтому мы ничего не ухудшаем, объединяя эти две вершины в одну.

Следовательно нам необходимо для данного графа найти минимальный разрез между какой-нибудь парой вершин [math]s[/math] и [math]t[/math]. Для этого вводим некоторое множество вершин [math]A[/math], которое изначально содержит единственную произвольную вершину [math]s[/math]. На каждом шаге находится вершина, наиболее сильно связанная с множеством [math]A[/math], т.е. вершина [math]v \not\in A[/math], для которой следующая величина [math]w(v,A) = \sum\limits_{(v,u) \in E, \atop u \in A} w(v,u)[/math] максимальна (максимальна сумма весов рёбер, один конец которых [math]v[/math], а другой принадлежит [math]A[/math]). Этот процесс завершится, когда все вершины перейдут в множество [math]A[/math].


minCut(граф G):
  v[i] - список вершин, которые были сжаты в i-тую (сначала заполняется i);
  for i = 1..n-1
    A = Ø;
    fill(w, 0);
    for j = 1..n-1
      s = {s [math]\in[/math] V | s [math]\notin[/math] A, w[s] - max};
      if (j != n-1)
        A += s;
        пересчитываем связность w[i] для остальных вершин; 
        prev = s;
      else
        if (w[s] < minCost)
          minCost = w[s];
          minCut = v[s];
        s' = s [math]\cup[/math] prev;
  return minCut - список вершин в минимальном разрезе;

Корректность алгоритма

Теорема:
Если добавить в множество [math]A[/math] по очереди все вершины, каждый раз добавляя вершину, наиболее сильно связанную с [math]A[/math], то пусть предпоследняя добавленная вершина — [math]s[/math], а последняя — [math]t[/math]. Тогда минимальный [math]s[/math]-[math]t[/math] разрез состоит из единственной вершины — [math]t[/math]
Доказательство:
[math]\triangleright[/math]

Рассмотрим произвольный [math]s[/math]-[math]t[/math] разрез [math]C[/math] и покажем, что его вес не может быть меньше веса разреза, состоящего из единственной вершины [math]t[/math]:

[math]w (\{t\}) \le w (C)[/math].

Пусть [math]v[/math] - вершина, которую мы хотим добавить в [math]A[/math], тогда [math]A_v[/math] - состояние множества [math]A[/math] в этот момент. Пусть [math]C_v[/math] - разрез множества [math]A_v \cup v[/math], индуцированный разрезом [math]C[/math]. Вершина [math]v[/math] - активная, если она и предыдущая добавленная вершина в [math]A[/math] принадлежат разным частям разреза [math]C[/math], тогда для любой такой вершины:

[math]w (v, A_v) \le w (C_v)[/math].

[math]t[/math] - активная вершина, для неё выполняется:

[math]w (t,A_t) \le w (C_t)[/math]
[math]w (t,A_t) = w (\{t\}), w (C_t) = w (C)[/math]

Получили утверждение теоремы. Для доказательства воспользуемся методом математической индукции. Для первой активной вершины [math]v[/math] это неравенство верно, так как все вершины [math]A_v[/math] принадлежат одной части разреза, а [math]v[/math] - другой. Пусть неравенство выполнено для всех активных вершин до [math]v[/math], включая [math]v[/math], докажем его для следующей активной вершины [math]u[/math].

[math] w (u,A_u) \equiv w (u,A_v) + w (u,A_u \setminus A_v)[/math] (*)

Заметим, что

[math]w (u,A_v) \le w (v,A_v)[/math] (**)

вершина [math]v[/math] имела большее значение [math]w[/math], чем [math]u[/math], так как была добавлена в [math]A[/math] раньше. По предположению индукции:

[math]w (v,A_v) \le w (C_v)[/math]

Следовательно из (**):

[math]w(u,A_v) \le w(C_v)[/math]

А из (*) имеем:

[math]w (u,A_u) \le w (C_v) + w (u,A_u \setminus A_v)[/math]

Вершина [math]u[/math] и [math]A_u \setminus A_v[/math] находятся в разных частях разреза [math]C[/math], значит [math]w (u,A_u \setminus A_v)[/math] равна сумме весов рёбер, которые не входят в [math]C_v[/math], но входят в [math]C_u[/math].

[math]w (u,A_u) \le w (C_v) + w (u,A_u \setminus A_v) \le w (C_u)[/math]
Что и требовалось доказать.
[math]\triangleleft[/math]

Асимптотика

  1. Нахождение вершины с наибольшей [math]w[/math] за [math]O (n)[/math], [math]n-1[/math] фаза по [math]n-1[/math] итерации в каждой. В итоге имеем [math]O (n^3)[/math]
  2. Если использовать фибоначчиевы кучи для нахождения вершины с наибольшей [math]w[/math], то асимптотика составит [math]O (nm + n^2 \log n)[/math]
  3. Если использовать двоичные кучи, то асимптотика составит [math]O (nm \log n + n^2)[/math]

Применение

Нахождение разреза минимальной стоимости является основой в одном из методов сегментации изображений (сегментацией изображения называется разбиение его на некоторые области, непохожие по некоторому признаку).

Изображение представляется в виде взвешенного графа, вершинами которого являются точки изображения (как правило, пиксели, но, возможно, и большие области, от этого зависит качество сегментации, а также скорость её построения). Вес ребра представляет отражает "разницу" между точками (расстояние в некоторой метрике). Разбиение изображения на однородные области сводится к задаче поиска минимального разреза в графе. Специально для такого рода задач был предложен метод нахождения разреза минимальной стоимости Normalized Cut (J. Shi, J. Malik (1997))

Источники

Ссылки