Задача нахождения минимального остовного дерева - Жадные алгоритмы

А теперь мы воспользуемся методом замены в контексте второй фундаментальной задачи графов: задачи нахождения минимального остовного дерева.

Задача

Имеется множество точек V = {v₁, v₂, ..., v_n}; требуется построить для них коммуникационную сеть. Сеть должна быть связной (то есть в ней должен существовать путь между любой парой узлов), но при соблюдении этого требования сеть должна быть построена с минимальными затратами.

Для некоторых пар (v_i, v_j) можно построить прямой канал с определенными затратами c(v_i, v_j) > 0. Таким образом, множество всех возможных каналов представляется графом G = (V, E), в котором с каждым ребром e = (v_i, v_j) связывается положительная стоимость с_e. Задача заключается в нахождении такого подмножества ребер T ⊆ E, чтобы граф (V, T) был связным, а общая стоимость была как можно меньшей. (Предполагается, что полный граф G является связным; в противном случае решение невозможно.)

Ниже приведено базовое наблюдение.

(4.16) Пусть T — решение описанной выше задачи проектирования сети с минимальной стоимостью. В этом случае (V, T) является деревом.

Доказательство. По определению граф (V, T) должен быть связным; мы покажем, что он также не содержит циклов. Предположим, граф содержит цикл C, а e — любое ребро C. Утверждается, что граф (V, T - {e}) остается связным, потому что любой путь, который использовал ребро e, теперь может воспользоваться “обходным путем” по оставшейся части цикла C. Из этого следует, что (V, T- {e}) также является действительным решением задачи, и при этом оно имеет меньшую стоимость, — обнаружено противоречие. ■

Если допустить, что некоторые ребра могут иметь нулевую стоимость (то есть предполагается лишь то, что значения с_е не отрицательны), то решение задачи проектирования сети с минимальной стоимостью может содержать лишние ребра — такие ребра имеют нулевую стоимость и при желании могут быть удалены. Начиная с любого оптимального решения, мы можем удалять ребра в циклах до тех пор, пока не возникнет дерево; с неотрицательными ребрами общая стоимость при этом не увеличится.

Подмножество T ⊆ E будет называться остовным деревом графа G, если (V, T) является деревом. Утверждение (4.16) указывает на то, что цель задачи проектирования сети можно переформулировать как задачу поиска остовного дерева графа с минимальной стоимостью; по этой причине эта задача обычно называется задачей нахождения минимального остовного дерева. Во всех графах G, кроме очень простых, количество разных остовных деревьев растет по экспоненциальному закону, а их структуры могут сильно отличаться друг от друга. Совершенно непонятно, как эффективно найти дерево с минимальной стоимостью среди всех этих вариантов.

Разработка алгоритма

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

Итак, перед вами три жадных алгоритма, каждый из которых правильно находит минимальное остовное дерево.

♦ Один простой алгоритм начинает с пустого дерева и строит остовное дерево, последовательно вставляя ребра из E в порядке возрастания стоимости. При перемещении по ребрам в этом порядке каждое ребро e вставляется в том случае, если при добавлении к ранее вставленным ребрам оно не создает цикл. Если же, напротив, вставка e порождает цикл, то ребро e просто игнорируется, а выполнение алгоритма продолжается. Такое решение называется алгоритмом Крускала.

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

Или говоря конкретнее, алгоритм поддерживает множество S ⊆ V, для которого уже было построено остовное дерево. В исходном состоянии S = {s}. При каждой итерации S наращивается на один узел; при этом добавляется узел, минимизирующий “стоимость присоединения” и ребро e = (u, v), обеспечивающее этот минимум в остовном дереве. Такое решение называется алгоритмом Прима.

♦ Наконец, жадный алгоритм может представлять собой своего рода “алгоритм Крускала наоборот”, а именно: он начинает с полного графа (V, E) и удаляет ребра в порядке уменьшения стоимости. При переходе к каждому ребру e (начиная с самого дорогого) это ребро удаляется, если это не приводит к потере связности текущего графа. Обычно этого алгоритм называется алгоритмом обратного удаления (насколько нам известно, с именем конкретного человека он никогда не связывался).

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

Рис. 4.9. Пример выполнения алгоритмов нахождения минимального остовного дерева: а — алгоритм Прима; b — алгоритм Крускала, для общих входных данных. Первые четыре ребра, добавленных в остовное дерево, обозначены сплошными линиями; следующее добавляемое ребро обозначено пунктиром

Тот факт, что каждый из этих алгоритмов гарантированно строит оптимальное решение, предполагает определенную “устойчивость” задачи нахождения минимального остовного дерева — ответ можно получить разными способами. Затем мы исследуем некоторые причины, из-за которых минимальные остовные деревья могут строиться настолько разными алгоритмами.

Анализ алгоритмов

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

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

(4.17) Допустим, все стоимости ребер различаются. Пусть S — любое подмножество узлов, не пустое и не равное V, и пусть ребро е = (v, w) — ребро минимальной стоимости, один конец которого принадлежит S, а другой — V - S. В этом случае ребро e входит в каждое минимальное остовное дерево.

Доказательство. Пусть Т — остовное дерево, не содержащее е; необходимо показать, что стоимость T не является минимально возможной. Для этого мы воспользуемся методом замены: найдем в T ребро е' с большей стоимостью, чем у е, и с тем свойством, что замена е на е' приводит к другому остовному дереву. Полученное остовное дерево будет обладать меньшей стоимостью, чем у T, как и требовалось.

Таким образом, вся суть в том, чтобы найти ребро, которое можно успешно обменять с е. Вспомните, что концами е являются узлы v и w. T — остовное дерево, поэтому в T должен существовать путь из v в w. Предположим, начиная с v, мы последовательно переходим по узлам P; в P существует первый узел w', который принадлежит V - S. Пусть v' ∈ S — узел, непосредственно предшествующий w' в P, а е' = (v', w') — соединяющее их ребро. Следовательно, е' — ребро T, один конец которого принадлежит S, а другой — V - S. Ситуация для этой стадии доказательства представлена на рис. 4.10.

Рис. 4.10. Ребро е меняется с ребром е' в остовном дереве T, как описано в доказательстве (4.17)

Заменив e на e', мы получаем множество ребер T = T - {e'} U {e}. Утверждается, что T — остовное дерево. Очевидно, граф (V, T') является связным, поскольку связным является (V, T), а любой путь в (V, T), который использовал ребро e' = (v', w'), теперь может быть “перенаправлен” через (V, T') для прохождения части P от v' до v, ребра e и затем части P от w до w'. Чтобы понять, что граф (V, T') также является ациклическим, следует заметить, что единственный цикл в (V, T U {e'}) состоит из e и пути P, но этот цикл не присутствует в (V, T') из-за удаления e'.

Ранее было отмечено, что один конец ребра e' принадлежит S, а другой — V - S. Но e является ребром с минимальной стоимостью, обладающим этим свойством, поэтому с_e < с_e'. (Неравенство строгое, потому что никакие два ребра не обладают одинаковой стоимостью.) Следовательно, общая стоимость T меньше общей стоимости T, как и требуется. ■

Доказательство (4.17) немного сложнее, чем кажется на первый взгляд. Чтобы понять эту сложность, возьмем следующее (более короткое, но неправильное) обоснование для (4.17). Пусть T — остовное дерево, которое не содержит e. Так как T является остовным деревом, оно должно содержать реброf один конец которого принадлежит S, а другой — V - S. Так как e является самым “дешевым” ребром, обладающим таким свойством, выполняется условие с_е < с_f, а значит, T - {f} U {e} — остовное дерево с меньшей стоимостью, чем у T.

Проблема с этим обоснованием связана не с утверждением о том, что f существует или что T - {f} U {e} имеет меньшую стоимость, чем T. Проблема в том, что T - {f} U {e} может не быть остовным деревом, как видно на примере ребра f на рис. 4.10. Утверждение (4.17) нельзя доказать простым выбором любого ребра в T, переходящего из S в V - S; необходимо принять меры к тому, чтобы найти правильное ребро.

Оптимальность алгоритмов Крускала и Прима

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

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

Доказательство. Рассмотрим любое ребро e = (v, w), добавленное алгоритмом Крускала. Пусть S — множество всех узлов, к которым существует путь из v непосредственно перед добавлением e. Очевидно, v ∈ S, но и w ∈ S, так как добавление e не приводит к созданию цикла.

Более того, никакое ребро из S в V - S еще не было обнаружено, так как любое такое ребро может быть добавлено без создания цикла, а значит, было бы добавлено алгоритмом Крускала. Следовательно, e — ребро с минимальной стоимостью, у которого один конец принадлежит S, а другой — V - S, и, согласно (4.17), оно принадлежит минимальному остовному дереву.

Итак, если нам удастся показать, что результат (V, T) алгоритма Крускала действительно является остовным деревом графа G, то дело будет сделано. Очевидно, (V, T) не содержит циклов, поскольку алгоритм проектировался для предотвращения создания циклов. Кроме того, если граф (V, T) не был связным, то существовало бы непустое множество узлов S (не равное всему множеству V), такое, что не существует ребра из S в V- S. Но это противоречит поведению алгоритма: мы знаем, что поскольку граф G является связным, между S и V - S существует как минимум одно ребро, и алгоритм добавит первое из таких ребер при его обнаружении. ■

(4.19) Алгоритм Прима строит минимальное остовное дерево графа G. Доказательство. Для алгоритма Прима также очень легко показать, что он добавляет только ребра, принадлежащие любому возможному минимальному остовному дереву. В самом деле, при каждой итерации алгоритма существует множество S ⊆ V, на базе которого было построено частичное остовное дерево, и добавляется узел v и ребро е, которые минимизируют величину По определению е является ребром с минимальной стоимостью, у которого один конец принадлежит S, а другой — V - S, поэтому по свойству сечения (4.17) оно присутствует в каждом минимальном остовном дереве.

Также тривиально показывается, что алгоритм Прима строит остовное дерево графа G — а следовательно, он строит минимальное остовное дерево. ■

Когда можно гарантировать, что ребро не входит в минимальное остовное дерево?

При удалении ребер критичен следующий факт, который мы будем называть “свойством цикла”.

(4.20) Предполагается, что стоимости всех ребер различны. Пусть C — любой цикл в G, а ребро е = (v, w) — ребро с максимальной стоимостью, принадлежащее C. В этом случае е не принадлежит никакому минимальному остовному дереву графа G.

Доказательство. Пусть T — остовное дерево, содержащее е; необходимо показать, что T не обладает минимальной возможной стоимостью. По аналогии с доказательством свойства сечения (4.17) мы воспользуемся методом замены, подставляя на место е ребро с меньшей стоимостью так, чтобы не разрушить остовное дерево.

Итак, мы сталкиваемся с тем же вопросом: как найти ребро с меньшей стоимостью, которое можно поменять местами с е? Начнем с удаления е из T; узлы при этом делятся на два подмножества: S, содержащее узел v; и V - S, содержащее узел w. Теперь один конец ребра, используемого вместо е, должен принадлежать S, а другой — V - S, чтобы снова объединить дерево.

Такое ребро можно найти переходом по циклу C. Ребра C, отличные от е, по определению образуют путь P, один конец которого находится в узле v, а другой в узле w. Если перейти по P от v к w, переход начнется в S и закончится в V - S, поэтому в P существует некоторое ребро е', соединяющее S с V - S. Ситуация изображена на рис. 4.11.

Теперь рассмотрим множество ребер T' = T - {е} U {е'}. По причинам, изложенным при доказательстве свойства сечения (4.17), граф (V, T') является связным и не содержит циклов, поэтому T' является остовным деревом G. Кроме того, поскольку e — самое “дорогое” ребро цикла C, а e' принадлежит C, стоимость e' должна быть ниже, чем у e, а следовательно, стоимость T ниже стоимости T, как и требовалось. ■

Рис. 4.11. Замена ребра e ребром e' в остовном дереве T в соответствии с доказательством (4.20)

Оптимальность алгоритма обратного удаления

Располагая свойством цикла (4.20), можно легко доказать, что алгоритм обратного удаления строит минимальное остовное дерево. Базовая идея аналогична доказательствам оптимальности двух предыдущих алгоритмов: алгоритм обратного удаления добавляет ребро только в том случае, если это оправданно согласно (4.20).

(4.21) Алгоритм обратного удаления строит минимальное остовное дерево графа G.

Доказательство. Рассмотрим любое ребро e = (v, w), удаляемое алгоритмом обратного удаления. На момент удаления в находится в цикле C; и поскольку это первое ребро, обнаруженное алгоритмом в порядке убывания стоимости ребер, оно должно быть ребром с максимальной стоимостью в C. Следовательно, согласно (4.20), ребро в не принадлежит никакому минимальному остовному дереву.

Итак, если показать, что результат (V, T) алгоритма обратного удаления является остовным деревом графа G, дело будет сделано. Очевидно, граф (V, T) является связным, потому что алгоритм не станет удалять ребро, если это приведет к потере связности графа. Действуя от обратного, предположим, что (V, T) содержит цикл C. Рассмотрим ребро в с максимальной стоимостью в C, которое будет первым обнаружено этим алгоритмом. Это ребро должно быть удалено, потому что его удаление не приведет к потере связности графа, но это противоречит поведению алгоритма обратного удаления. ■

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

Отказ от предположения о различной стоимости всех ребер

До настоящего момента предполагалось, что все стоимости ребер различны; такое предположение упростило анализ в ряде мест. Но предположим, имеется экземпляр задачи минимального остовного дерева, которого некоторые ребра имеют одинаковую стоимость, — как убедиться в том, что рассмотренные алгоритмы по-прежнему обеспечивают оптимальные решения?

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

Более того, можно утверждать, что любое минимальное остовное дерево T для нового, измененного экземпляра также должно являться минимальным остовным деревом для исходного экземпляра. Убедиться в этом несложно: если стоимость T больше стоимости некоторого дерева T* в исходном экземпляре, то для достаточно малых отклонений изменение стоимости T не может быть достаточным, чтобы оно стало лучше T* с новыми стоимостями. Таким образом, при выполнении любого из наших алгоритмов минимального остовного дерева с измененными стоимостями для сравнения ребер будет получено минимальное остовное дерево T, которое также является оптимальным для исходного экземпляра.

Реализация алгоритма Прима

Обсудим реализацию рассмотренных алгоритмов и попробуем получить хорошие оценки времени выполнения. Как вы увидите, алгоритмы Прима и Крускала с правильным выбором структур данных могут быть реализованы с временем выполнения O(m log n). В этом разделе показано, как это делается для алгоритма Прима, а обсуждение реализации алгоритма Крускала приводится в следующем разделе. Для алгоритма обратного удаления получить время выполнения, близкое к этому, непросто, поэтому этим алгоритмом мы заниматься не будем.

Хотя для алгоритма Прима доказательство правильности сильно отличалось от доказательства алгоритма Дейкстры для кратчайшего пути, реализации алгоритмов Прима и Дейкстры почти идентичны. По аналогии с алгоритмом Дейкстры для принятия решения о том, какой узел v добавить следующим в растущее множество S, следует хранить стоимости присоединения для каждого узла v ∈ V - S. Как и в предыдущем случае, узлы хранятся в приоритетной очереди, использующей стоимости присоединения a(v) в качестве ключей; узел выбирается операцией ExtractMin, а для обновления стоимости присоединения используются операции ChangeKey. Всего существует n - 1 итераций, на которых выполняется операция ExtractMin, а операция ChangeKey выполняется не более одного раза для каждого ребра. Следовательно:

(4.22) При использовании приоритетной очереди алгоритм Прима для графа с n узлами и m ребрами может быть реализован с выполнением за время O(m) с добавлением времени n операций ExtractMin и m операций ChangeKey.

Как и в случае с алгоритмом Дейкстры, приоритетная очередь на базе кучи позволяет реализовать операции ExtractMin и ChangeKey за время O(log n), а следовательно, обеспечивает общее время выполнения O(m log n).

Расширения

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

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

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

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

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