Начинают с пустого подргафа. Формируют последовательность из (не обязательно связных) подграфов, добавляя на каждой стадии дугу с самой маленькой стоимостью, не допуская при этом образования петель у существующего подграфа. Когда возникает ситуация, при которой дальнейшее добавление ребер оказывается невозможным, получают результирующий подграф, представляющий собой минимальное остовное дерево. Для примера сети изображенной на рис. 12. Последовательность дуг, присоединяемых к минимальному остовному дереву по алгоритму Краскала следующая: первой присоединяется дуга с наименьшей стоимостью 1, далее две дуги со стоимостью 2, затем дуга со стоимостью 3 и последней дуга стоимости 4. Стоимость минимального остовного дерева 12.
ЛЕКЦИЯ 5. Проблема коммивояжера. Алгоритмы «ближайшего соседа», «самой близкой вставки»
Коммивояжер должен посетить каждый из заданных городов и возвратиться к своему первоначальному положению. Учитывая сеть дорог, соединяющих различные города на его маршруте, проблема путешествующего коммивояжера состоит в том, чтобы найти маршрут, который минимизирует полное расстояние его путешествия. При этом такой маршрут допускает посещение некоторых городов более одного раза.
Сеть дорог может быть представлена взвешенным графом (сетью). Каждый город представляется вершиной, а каждая дорога, соединяющая два города представляется ребром, соединяющим соответствующие два вершины, причем вес ребра равен длине данной дороги. Путешествие, при котором посещается каждый город и которое заканчивается в исходном стартовом положении, представляется замкнутой последовательностью ребер графа, у которого последовательность связанных вершин содержит все вершины. В терминологии теории графов проблема коммивояжера состоит в том, чтобы найти такую замкнутую последовательность ребер, полный вес которой является минимальным. Мы предположим, что граф связан так, что для коммивояжера действительно оказывается возможным посетить каждый город, используя дороги данной сети.
Как правило, оказывается целесообразным несколько видоизменить исходную проблему следующим образом. Граф, описанный выше, заменяется полным графом с одной вершиной для каждого города. (Напомним, что полный граф — это такой граф, у которого имеется единственное ребро, соединяющее каждую пару отличных вершин.) Каждому ребру такого графа приписывается вес, равный наикротчайшему расстоянию между соответствующими городами, в соответствии с используемой сетью дорог. Эти самые короткие расстояния могут быть найдены, на основании применения алгоритма Дейкстры к первоначальному графу. Вес ребра в полном графе может быть меньше, чем вес ребра, соединяющего те же самые вершины в первоначальном графе. Это связано с тем, что может найтись маршрут между двумя вершинами итоговая длина которого будет меньшей, чем длина единственного ребра соединяющего эти две вершины. Чтобы мы могли позже возвращать информацию относительно исходного графа (который может и не являться полным графом), мы должны будем хранить записи связанные с информацией о том, какие пути исходного графа формировали ребра полного графа.
Замкнутая последовательность ребер, позволяющая посетить все вершины графа представляющего дорожную сеть соответствует цепи Гамильтона в полном графе Таким образом, проблема коммивояжера может быть сформулирована следующим образом.
ПРОБЛЕМА КОММИВОЯЖЕРА. Для заданного связанного, взвешенного, полного графа требуется построить цепь Гамильтона минимального веса; то есть минимальную цепь Гамильтона.
Напомним, что не каждый граф имеет цепь Гамильтона; однако, каждый полный граф, имеющий, по крайней мере, три вершины, имеет цепь Гамильтона, что непосредствен. Так как наши графы конечны, то может иметься только конечное число цепей Гамильтона, и следовательно, среди них должна быть и минимальная.
Так как веса ребер в полном графе - это самые короткие расстояния между вершинами первоначального графа сети дорог, то для полного графа должно выполняться следующее неравенство треугольника.
Для каждого триплета отличных вершин (V1;V2, V3) справедливо:
d12 + d23 ≥ d13,
где dij - - вес единственного ребра, соединяющего Vi и Vj.
Проблема коммивояжера в виду своего большого практического значения получила значительное внимание со стороны теоретиков, и было разработано много различных алгоритмов для строительства минимальной цепи Гамильтона. Одна из причина большого интереса к данной проблеме связана с тем фактом, что все известные алгоритмы, которые решают данную проблему являются в вычислительном отношении неэффективными относительно числа вершин, то есть все известные алгоритмы являются алгоритмами показательного времени. Тем не менее, с практической точки зрения известны различные эффективные алгоритмы, которые дают приблизительное решение. Другими словами, они обеспечивают цепи Гамильтона, чей вес оказывается близким к минимально возможному, однако при этом нельзя быть уверенным в том, что данный вес является самым минимальным из возможных.
Имеется достаточно очевидный и простой "приблизительный" алгоритм, так называемый известный «алгоритм ближайшего соседа». Это своего рода модификация алгоритма поиска по глубине.
Идея алгоритма «ближайшего соседа». Алгоритм начинается в любой вершине и «идет» по ребрам с самым маленьким весом, которые (ребра) оказываются инцидентными вершине. На каждом шаге алгоритма, мы начинаем развитие событий с последней из числа посещенных вершин и двигаемся вдоль ребер с наименьшим из возможных значений веса по направлению к новым вершинам. (Могут иметься несколько возможностей выбора «минимального ребра» на каждой стадии.) Когда все вершины окажутся посещенными, мы возвращаемся к стартовому положению по единственному ребру полного графа от последней вершины, назад к первой.
Наиболее похожим алгоритмом является жадный алгоритм (в том смысле, что именно ближайшие вершины посещаются на каждой стадии). Оказывается, что этот алгоритм чрезвычайно беден в следующем смысле. Хотя этот алгоритм в некоторых случаях и будет производить минимальный цикл Гамильтона, как правило, цикл, произведенный таким алгоритмом может иметь вес значительно превышающий возможный минимум. Фактически работа данного алгоритма примерно настолько плоха, как только это можно себе представить. Взяв любое положительное целое число k (сколь угодно большое) всегда найдутся графы, для которых вес цикла Гамильтона, полученного на основании алгоритма ближайшего соседа, окажется в k раз больше веса минимального цикла.
Рассмотрим другой "приблизительный" алгоритм — «алгоритм самой близкой вставки». Он гарантирует нахождение цикла Гамильтона с полным весом, который не более, чем в два раза превышает минимальный цикл. Причем, как правило, алгоритм самой близкой вставки порождает цикл Гамильтона с весом, значение которого оказывается значительно меньше двойного минимума
Идея алгоритма самой близкой вставки. Основной шаг в алгоритме самой близкой вставки заключается в том, чтобы взять в графе цикл и увеличить его, включая в него самые близкие к нему вершины. Этот шаг повторяется до тех пор, пока все вершины не окажутся включенными в цикл.
Алгоритм может применяться к любому полному взвешенному графу, для которого выполняется неравенство треугольника.
