Дай 10 !)

воскресенье, 19 июня 2011 г.

Алгоритм Прима

Предлагаю чуточку отвлечься от Sython'a (я так называю реализацию SICP на Python))))
Итак рассмотрим один из простых но очень классических алгоритмов - алгоритм Прима поиска минимальных остовного дерева.
Советую так же ознакомиться со статьей Теория графов и деревьев для Python

Описание

Дан взвешенный неориентированный граф G с n вершинами и m рёбрами. Требуется найти такое поддерево этого графа, которое бы соединяло все его вершины, и при этом обладало наименьшим возможным весом (т.е. суммой весов рёбер). Поддерево — это набор рёбер, соединяющих все вершины, причём из любой вершины можно добраться до любой другой ровно одним простым путём.
*-Нравится статья? Кликни по рекламе! :)

Сам алгоритм имеет очень простой вид. Искомый минимальный остов строится постепенно, добавлением в него рёбер по одному. Изначально остов полагается состоящим из единственной вершины (её можно выбрать произвольно). Затем выбирается ребро минимального веса, исходящее из этой вершины, и добавляется в минимальный остов. После этого остов содержит уже две вершины, и теперь ищется и добавляется ребро минимального веса, имеющее один конец в одной из двух выбранных вершин, а другой — наоборот, во всех остальных, кроме этих двух. И так далее, т.е. всякий раз ищется минимальное по весу ребро, один конец которого — уже взятая в остов вершина, а другой конец — ещё не взятая, и это ребро добавляется в остов (если таких рёбер несколько, можно взять любое). Этот процесс повторяется до тех пор, пока остов не станет содержать все вершины (или, что то же самое, n-1 ребро).
В итоге будет построен остов, являющийся минимальным. Если граф был изначально не связен, то остов найден не будет (количество выбранных рёбер останется меньше n-1).

Доказательство

Пусть граф G был связным, т.е. ответ существует. Обозначим через T остов, найденный алгоритмом Прима, а через S — минимальный остов. Очевидно, что T действительно является остовом (т.е. поддеревом графа G). Покажем, что веса S и T совпадают.
Рассмотрим первый момент времени, когда в T происходило добавление ребра, не входящего в оптимальный остов S. Обозначим это ребро через e, концы его — через a и b, а множество входящих на тот момент в остов вершин — через V (согласно алгоритму, a \in V, b \not\in V, либо наоборот). В оптимальном остове S вершины a и b соединяются каким-то путём P; найдём в этом пути любое ребро g, один конец которого лежит в V, а другой — нет. Поскольку алгоритм Прима выбрал ребро e вместо ребра g, то это значит, что вес ребра g больше либо равен весу ребра e.
Удалим теперь из S ребро g, и добавим ребро e. По только что сказанному, вес остова в результате не мог увеличиться (уменьшиться он тоже не мог, поскольку S было оптимальным). Кроме того, S не перестало быть остовом (в том, что связность не нарушилась, нетрудно убедиться: мы замкнули путь P в цикл, и потом удалили из этого цикла одно ребро).
Итак, мы показали, что можно выбрать оптимальный остов S таким образом, что он будет включать ребро e. Повторяя эту процедуру необходимое число раз, мы получаем, что можно выбрать оптимальный остов S так, чтобы он совпадал с T. Следовательно, вес построенного алгоритмом Прима T минимален, что и требовалось доказать.

Реализации

Время работы алгоритма существенно зависит от того, каким образом мы производим поиск очередного минимального ребра среди подходящих рёбер. Здесь могут быть разные подходы, приводящие к разным асимптотикам и разным реализациям.

Тривиальная реализация: алгоритмы за O(n m) и O(n^2 + m \log n)

Если искать каждый раз ребро простым просмотром среди всех возможных вариантов, то асимптотически будет требоваться просмотр O(m) рёбер, чтобы найти среди всех допустимых ребро с наименьшим весом. Суммарная асимптотика алгоритма составит в таком случае O(nm), что в худшем случае есть O(n^3), — слишком медленный алгоритм.
Этот алгоритм можно улучшить, если просматривать каждый раз не все рёбра, а только по одному ребру из каждой уже выбранной вершины. Для этого, например, можно отсортировать рёбра из каждой вершины в порядке возрастания весов, и хранить указатель на первое допустимое ребро (напомним, допустимы только те рёбра, которые ведут в множество ещё не выбранных вершин). Тогда, если пересчитывать эти указатели при каждом добавлении ребра в остов, суммарная асимптотика алгоритма будет O(n^2 + m), но предварительно потребуется выполнить сортировку всех рёбер за O(m \log n), что в худшем случае (для плотных графов) даёт асимптотику O(n^2 \log n).
Ниже мы рассмотрим два немного других алгоритма: для плотных и для разреженных графов, получив в итоге заметно лучшую асимптотику.

Случай плотных графов: алгоритм за O(n^2)

Подойдём к вопросу поиска наименьшего ребра с другой стороны: для каждой ещё не выбранной будем хранить минимальное ребро, ведущее в уже выбранную вершину.
Тогда, чтобы на текущем шаге произвести выбор минимального ребра, надо просто просмотреть эти минимальные рёбра у каждой не выбранной ещё вершины — асимптотика составит O(n).
Но теперь при добавлении в остов очередного ребра и вершины эти указатели надо пересчитывать. Заметим, что эти указатели могут только уменьшаться, т.е. у каждой не просмотренной ещё вершины надо либо оставить её указатель без изменения, либо присвоить ему вес ребра в только что добавленную вершину. Следовательно, эту фазу можно сделать также за O(n).
Таким образом, мы получили вариант алгоритма Прима с асимптотикой O(n^2).
В частности, такая реализация особенно удобна для решения так называемой евклидовой задачи о минимальном остове: когда даны n точек на плоскости, расстояние между которыми измеряется по стандартной евклидовой метрике, и требуется найти остов минимального веса, соединяющий их все (причём добавлять новые вершины где-либо в других местах запрещается). Эта задача решается описанным здесь алгоритмом за O(n^2) времени и O(n) памяти, чего не получится добиться алгоритмом Крускала.

Случай разреженных графов: алгоритм за O(m \log n)

В описанном выше алгоритме можно увидеть стандартные операции нахождения минимума в множестве и изменение значений в этом множестве. Эти две операции являются классическими, и выполняются многими структурами данных, например, реализованным в языке C++ красно-чёрным деревом set.
По смыслу алгоритм остаётся точно таким же, однако теперь мы можем найти минимальное ребро за время O(\log n). С другой стороны, время на пересчёт n указателей теперь составит O(n \log n), что хуже, чем в вышеописанном алгоритме.
Если учесть, что всего будет O(m) пересчётов указателей и O(n) поисков минимального ребра, то суммарная асимптотика составит O(m \log n) — для разреженных графов это лучше, чем оба вышеописанных алгоритма, но на плотных графах этот алгоритм будет медленнее предыдущего.

Реализация на Python(за O(n^2 \log n))

На сайте Традиция представлен данный алгоритм на Python, но мне кажется, что это выдранный кусочек кода, т.к. совсем не понятно какого класса объект G подается на вход функции, поэтому относитесь к нему как к псевдокоду))) Но там так же представлена иллюстрация к алгоритму, наш пример мы построим именно на том графе.
Для представления воспользуемся так называемой смежной весовой матрицей. Которая симметрична относительно своей главной, нулевой(т.е. она заполнена 0) диагонали. Примем, что -1 означает отсутствие маршрута между городами, как между Минском и NY))

   
                        mnsk NY mos   ber  kiv
              mnsk           0      -1     15      20   15
                 NY          -1      0      60       50   80
               mos          15      60      0       50   10
                 ber          20     50     50      0     30 

             kiv       15     80      10     30    0

Воспользуемся стандартным способом представлять матрицу посредством списка списков:

matr = [
         [0, -1, 15, 20, 15], 
         [-1, 0, 60, 50, 80], 
         [15, 60, 0, 50, 10], 
         [20, 50, 50, 0, 30], 
         [15, 80, 10, 30, 0]
       ]

Вот наши функции:
def search_min(tr, vizited):#1 место для оптимизации
    min=max(tr)
    for ind in vizited:
        for index, elem in enumerate(tr[ind]):
            if elem>0 and elem<min and index not in vizited:
                min=elem#веса путей
                index2=index# индекс города
    return [min, index2]

def prim(matr):
    toVisit=[i for i in range(1,len(matr))]# города кроме начального(0)
    vizited=[0]
    result=[0]# начнем с минска
    for index in toVisit:
        weight, ind=search_min(matr, vizited)
        result.append(weight)#в результат будут заноситься веса
        vizited.append(ind)# содержит карту пути
    return result


Аналогия с алгоритмом Дейкстры

Прослеживается вполне чёткая аналогия с алгоритмом Дейкстры: он имеет такую же структуру (n-1 фаза, на каждой из которых сначала выбирается оптимальное ребро, добавляется в ответ, а затем пересчитываются значения для всех не выбранных ещё вершин). Более того, алгоритм Дейкстры тоже имеет два варианта реализации: за O(n^2) и O(m \log n) (мы, конечно, здесь не учитываем возможность использования сложных структур данных для достижения ещё меньших асимптотик).
Если взглянуть на алгоритмы Прима и Дейкстры более формально, то получается, что они вообще идентичны друг другу, за исключением весовой функции вершин: если в алгоритме Дейкстры у каждой вершины поддерживается длина кратчайшего пути (т.е. сумма весов некоторых рёбер), то в алгоритме Прима каждой вершине приписывается только вес минимального ребра, ведущего в множество уже взятых вершин.

Свойства минимальных остовов

  • Максимальный остов также можно искать алгоритмом Прима (например, заменив все веса рёбер на противоположные: алгоритм не требует неотрицательности весов рёбер).
  • Минимальный остов единственен, если веса всех рёбер различны. В противном случае, может существовать несколько минимальных остовов (какой именно будет выбран алгоритмом Прима, зависит от порядка просмотра рёбер/вершин с одинаковыми весами/указателями)
  • Минимальный остов также является остовом, минимальным по произведению всех рёбер (предполагается, что все веса положительны). В самом деле, если мы заменим веса всех рёбер на их логарифмы, то легко заметить, что в работе алгоритма ничего не изменится, и будут найдены те же самые рёбра.
  • Минимальный остов является остовом с минимальным весом самого тяжёлого ребра. Яснее всего это утверждение понятно, если рассмотреть работу алгоритма Крускала.
  • Критерий минимальности остова: остов является минимальным тогда и только тогда, когда для любого ребра, не принадлежащего остову, цикл, образуемый этим ребром при добавлении к остову, не содержит рёбер тяжелее этого ребра. В самом деле, если для какого-то ребра оказалось, что оно легче некоторых рёбер образуемого цикла, то можно получить остов с меньшим весом (добавив это ребро в остов, и удалив самое тяжелое ребро из цикла). Если же это условие не выполнилось ни для одного ребра, то все эти рёбра не улучшают вес остова при их добавлении.
Используемая литература:
  1. Википедия
  2. Традиция
  3. MAXimal

6 комментариев:

  1. Отличный пост!

    ОтветитьУдалить
  2. Спасибо большое, очень полезно

    ОтветитьУдалить
  3. Ответы
    1. Не обзывайся, я поддерживаю данный сайт, ибо он хороший и помогает людям работать с графами

      Удалить
  4. Капец что тут у вас творится
    P.s. Код говно

    ОтветитьУдалить