Python алгоритмы: Алгоритм Прима

Предлагаю чуточку отвлечься от 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)$ (мы, конечно, здесь не учитываем возможность использования сложных структур данных для достижения ещё меньших асимптотик).
Если взглянуть на алгоритмы Прима и Дейкстры более формально, то получается, что они вообще идентичны друг другу, за исключением весовой функции вершин: если в алгоритме Дейкстры у каждой вершины поддерживается длина кратчайшего пути (т.е. сумма весов некоторых рёбер), то в алгоритме Прима каждой вершине приписывается только вес минимального ребра, ведущего в множество уже взятых вершин.

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

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

Используемая литература:

Python алгоритмы

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

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

Описание

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

Реализации

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

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

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

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

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

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

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

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

Описание

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

Реализации

Тривиальная реализация: алгоритмы за и

Случай плотных графов: алгоритм за

Случай разреженных графов: алгоритм за

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

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

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

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

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

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

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