Обсуждение:PSRS-сортировка — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Оптимизации)
 
(не показано 35 промежуточных версий 3 участников)
Строка 1: Строка 1:
 +
<b>Алгоритм Борувки</b> (англ. ''Borůvka's algorithm'') — алгоритм поиска минимального остовного дерева (англ. ''minimum spanning tree, MST'') во взвешенном неориентированном связном графе.
 +
Впервые был опубликован в 1926 году Отакаром Борувкой.
  
== Оптимизации ==
+
==Описание алгоритма==
=== Бинарные вставки ===
+
# Построим граф <tex>T</tex>. Изначально <tex>T</tex> содержит все вершины из <tex>G</tex> и не содержит ребер (каждая вершина в графе <tex>T</tex> {{---}} отдельная компонента связности).
Так как в среднем количество сравнений для <tex>j</tex>-го элемента равно <tex>j/2</tex>, следовательно общее количество сравнений приблизительно <tex>\frac {(1+2+3+...+N)}{2} \approx N^2/4</tex>, но это очень много даже при малых <tex>N</tex>. Суть этого заключается в том, что поиск позиции для вставки <tex>j</tex>-го элемента осуществляется бинарным поиском, вследствие чего количество сравнений для <tex>N</tex> элементов <tex>N \cdot \log_{2} N</tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить <tex>R_j</tex> элемент на <tex>i</tex>-тое место, всё ещё необходимо переместить <tex>j-i</tex> элементов. Что касается константы <tex>C</tex>, то <tex>C \cdot N \cdot (N/4+log_{2} N) \approx N^2/4</tex>, следовательно <tex>C=1/4</tex>.    
+
# Будем добавлять в <tex>T</tex> ребра следующим образом, пока <tex>T</tex> не является деревом
=== Двухпутевые вставки ===
+
#* Для каждой компоненты связности находим минимальное по весу ребро, которое связывает эту компоненту с другой.   
Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается потём сдвига элементов влево или вправо туда, куда выгоднее.
+
#* Добавим в <tex>T</tex> все найденные рёбра.
Пример для набора элементов 5 7 3 4 6         
+
# Получившийся граф <tex>T</tex> является минимальным остовным деревом графа <tex>G</tex>.
      5
 
      5 7
 
    3 5 7
 
  3 4 5 7
 
  3 4 5 6 7
 
Как мы видим в этом примере понадобилось сдвинуть всего 3 элемента. Что касается константы <tex>C</tex>, то <tex>C \cdot N \cdot (N/8+log_{2} N) \approx N^2/8</tex>, следовательно <tex>C=1/8</tex>.   
 
=== Метод Шелла ===
 
Метод Шелла основан на том, что сортировка вставками более эффективна на маленьких или на частичной отсортированных входных данных. Устройство метода Шелла более понятно если рассматривать его на фиксированном наборе данных. Например мы имеем набор из 16 элементов <tex>R_1...R_{16}</tex> разобьём их на пары <tex>(R_1,R_9),...,(R_8,R_{16})</tex>. Каждое разделение называется проходом. Отсортируем каждую из пар. Разобьем на группы по 4 элемента <tex>(R_1,R_5,R_9,R_{13}),...,(R_4,R_8,R_{12},R_{16})</tex>. Отсортируем каждую из пар. Разобьём на 2 группы по восемь элементов <tex>(R_1,R_3,R_5,R_7,R_9,R_{11},R_{13},R_{15}),(R_2,R_4,R_6,R_8,R_{10},R_{12},R_{14},R_{16})</tex>. Отсортируем каждую из пар. При четвёртоми последнем проходе сортируются все 16 элементов. В итоге получится отсортированный массив.
 
Последовательность смещений 1 2 4 8 может меняться в зависимости от неё меняется и асимптотика. Например предложенная Хиббардом последовательность <tex>2^i-1 \le N, i \in N </tex> приводит к алгоритму с асимптотиткой <tex> O(N^{3/2}) </tex>.
 
  
===Вставка в список ===
+
Данный алгоритм может работать неправильно, если в графе есть ребра равные по весу. Например, полный граф из трех вершин, вес каждого ребра равен один. В <tex>T</tex> могут быть добавлены все три ребра. Избежать эту проблему можно, выбирая в первом пункте среди ребер, равных по весу, ребро с наименьшим номером.
При этой сортировке мы используем односвязной список вместо упорядоченной части массива. Теперь на не потребуется времени на сдвиг, а понадобиться всего лишь изменить родстве6ые связи. Что касается константы <tex>C</tex>, то <tex>C \cdot N \cdot (N/4+2) \approx N^2/4</tex>, следовательно <tex>C=1/4</tex>.
+
 
=== Сортировка с вычислением адреса ===
+
Доказательство будем проводить, считая веса всех ребер различными.
Сортировку с вычисление адревса выгодно использовать когда ключи распределены равномерно и не скапливаются хаотично в отдельных диапазонах значений. Вместо левой отсортированной части массива мы будем использовать <tex> M </tex> односвязных списков, в каждом из которых будут храниться значения из определённого диапазона. С каждым списком работаем как при простых выставках в список. Вероятность того что элемент попадёт в какой-либо список <tex>1/M</tex>, следовательно для каждого элемента происходит примерно <tex> \frac {N} {4 \cdot M} </tex> сравнений, следовательно общее количество сравнений <tex> \frac {N^2} {4 \cdot M} </tex>, а при <tex>M</tex> порядка <tex>N</tex> асимптотическая сложность уменьшается до <tex>O(N)</tex>. Что касается константы <tex>C</tex>, то она <tex> \frac {N} {4 \cdot M} </tex>. Рассмотрим на примере.
+
 
Входные данные : 867 345 984 245 123 743 550 490 300
+
==Доказательство корректности==
Будем использовать 4 списка с соответствующими диапазонами значений : 0 - 250, 251 - 500, 501 - 750, 751- 1000.
+
{{Лемма
{|border="1"
+
|id=lemma1
|
+
|statement=Рассмотрим связный неориентированный взвешенный граф <tex> G = (V, E)  </tex> с инъективной весовой функцией <tex>w : E \to \mathbb{R}</tex> .
|3 элемента
+
Тогда после первой итерации главного цикла алгоритма Борувки получившийся подграф можно достроить до ''MST''.
|6 элементов
+
|proof=Предположим обратное: пусть любое ''MST'' графа <tex>G</tex> не содержит <tex>T</tex>. Рассмотрим какое-нибудь ''MST''. Тогда существует ребро <tex>x</tex> из <tex>T</tex> такое что <tex>x</tex> не принадлежит ''MST''. Добавив ребро <tex>x</tex> в ''MST'', получаем цикл в котором <tex>x</tex> не максимально, т.к оно было минимальным. Тогда, исходя из [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]], получаем противоречие.
|9 элементов
+
}}
|-
+
 
|0 - 250
+
 
|
+
{{Теорема
|123 245
+
|id=th1.
|123 245
+
|statement=Алгоритм Борувки строит ''MST''.
  |-
+
|proof=Очевидно, что алгоритм Борувки строит дерево.Будем доказывать что после каждой итерации главного цикла в алгоритме Борувки текущий подграф <tex>T</tex> можно достроить до ''MST''.
|251 - 500
+
 
|345
+
Докажем это по индукции.
|345
+
 
|300 345 490
+
'''База. '''  <tex>n = 1</tex>([[#lemma1|Лемма]]).
|-
+
 
  |501 - 750
+
'''Переход. '''  Пусть лес <tex>T</tex>, получившийся после <tex>n</tex> итераций алгоритма, можно достроить до ''MST''. Докажем, что после <tex>n+1</tex> итерации получившийся лес <tex>T'</tex> можно достроить до ''MST''. Предположим обратное: <tex>T'</tex> нельзя достроить до ''MST''. Тогда существует <tex>F</tex> = ''MST'' графа <tex>G</tex>, содержащее <tex>T</tex>  и не содержащее <tex>T'</tex>. Тогда рассмотрим цикл, получающийся добавлением в <tex>F</tex> какого-нибудь ребра <tex>x</tex> из <tex>T' {{---}} T</tex>. На этом цикле имеется ребро, большее по весу чем ребро <tex>x</tex>, иначе компонента для которой <tex>x</tex> является минимальным ребром ни с кем больше ни связана. Исходя из [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]], получаем противоречие.
|
+
 
|743
+
'''Получаем. '''  <tex>T'</tex> можно достроить до ''MST''. Следовательно предположение индукции верно.
|550 743
+
|-
+
}}
|751 - 1000
+
 
|867 984
+
==Реализация==
|867 984
+
У вершины есть поле comp — компонента связности, которой принадлежит эта вершина.
|867 984|
+
 
 +
{| width = 100%
 +
|-
 +
|
 +
  <font color=green>// <tex>G</tex> {{---}} исходный граф</font>
 +
  <font color=green>// <tex>w</tex> {{---}} весовая функция</font>
 +
  '''function''' <tex>\mathtt{boruvkaMST}():</tex>
 +
      '''while''' <tex>T\mathtt{.size} < n - 1</tex>                                 
 +
            '''for''' <tex>k \in </tex> Component                                // Component — множество компонент связности в <tex>T</tex>
 +
                <tex>w(\mathtt{minEdge}[k])=\infty</tex>                      // для каждой компоненты связности вес минимального ребра = <tex>\infty</tex>
 +
            <tex>\mathtt{findComp(}T\mathtt{)}</tex>                                      // разбиваем граф <tex>T</tex> на компоненты связности обычным ''dfs''-ом
 +
            '''for''' <tex>\mathtt{(u,v)} \in  E </tex>
 +
                '''if''' <tex>\mathtt{u.comp} \neq \mathtt{v.comp}</tex>
 +
                    '''if''' <tex>w(\mathtt{minEdge}[\mathtt{u.comp}]) < w(u,v)</tex>
 +
                        <tex>\mathtt{minEdge}[\mathtt{u.comp}] = (u,v)</tex>
 +
                    '''if''' <tex>w(\mathtt{minEdge}[\mathtt{v.comp}]) < w(u,v)</tex>
 +
                        <tex>\mathtt{minEdge}[\mathtt{v.comp}] = (u,v)</tex>
 +
            '''for''' <tex>k \in </tex> Component                               
 +
                <tex>T\mathtt{.addEdge}(\mathtt{minEdge}[k])</tex>                     // добавляем ребро если его не было в <tex>T</tex>
 +
      '''return''' <tex>T</tex>   
 +
|}
 +
 
 +
==Пример==
 +
{| class = "wikitable"
 +
! Изображение !! Компоненты связности !! Описание
 +
|-
 +
|[[Файл:Step_0.png|200px]]
 +
|
 +
|Начальный граф <tex>T</tex>
 +
|-
 +
|[[Файл:Step_1.png|200px]]
 +
| <center>'''a''' '''b''' '''c''' '''d''' '''e'''</center>
 +
|Распределим вершины по компонентам.
 +
|-
 +
|[[Файл:1step_2.png|200px]]
 +
| <center>'''a''' '''b'''  '''c''' '''d''' '''e'''</center>
 +
|Пометим минимальные пути между компонентами.
 +
|-
 +
|[[Файл:1step_3.png|200px]]<br/>
 +
|<center>'''bae'''      '''cd'''</center>
 +
|Объединим соединившиеся компоненты в одну и добавим минимальные рёбра к графу <tex>T</tex><br/>
 +
|-
 +
|[[Файл:1step_4.png|200px]]
 +
|<center>'''bae''' '''cd'''</center>
 +
|Пометим минимальные пути между компонентами.
 +
|-
 +
|[[Файл:1step_5.png|200px]]
 +
|<center>'''baecd'''</center>
 +
|Объединим соединившиеся компоненты в одну и добавим минимальные рёбра к графу <tex>T</tex><br/>
 +
|}
 +
 
 +
==Асимптотика==
 +
Внешний цикл повторяется <tex>\log{V}</tex> раз, так как количество компонент связности каждый раз уменьшается в двое и изначально равно количеству вершин. Что же касается внутреннего цикла, то он выполняется за <tex>E</tex>, где <tex>E</tex> {{---}} количество рёбер в исходном графе. Следовательно конечное время работы алгоритма <tex>O(E\log{V})</tex>.
 +
 
 +
==См. также==
 +
* [[Алгоритм Прима]]
 +
* [[Алгоритм Краскала]]
 +
* [[Алгоритм двух китайцев]]
 +
 
 +
== Ссылки ==
 +
* [http://rain.ifmo.ru/cat/view.php/vis/graph-spanning-trees/mst-2006 Визуализатор алгоритма]
 +
* [http://www.csee.wvu.edu/~ksmani/courses/fa01/random/lecnotes/lecture11.pdf Minimum Spanning Trees]
 +
* [[wikipedia:ru:Алгоритм Борувки|Алгоритм Борувки— Википедия]]
 +
 
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Остовные деревья ]]

Текущая версия на 18:02, 3 декабря 2014

Алгоритм Борувки (англ. Borůvka's algorithm) — алгоритм поиска минимального остовного дерева (англ. minimum spanning tree, MST) во взвешенном неориентированном связном графе. Впервые был опубликован в 1926 году Отакаром Борувкой.

Описание алгоритма[править]

  1. Построим граф [math]T[/math]. Изначально [math]T[/math] содержит все вершины из [math]G[/math] и не содержит ребер (каждая вершина в графе [math]T[/math] — отдельная компонента связности).
  2. Будем добавлять в [math]T[/math] ребра следующим образом, пока [math]T[/math] не является деревом
    • Для каждой компоненты связности находим минимальное по весу ребро, которое связывает эту компоненту с другой.
    • Добавим в [math]T[/math] все найденные рёбра.
  3. Получившийся граф [math]T[/math] является минимальным остовным деревом графа [math]G[/math].

Данный алгоритм может работать неправильно, если в графе есть ребра равные по весу. Например, полный граф из трех вершин, вес каждого ребра равен один. В [math]T[/math] могут быть добавлены все три ребра. Избежать эту проблему можно, выбирая в первом пункте среди ребер, равных по весу, ребро с наименьшим номером.

Доказательство будем проводить, считая веса всех ребер различными.

Доказательство корректности[править]

Лемма:
Рассмотрим связный неориентированный взвешенный граф [math] G = (V, E) [/math] с инъективной весовой функцией [math]w : E \to \mathbb{R}[/math] . Тогда после первой итерации главного цикла алгоритма Борувки получившийся подграф можно достроить до MST.
Доказательство:
[math]\triangleright[/math]
Предположим обратное: пусть любое MST графа [math]G[/math] не содержит [math]T[/math]. Рассмотрим какое-нибудь MST. Тогда существует ребро [math]x[/math] из [math]T[/math] такое что [math]x[/math] не принадлежит MST. Добавив ребро [math]x[/math] в MST, получаем цикл в котором [math]x[/math] не максимально, т.к оно было минимальным. Тогда, исходя из критерия Тарьяна, получаем противоречие.
[math]\triangleleft[/math]


Теорема:
Алгоритм Борувки строит MST.
Доказательство:
[math]\triangleright[/math]

Очевидно, что алгоритм Борувки строит дерево.Будем доказывать что после каждой итерации главного цикла в алгоритме Борувки текущий подграф [math]T[/math] можно достроить до MST.

Докажем это по индукции.

База. [math]n = 1[/math](Лемма).

Переход. Пусть лес [math]T[/math], получившийся после [math]n[/math] итераций алгоритма, можно достроить до MST. Докажем, что после [math]n+1[/math] итерации получившийся лес [math]T'[/math] можно достроить до MST. Предположим обратное: [math]T'[/math] нельзя достроить до MST. Тогда существует [math]F[/math] = MST графа [math]G[/math], содержащее [math]T[/math] и не содержащее [math]T'[/math]. Тогда рассмотрим цикл, получающийся добавлением в [math]F[/math] какого-нибудь ребра [math]x[/math] из [math]T' {{---}} T[/math]. На этом цикле имеется ребро, большее по весу чем ребро [math]x[/math], иначе компонента для которой [math]x[/math] является минимальным ребром ни с кем больше ни связана. Исходя из критерия Тарьяна, получаем противоречие.

Получаем. [math]T'[/math] можно достроить до MST. Следовательно предположение индукции верно.
[math]\triangleleft[/math]

Реализация[править]

У вершины есть поле comp — компонента связности, которой принадлежит эта вершина.

  // [math]G[/math] — исходный граф
  // [math]w[/math] — весовая функция
  function [math]\mathtt{boruvkaMST}():[/math]
      while [math]T\mathtt{.size} \lt  n - 1[/math]                                   
           for [math]k \in [/math] Component                                 // Component — множество компонент связности в [math]T[/math]
               [math]w(\mathtt{minEdge}[k])=\infty[/math]                      // для каждой компоненты связности вес минимального ребра = [math]\infty[/math]
           [math]\mathtt{findComp(}T\mathtt{)}[/math]                                      // разбиваем граф [math]T[/math] на компоненты связности обычным dfs-ом
           for [math]\mathtt{(u,v)} \in  E [/math]
               if [math]\mathtt{u.comp} \neq \mathtt{v.comp}[/math]
                   if [math]w(\mathtt{minEdge}[\mathtt{u.comp}]) \lt  w(u,v)[/math]
                       [math]\mathtt{minEdge}[\mathtt{u.comp}] = (u,v)[/math]
                   if [math]w(\mathtt{minEdge}[\mathtt{v.comp}]) \lt  w(u,v)[/math]
                       [math]\mathtt{minEdge}[\mathtt{v.comp}] = (u,v)[/math]
           for [math]k \in [/math] Component                                 
               [math]T\mathtt{.addEdge}(\mathtt{minEdge}[k])[/math]                     // добавляем ребро если его не было в [math]T[/math]
      return [math]T[/math]     

Пример[править]

Изображение Компоненты связности Описание
Step 0.png Начальный граф [math]T[/math]
Step 1.png
a b c d e
Распределим вершины по компонентам.
1step 2.png
a b c d e
Пометим минимальные пути между компонентами.
1step 3.png
bae cd
Объединим соединившиеся компоненты в одну и добавим минимальные рёбра к графу [math]T[/math]
1step 4.png
bae cd
Пометим минимальные пути между компонентами.
1step 5.png
baecd
Объединим соединившиеся компоненты в одну и добавим минимальные рёбра к графу [math]T[/math]

Асимптотика[править]

Внешний цикл повторяется [math]\log{V}[/math] раз, так как количество компонент связности каждый раз уменьшается в двое и изначально равно количеству вершин. Что же касается внутреннего цикла, то он выполняется за [math]E[/math], где [math]E[/math] — количество рёбер в исходном графе. Следовательно конечное время работы алгоритма [math]O(E\log{V})[/math].

См. также[править]

Ссылки[править]