Вступление
Вот классическая задача на графиках. У нас есть группа городов, и мы должны подключить их, чтобы обеспечить всех электричеством. Из всех возможных подключений, которые мы можем установить, используя минимальное количество проводов.
Для подключения N городов очевидно, что вам нужно использовать как минимум N-1 провода, соединяющие пару городов. Проблема в том, что иногда у вас есть несколько вариантов сделать это. Даже для небольшого числа городов должно быть более одного решения, как показано на рисунке ниже.
Здесь мы можем связать эти четыре узла несколькими способами, но вопрос в том, какой из них лучший. Кстати, определение термина «лучший» тоже сложно. Чаще всего это означает, что используется наименьший провод, но это может быть что угодно в зависимости от обстоятельств.
Когда мы говорим о взвешенных графах, мы можем говорить о решении с минимальным весом через все вершины графа.
Кстати, может быть более одного одинаково оптимального (минимального) решения.
обзор
Очевидно, что мы должны выбрать те ребра, которых достаточно, чтобы соединить все вершины графа и сумма весов которых минимальна. Поскольку у нас не может быть циклов в нашем окончательном решении, оно должно сформировать дерево. Таким образом, мы говорим о минимальном весовом остовном дереве, поскольку дерево охватывает весь граф.
Есть ли у каждого связного и взвешенного графа минимальное остовное дерево? Ответ — да! Удаляя циклы из графа G, мы получаем остовное дерево, поскольку оно связно. Из всех возможных связующих деревьев одно или несколько являются минимальными.
Если w (u, v) — вес ребра (u, v), мы можем говорить о весе любого остовного дерева T — w (T), которое является суммой всех ребер, образующих это дерево.
Таким образом, вес минимального остовного дерева меньше, чем вес любого другого остовного дерева G.
После того, как мы уверены, что существует хотя бы одно минимальное остовное дерево для всех связанных и взвешенных графов, нам нужно только как-то его найти.
Мы можем пойти с постепенным подходом. В конце у нас будет минимальное связующее дерево (MST), но перед этим на каждом шаге нашего алгоритма у нас будет подмножество этого конечного дерева, которое будет расти и расти до тех пор, пока оно не станет настоящим MST. Это подмножество ребер мы будем хранить в одном дополнительном наборе А.
Пока мы знаем, что на каждом шаге у нас есть подмножество окончательного MST, но сначала нам нужно ответить на пару вопросов.
Как мы начнем?
Что ж, начнем с пустого набора ребер. Ясно, что пустой набор является подмножеством любого другого набора, поэтому он также будет подмножеством MST.
Как мы выращиваем дерево?
Другой вопрос, на который мы должны ответить, — как вырастить дерево. Так как у нас есть подмножество MST (A) на каждом шаге, как мы добавляем ребро к этому набору, чтобы получить другое (большее, чем предыдущее) подмножество ребер, которое снова будет подмножеством минимального остовного дерева ?
Ясно, что мы должны принять решение, какое ребро добавить к растущему подмножеству, и это сложная часть этого алгоритма.
Выберите самый низкий вес края!
Чтобы найти минимальное остовное дерево на каждом шаге, мы должны получить наименьшее взвешенное ребро, которое соединяет наше подмножество (A) с остальными вершинами.
Однако можем ли мы быть уверены, что, выбрав менее взвешенное ребро, мы получим MST? Что ж, давайте предположим, что это неправильно, чтобы доказать, что это неправильно!
Итак, на каком-то шаге нашего растущего поддерева мы не получим самое легкое ребро (u, v), потому что мы каким-то образом сомневаемся в этом правиле и получаем другое ребро — скажем, (x, y). Имейте в виду, что w (x, y)> = w (u, v).
Таким образом, наше окончательное MST будет содержать где-то в своем множестве ребер ребро (x, y), но вес MST w (T) минимален, и если мы получим другое остовное дерево, которое содержит точно такие же ребра, что и T, но вместо (x, y) содержит (u, v), мы получим меньший вес!
Это невозможно! Таким образом, мы доказали, что на каждом шаге мы должны получить менее взвешенное ребро.
Этот конкретный подход называется «жадным», потому что на каждом этапе мы получаем наилучший возможный выбор. Однако жадные алгоритмы не всегда получают правильное или оптимальное решение. К счастью для MST, это не так, поэтому мы можем быть настолько жадными, насколько можем!
Хорошо, давайте подведем итоги нашего алгоритма в следующем псевдокоде.
Псевдокод
1. We start with an empty set (A) subset of the final MST; 2. Until A does not form T: a. Get the less weighted edge u from G; b. Add u to A; 3. Return A |
заявка
На самом деле этот алгоритм используется в первую очередь Боровкой, которая начала подключать Моравию в 1926 году. Даже не зная, что «жадный» подход приведет его к правильному решению, он оптимально покрыл Моравию электричеством.
Однако этот алгоритм слишком общий, и есть два основных алгоритма — алгоритм Прима и алгоритм Крускала, которые мы увидим в следующих статьях.
Дело в том, что на каждом шаге мы должны получить менее взвешенное преимущество, и оба алгоритма используют для этого разные подходы.
Похожие сообщения: