Алгоритм Minimum Spanning Trees

Остовные деревья

Связующего дерева графа просто подграф, содержащий все вершины и является деревом. Граф может иметь множество связующих деревьев; например полный граф на четырех вершинах

    O --- O
    | \ / |
    | X |
    | / \ |
    O --- O

имеет шестнадцать остовных деревьев:

    O --- O O --- O --- ООО O
    | | | | | |
    | | | | | |
    | | | | | |
    оо O --- O O --- O O --- O

    O --- ооооооо
     \ / | \ / \ / \ / |
      X | XXX |
     / \ | / \ / \ / \ |
    оооо O --- ООО

    оо O --- O --- ООО O
    | \ | / | / | \
    | \ | / | / | \
    | \ | / | / | \
    оо O --- O --- ООО O

    O --- O --- OOOOO O
    | \ | / \ | / |
    | \ | / \ | / |
    | \ | / \ | / |
    оо O --- O O --- ООО

Минимум остовных деревьев

Теперь предположим, что ребра графа имеют веса или длины. Вес дерева только сумму весов его ребер. Очевидно, что различные деревья имеют разную длину. Проблема: Как найти минимальную длину связующего дерева?

Эта проблема может быть решена путем различных алгоритмов. Это является темой некоторых последних исследований. Есть несколько «лучших» алгоритмов, в зависимости от предположений:

– Рандомизированный алгоритм может решить это в линейное ожидаемое время. [Karger, Klein, and Tarjan, «A randomized linear-time algorithm to find minimum spanning trees», J. ACM, vol. 42, 1995, pp. 321-328.]

– Это может быть решено в линейном худшем случае время, если вес небольшие целые числа. [Fredman and Willard, «Trans-dichotomous algorithms for minimum spanning trees and shortest paths», 31st IEEE Symp. Foundations of Comp. Sci., 1990, pp. 719 725.]

– В противном случае, лучшим решением будет очень близка к линейной, но не точно линейной. Точная оценка является O(m log beta(m,n)), где бета-функции имеет сложное определение: самым маленький, как ( log(log(log(...log(n)...))) меньше чем m/n, в которой вложен i раз. [Gabow, Galil, Spencer, and Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica, vol. 6, 1986, pp. 109--122.].

Эти алгоритмы все довольно сложны, и, вероятно, не так уж велики на практике, если вы не смотрите на действительно огромные графики. Книга пытается держать вещи простыми, поэтому она описывает только один алгоритм, но (на мой взгляд) не делают очень хорошую работу по нему. Я пройду три простых классических алгоритма (не тратя времени на каждый).

Почему минимального охватывающего дерева?

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

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

Обратите внимание, что если у вас есть пути посещение всех точек ровно один раз, это особый вид дерева. Например, в приведенном выше примере, двенадцать из шестнадцати остовных деревьев на самом деле путей. Если у вас есть пути посетив несколько вершин более чем один раз, вы всегда можете отказаться от ряда краев, чтобы получить дерево. Таким образом, в общем весе MST меньше, чем вес TSP, так как это минимизация в строго больший набор.

С другой стороны, если вы рисуете трассировку пути вокруг минимального охватывающего дерева, вы пройдете каждое ребро дважды и посетить все точки, так что вес TSP меньше удвоенного веса MST. Поэтому этот тур в два раза оптимальней. Существует более сложным образом (Христофидес эвристические) использования минимальных остовных деревьев найти тур в 1,5 раза оптимального.

Как найти минимум охватывающего дерева?

Метод, чтобы получить список всех остовных деревьев, и найти минимум в списке. Мы уже знаем, как найти минимум. Но слишком много деревьев, чтобы это было эффективно. Это даже не алгоритм, поскольку вы все равно должны знать, как для получить список всех деревьев.

Лучшая идея заключается, чтобы найти некоторые ключевые свойства MST, которые позволяет нам быть уверенными, что некоторые края является его частью, и использовать это свойство для создания MST одного края в то время.

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

Лемма: Пусть X любое подмножество вершин G, и пусть ребро е наименьшее ребро, соединяющее в X GX. Тогда е является частью минимального остова.

Доказательство: Предположим, у вас есть дерево T не содержащие е, а потом я хочу показать, что T не MST. Пусть e=(u,v), с u в X и v не в X. Тогда, потому что T является связующего дерева он содержит уникальный путь от u и к v, которые вместе с e образует цикл в G. Этот путь должен включать в себя другой края f включений X G-X. T+e-f другое связующееего дерево (он имеет такое же число ребер, и остается связан, так как вы можете заменить любой путь, содержащий f одним, собираясь пойти другим путем по циклу). Это имеет меньший вес, чем t так как е имеет меньший вес, чем t. Так T не было минимальным, что и требовалось доказать.

Алгоритм Крускала

Мы начнем с алгоритма Крускала, который является простой для понимания и, вероятно, одним из лучших вариантов решения проблем вручную.

    Kruskal's algorithm:
    sort the edges of G in increasing order by length
    keep a subgraph S of G, initially empty
    for each edge e in sorted order
        if the endpoints of e are disconnected in S
        add e to S
    return S

Обратите внимание, что, когда вы добавите ребро (u, v), это всегда наименьшая соединяющая часть S, добраться от u к остальным G, так чтобы по лемме это было частью MST.

Этот алгоритм известен как «жадный алгоритм», потому что он выбирает на каждом шагу самые дешевые края добавление S. Вы должны быть очень осторожны при попытке использовать «жадных алгоритмов» для решения других проблем, так как он обычно не работает. Например, если вы хотите, найти кратчайший путь от a до b, это может быть плохой идеей, чтобы продолжать принимать кратчайшие края. Эта идея работает только в алгоритме Крускала из-за ключевого свойства, которое мы доказали.

Анализ: линии проверки равенства двух концах отключены, это должно быть медленно (линейное время на одну итерацию, или O(mn) общего числа). Но на самом деле есть некоторые сложные структуры данных, которые позволяют нам выполнять каждое испытание в близких ко времени; это известно как union-find проблема. Медленная часть оказывается сортировочным шагом, который занимает O(m log n)) времени.

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

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

    Prim's algorithm:
    let T be a single vertex x
    while (T has fewer than n vertices)
    {
        find the smallest edge connecting T to G-T
        add it to T
    }

Так как каждое добавленное ребро является самым маленьким подключением T к G-T, доказаная Лемма показывает, что мы только добавляем края, которые должны быть частью MST.

Опять же, это выглядит как петля имеет медленный шаг. Но опять же, некоторые структуры данных могут быть использованы для ускорения этого процесса. Идея заключается в использовании кучи запоминаня, для каждой вершины, наименьший край соединительного T с этой вершины.

    Prim with heaps:
    make a heap of values (vertex,edge,weight(edge))
        initially (v,-,infinity) for each vertex
        let tree T be empty
    while (T has fewer than n vertices)
    {
        let (v,e,weight(e)) have the smallest weight in the heap
        remove (v,e,weight(e)) from the heap
        add v and e to T
        for each edge f=(u,v)
        if u is not already in T
            find value (u,g,weight(g)) in heap
            if weight(f) < weight(g)
            replace (u,g,weight(g)) with (u,f,weight(f))
    }

Анализ: Мы выполняем n шагов, в которых удаляем наименьший элемент и заносим в динамическую память, и не более 2m шагов, в котором мы рассмотрим края f = (u, v). Для каждого из этих шагов, мы могли бы заменить значения в памяти, снижение его веса. (Вы также должны определить верное значение в динамической памяти, но это может быть сделано достаточно легко сохраняя указатель от вершин к соответствующим значениям). Не описано, как снизить вес элементов двоичной памяти, но это легко сделать в O(log n) времени. Попеременно с использованием более сложной структуры данных, известной как числа Фибоначчи, вы можете уменьшить вес элемента за постоянное время. В результате общее время граница O(m + n log n).

Борувка Алгоритм

На самом деле Борувка должно быть прописано с небольшим ударением на «u». Хотя это кажется немного сложно объяснить, это, вероятно, самый простой для компьютерной реализации, поскольку она не требует каких-либо сложных структур данных. Идея заключается в том, чтобы сделать шаги, как алгоритм Прима, параллельно всему график одновременно.

     Boruvka's algorithm:
    make a list L of n trees, each a single vertex
    while (L has more than one tree)
        for each T in L, find the smallest edge connecting T to G-T
        add all those edges to the MST
        (causing pairs of trees in L to merge)

Как мы видели в алгоритме Прима, каждый край добавления должны быть частью MST, поэтому он должен быть в порядке, чтобы добавить их все за один раз.

Анализ: Это похоже на сортировку слиянием. Каждый проход уменьшает количество деревьев в два раза, так что есть O(log n) прохождений. Каждый проход занимает время O(m), (сначала выяснить, какя вершина в каком дереве, затем для каждого ребра проверить, является ли оно соединением двух деревьев, и лучшее чем те, что видели за деревьями по обе конечной точки), так что общая сумма O(m log n).

Гибридный алгоритм

В действительности это не отдельный алгоритм, но вы можете объединить два классических алгоритма и сделать лучше, чем в одиночку. Идея состоит в том, чтобы сделать O(log log n) проходов алгоритмом Борувка, затем переключиться на алгоритм Прима. Алгоритм Прима строит одно большое дерево, подключив его с небольшими деревьями в списке L к построенному алгоритмом Борувка, сохраняя память, которая хранит для каждого дерева L, лучший край, который может быть использован для подключения к большому дереву. Кроме того, вы можете думать о разрушающихся деревьях найденных алгоритмом Борувка в нечто вроде «супер вершин» и применить алгоритм Прима на результатах меньшего графа. Дело в том, что это уменьшает количество операций удаления min в памяти используя алгоритм Прима, равным числу деревьев осталось L после алгоритм Борувка, которая является O(n/log n).

Анализ: O(mloglogn) для первой части, O(m + (n/log n) log n) = O(m + n) для второй, так что O(mloglogn) общая.