35. “Жадные алгоритмы”. Алгоритм Крускала нахождения остовного дерева наименьшей стоимости, как пример “жадного алгоритма”. Временная сложность алгоритма

 

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

Если глобальная оптимальность алгоритма имеет место практически всегда, его обычно предпочитают другим методам оптимизации, таким как динамическое программирование.

Алгоритм Хаффмана (адаптивный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью).

Алгоритм Крускала (поиск остовного леса минимального веса в графе).

Алгоритм Прима (поиск остовного дерева минимального веса в связном графе).

Задачи, в которых жадные алгоритмы не дают оптимального решения

Для ряда задач, относящихся к классу NP, жадные алгоритмы не дают оптимального решения. К ним относятся:

Тем не менее, в ряде задач жадные алгоритмы дают неплохие приближённые решения.

 

Алгоритм Краскала — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые описан Джозефом Крускалом в 1956 году.

Формулировка

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

Оценка

До начала работы алгоритма необходимо отсортировать рёбра по весу, это требует O(E * log(E)) времени. После чего компоненты связности удобно хранить в виде системы непересекающихся множеств. Все операции в таком случае займут O(E * α(E, V)), где α — функция, обратная к функции Аккермана. Поскольку для любых практических задач α(E, V) < 5, то можно принять её за константу, таким образом общее время работы алгоритма Крускала можно принять за O(E).

 

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

Предположим, что есть связный граф G = (V, Е) с множеством вершин V = (1, 2, ..., п} и функцией стоимости с, определенной на множестве ребер E. В ал­горитме Крускала (Kruskal) построение остовного дерева минимальной стоимости для графа G начинается с графа Т = (V, ), состоящего только из п вершин графа G и не имеющего ребер. Таким образом, каждая вершина является связной (с самой собой) компонентой. В процессе выполнения алгоритма мы имеем набор связных компонент, постепенно объединяя которые формируем остовное дерево.

При построении связных, постепенно возрастающих компонент поочередно прове­ряются ребра из множества Е в порядке возрастания их стоимости. Если очередное ребро связывает две вершины из разных компонент, тогда оно добавляется в граф Т. Если это ребро связывает две вершины из одной компоненты, то оно отбрасывается, так как его добавление в связную компоненту, являющуюся свободным деревом, приведет к образованию цикла. Когда все вершины графа G будут принадлежать одной компоненте, построение остовного дерева минимальной стоимости Т для этого графа заканчивается.

Пример 7.6. Рассмотрим помеченный граф, представленный на рис. 7.4,а. После­довательность добавления ребер в формирующееся дерево Т показана на рис. 7.7. Ребра стоимостью 1, 2, 3 и 4 рассмотрены первыми и все включены в Т, поскольку их добавление не приводит к циклам. Ребра (1,4) и (3, 4) стоимостью 5 нельзя включить в Т, так как они соединяют вершины одной и той же компоненты (рис, 7.7,г) и поэтому замыкают цикл. Но оставшееся ребро (2, 3) также стоимостью 5 но создает цикл. После включения этого ребра в Т формирование остовного дерева завершается.

Рис. 7.7. Последовательное формирование остовного дерева минимальной стоимости посредством алгоритма Крускала

 Этот алгоритм можно реализовать, основываясь на множествах (для вершин и ребер) и операторах. Прежде всего, необходимо множество ребер E, к которому можно было бы последовательно применять оператор DELETEMIN для отбора ребер в порядке возрастания их стоимости. Поэтому множество ребер целесообразно представить в виде очереди с приоритетами и использовать для нее частично упорядоченное дерево в качестве структуры данных.

Необходимо также поддерживать набор С связных компонент, для чего можно использовать следующие операторы.

1. Оператор MERGE(A, В, С) объединяет компоненты А и В из набора С и результат

объединения помещает или в А, иди в В,

2. Функция FIND(v, С) возвращает имя той компоненты из набора С, которая со

держит вершину v.

3. Оператор INITIAL(A, v, С) создает в наборе С новую компоненту с именем А, со держащую только одну вершину v.

Если в исходном графе G всего е ребер, то для вставки их в очередь с приоритетами потребуется время порядка О(е loge). Каждая итерация цикла нахождения ребра е наименьшей стоимостью в очереди edges требует времени порядка О{loge). Поэтому выполнение всего этого цикла в самом худшем случае по­требует времени О(е logе), Вторым фактором, влияющим на время выполнения программы, является общее время выполнения операторов MERGE и FIND, которое зависит от метода реализации АТД MFSET. Существуют методы, требующие времени и О(е loge), и О(е а(е)). В любом случае алгоритм Крускала  может быть выполнен за время О(е logе).