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

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показаны 4 промежуточные версии 2 участников)
Строка 1: Строка 1:
== Сортировка PSRS ==
+
<b>Алгоритм Борувки</b> (англ. ''Borůvka's algorithm'') — алгоритм поиска минимального остовного дерева (англ. ''minimum spanning tree, MST'') во взвешенном неориентированном связном графе.
=== Описание ===
+
Впервые был опубликован в 1926 году Отакаром Борувкой.
Parallel Sorting by Regular Sampling {{---}} параллельная сортировка, разработанная Ханмао Ши, Рисажем Канселом и Джонатаном Шеффером в 1992 году. Имеет два преимущества по сравнению с быстрой сортировкой:
 
* сохраняет размер списка более сбалансированным на протяжении всего процесса
 
* избегает повторных перестановок ключей
 
  
=== Алгоритм ===
+
==Описание алгоритма==
На вход подаётся <tex>n</tex> элементов. Для начала надо разделить входные данные на <tex>p</tex> равных частей, где <tex>p</tex> {{---}} количество процессоров. Далее запустить алгоритм быстрой сортировки на каждом из процессоров. Далее  мы должны сформировать массив элементами которого будут элементы из каждого процессора с индексами <tex dpi=145>0,\frac {n}  {p^2}, \frac {2n}{p^2},...,\frac {(p-1)n}{p^2}</tex>. Теперь нам потребуется отсортировать полученный массив и выбрать из него p разделителей с индексами <tex dpi=145>   p + [\frac {p} {2}] - 1, 2p + [\frac {p}{2}] - 1,...,(p-1)p + [\frac {p}{2}] - 1</tex>. После чего разделим данные в процессорах согласно полученному массиву разделителей. Пусть <tex>a_1, a_2,..., a_j</tex> {{---}} разделители. Разделение происходит следующим образом, данные в каждом процессоре разобьём на группы элементов, попадающие в соответствующие полуинтервалы <tex>(-\infty,a_1],(a_1,a_2],...,(a_j,+\infty)</tex>. Далее сольём соответствующие группы, которые отсортированы по в возрастанию, в массивы. Слияние будем производить поочерёдно, то есть сначала сольём первую группу со второй потом результат с третей и так далее. В итоге получим отсортированный набор данных.
+
# Построим граф <tex>T</tex>. Изначально <tex>T</tex> содержит все вершины из <tex>G</tex> и не содержит ребер (каждая вершина в графе <tex>T</tex> {{---}} отдельная компонента связности).
 +
# Будем добавлять в <tex>T</tex> ребра следующим образом, пока <tex>T</tex> не является деревом
 +
#* Для каждой компоненты связности находим минимальное по весу ребро, которое связывает эту компоненту с другой.
 +
#* Добавим в <tex>T</tex> все найденные рёбра.
 +
# Получившийся граф <tex>T</tex> является минимальным остовным деревом графа <tex>G</tex>.
  
=== Пример ===
+
Данный алгоритм может работать неправильно, если в графе есть ребра равные по весу. Например, полный граф из трех вершин, вес каждого ребра равен один. В <tex>T</tex> могут быть добавлены все три ребра. Избежать эту проблему можно, выбирая в первом пункте среди ребер, равных по весу, ребро с наименьшим номером.
Количество элементов <tex>27</tex>, количество процессоров <tex>3</tex>.
 
Исходный набор данных:
 
  
<tex>[15, 46, 48, 93, 39, 6, 72, 91, 14, 36, 69, 40, 89, 61, 97, 12, 21, 54, 53, 97, 84, 58, 32, 27, 33, 72, 20]</tex>:
+
Доказательство будем проводить, считая веса всех ребер различными.
{| style="background-color:#CCC;margin:0.5px"
+
 
!style="background-color:#EEE"| Описание этапа
+
==Доказательство корректности==
!style="background-color:#EEE"| 1 процессор
+
{{Лемма
!style="background-color:#EEE"| 2 процессор
+
|id=lemma1
!style="background-color:#EEE"| 3 процессор
+
|statement=Рассмотрим связный неориентированный взвешенный граф <tex> G = (V, E)  </tex> с инъективной весовой функцией <tex>w : E \to \mathbb{R}</tex> .
 +
Тогда после первой итерации главного цикла алгоритма Борувки получившийся подграф можно достроить до ''MST''.
 +
|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> не максимально, т.к оно было минимальным. Тогда, исходя из [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]], получаем противоречие.
 +
}}
 +
 
 +
 
 +
{{Теорема
 +
|id=th1.
 +
|statement=Алгоритм Борувки строит ''MST''.
 +
|proof=Очевидно, что алгоритм Борувки строит дерево.Будем доказывать что после каждой итерации главного цикла в алгоритме Борувки текущий подграф <tex>T</tex> можно достроить до ''MST''.
 +
 
 +
Докажем это по индукции.
 +
 
 +
'''База. '''  <tex>n = 1</tex>([[#lemma1|Лемма]]).
 +
 
 +
'''Переход. '''  Пусть лес <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> является минимальным ребром ни с кем больше ни связана. Исходя из  [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]], получаем противоречие.
 +
 
 +
'''Получаем. '''  <tex>T'</tex> можно достроить до ''MST''. Следовательно предположение индукции верно.
 +
 +
}}
 +
 
 +
==Реализация==
 +
У вершины есть поле comp — компонента связности, которой принадлежит эта вершина.
 +
 
 +
{| width = 100%
 
|-
 
|-
|style="background-color:#FFF;padding:2px 10px"| Разделение между процессорами
+
|  
|style="background-color:#FFF;padding:2px 10px"| 15 46 48 93 39 6 72 91 14
+
  <font color=green>// <tex>G</tex> {{---}} исходный граф</font>
|style="background-color:#FFF;padding:2px 10px"| 36 69 40 89 61 97 12 21 54
+
  <font color=green>// <tex>w</tex> {{---}} весовая функция</font>
|style="background-color:#FFF;padding:2px 10px"| 53 97 84 58 32 27 33 72 20
+
  '''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"
 +
! Изображение !! Компоненты связности !! Описание
 
|-
 
|-
|style="background-color:#FFF;padding:2px 10px"| После сортировки частей
+
|[[Файл:Step_0.png|200px]]
|style="background-color:#FFF;padding:2px 10px"| 6 14 15 39 46 48 72 91 93
+
|
|style="background-color:#FFF;padding:2px 10px"| 12 21 36 40 54 61 69 89 97
+
|Начальный граф <tex>T</tex>
|style="background-color:#FFF;padding:2px 10px"| 20 27 32 33 53 58 72 84 97
 
 
|-
 
|-
|style="background-color:#FFF;padding:2px 10px"| Выбор элементов
+
|[[Файл:Step_1.png|200px]]
|style="background-color:#FFF;padding:2px 10px"| '''6''' 14 15 '''39''' 46 48 '''72''' 91 93 
+
| <center>'''a''' '''b''' '''c''' '''d''' '''e'''</center>
|style="background-color:#FFF;padding:2px 10px"| '''12''' 21 36 '''40''' 54 61 '''69''' 89 97
+
|Распределим вершины по компонентам.
|style="background-color:#FFF;padding:2px 10px"| '''20''' 27 32 '''33''' 53 58 '''72''' 84 97
 
|}
 
 
 
 
 
{| style="background-color:#CCC;margin:0.5px"
 
!style="background-color:#EEE"| Описание этапа
 
!style="background-color:#EEE"| Данные
 
 
|-
 
|-
|style="background-color:#FFF;padding:2px 10px"| Выбранные элементы
+
|[[Файл:1step_2.png|200px]]
|style="background-color:#FFF;padding:2px 10px"| 6 39 72 12 40 69 20 33 72
+
| <center>'''a''' '''b'''  '''c'''  '''d''' '''e'''</center>
 +
|Пометим минимальные пути между компонентами.
 
|-
 
|-
|style="background-color:#FFF;padding:2px 10px"| После сортировки
+
|[[Файл:1step_3.png|200px]]<br/>
|style="background-color:#FFF;padding:2px 10px"| 6 12 20 33 39 40 69 72 72
+
|<center>'''bae'''      '''cd'''</center>
 +
|Объединим соединившиеся компоненты в одну и добавим минимальные рёбра к графу <tex>T</tex><br/>
 
|-
 
|-
|style="background-color:#FFF;padding:2px 10px"| Выбор элементов
+
|[[Файл:1step_4.png|200px]]
|style="background-color:#FFF;padding:2px 10px"| 6 12 20 '''33''' 39 40 '''69''' 72 72
+
|<center>'''bae''' '''cd'''</center>
 +
|Пометим минимальные пути между компонентами.
 
|-
 
|-
|style="background-color:#FFF;padding:2px 10px"| Разделители
+
|[[Файл:1step_5.png|200px]]
|style="background-color:#FFF;padding:2px 10px"| 33 69
+
|<center>'''baecd'''</center>
 +
|Объединим соединившиеся компоненты в одну и добавим минимальные рёбра к графу <tex>T</tex><br/>
 
|}
 
|}
  
 +
==Асимптотика==
 +
Внешний цикл повторяется <tex>\log{V}</tex> раз, так как количество компонент связности каждый раз уменьшается в двое и изначально равно количеству вершин. Что же касается внутреннего цикла, то он выполняется за <tex>E</tex>, где <tex>E</tex> {{---}} количество рёбер в исходном графе. Следовательно конечное время работы алгоритма <tex>O(E\log{V})</tex>.
  
{| style="background-color:#CCC;margin:0.5px"
+
==См. также==
!style="background-color:#EEE"| Описание этапа
+
* [[Алгоритм Прима]]
!style="background-color:#EEE"|           
+
* [[Алгоритм Краскала]]
!style="background-color:#EEE"| 1 процессор
+
* [[Алгоритм двух китайцев]]
!style="background-color:#EEE"|           
+
 
!style="background-color:#EEE"|           
+
== Ссылки ==
!style="background-color:#EEE"| 2 процессор
+
* [http://rain.ifmo.ru/cat/view.php/vis/graph-spanning-trees/mst-2006 Визуализатор алгоритма]
!style="background-color:#EEE"|           
+
* [http://www.csee.wvu.edu/~ksmani/courses/fa01/random/lecnotes/lecture11.pdf Minimum Spanning Trees]
!style="background-color:#EEE"|           
+
* [[wikipedia:ru:Алгоритм Борувки|Алгоритм Борувки— Википедия]]
!style="background-color:#EEE"| 3 процессор
 
!style="background-color:#EEE"|           
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| После сортировки частей
 
|style="background-color:#FFF;padding:2px 10px"| 6 14 15
 
|style="background-color:#FFF;padding:2px 10px"| 39 46 48
 
|style="background-color:#FFF;padding:2px 10px"| 72 91 93
 
|style="background-color:#FFF;padding:2px 10px"| 12 21
 
|style="background-color:#FFF;padding:2px 10px"| 36 40 54 61 69
 
|style="background-color:#FFF;padding:2px 10px"| 89 97
 
|style="background-color:#FFF;padding:2px 10px"| 20 27 32 33
 
|style="background-color:#FFF;padding:2px 10px"| 53 58
 
|style="background-color:#FFF;padding:2px 10px"| 72 84 97
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| После обмена данными
 
|style="background-color:#FFF;padding:2px 10px"| 6 14 15
 
|style="background-color:#FFF;padding:2px 10px"| 12 21
 
|style="background-color:#FFF;padding:2px 10px"| 20 27 32 33
 
|style="background-color:#FFF;padding:2px 10px"| 39 46 48
 
|style="background-color:#FFF;padding:2px 10px"| 36 40 54 61 69
 
|style="background-color:#FFF;padding:2px 10px"| 53 58
 
|style="background-color:#FFF;padding:2px 10px"| 72 91 93
 
|style="background-color:#FFF;padding:2px 10px"| 89 97
 
|style="background-color:#FFF;padding:2px 10px"| 72 84 97
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| После слития
 
|style="background-color:#FFF;padding:2px 10px"| 6 12 14 
 
|style="background-color:#FFF;padding:2px 10px"| 15 20 21
 
|style="background-color:#FFF;padding:2px 10px"| 27 32 33
 
|style="background-color:#FFF;padding:2px 10px"| 36 39 40 
 
|style="background-color:#FFF;padding:2px 10px"| 46 48 53
 
|style="background-color:#FFF;padding:2px 10px"| 54 58 61 69
 
|style="background-color:#FFF;padding:2px 10px"| 72 72 
 
|style="background-color:#FFF;padding:2px 10px"| 84 89 91
 
|style="background-color:#FFF;padding:2px 10px"| 93 97 97
 
|}
 
  
=== Анализ ===
+
[[Категория: Алгоритмы и структуры данных]]
При <tex>n</tex> элементах и <tex>p</tex> процессорах начальная сортировка выполнится за <tex dpi=145>O( \frac {n\log(n/p)}{p})</tex>. Выбор порядка <tex>p</tex> элементов в каждом процессоре произойдёт за <tex>O(p)</tex>,их сортировать мы будем с помощью быстрой сортировки, а так же учитывая что их количество порядка <tex>p</tex>, то можно сказать, что они сортируются за <tex>O(p^2\log(p^2))=O(p^2\log(p))</tex>. После обмена данными будет произведено слияние <tex>p</tex> массивов в каждом процессоре, учитывая что при равномерном распределении данных длина сливаемых массивов будет <tex dpi=145>\frac {n}{p^2}</tex>, а <tex>\mathrm {merge} </tex> двух массивов выполняется за сумму их длин, это займёт <tex>\displaystyle O(\sum \limits_{k=2}^{p} \frac {k \cdot n}{p^2})=O(\frac {n \cdot p \cdot (p+1)}{2p^2}-\frac {n}{p^2})=O(n)</tex>. В итоге мы получим <tex dpi=145> O(\frac {n\log(n/p)}{p})+O(p^2\log(p))+O(n)+O(p)</tex><tex dpi=145> =O(\frac {n\log(n/p)}{p}+p^2\log(p)+\frac {n}{p\log p}+p)=O(\frac {n\log(n/p)}{p})</tex>.
+
[[Категория: Остовные деревья ]]
=== См. также ===
 
* [[Многопоточная сортировка слиянием|Многопоточная сортировка слиянием]]
 

Текущая версия на 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].

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

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