Клауди Альсина - Том 11. Карты метро и нейронные сети. Теория графов

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

* * *

ИЗОБРЕТЕНИЕ ЦЕНОЙ В ДВЕ ГИНЕИ

Подобные циклы на графах открыл Томас Киркман(1806–1895) . Исследованием этих циклов занимался ирландский математик Уильям Роуан Гамильтон(1805–1865) , он же сделал их широко известными. В 1859 году Гамильтон придумал такую игру: 20 вершин додекаэдра (правильного 12-гранника) соответствуют 20 городам. Нужно обойти все города по одному разу и при этом вернуться в тот же город, с которого началось путешествие. Восторженный Гамильтон продал идею производителю игрушек за смехотворную сумму в две гинеи. Блестящие идеи не всегда ценятся по достоинству!

Математик Уильям Роуан Гамильтони придуманная им игра.

* * *

МЕТОД ПОСТРОЕНИЯ ДЕРЕВА

На рисунках ниже показано, как можно сопоставить исходному графу ABCDдерево всех возможных маршрутов для поиска гамильтоновых циклов, которые начинаются и заканчиваются в вершине А, а вершины В, Си Dобходятся ровно один раз. С увеличением числа вершин поиск гамильтоновых циклов усложняется: в каждом случае исходным является полный граф с nвершинами (им соответствует nгородов). Из каждого города можно попасть в n — 1 город, из каждого из них — в n— 2 города и так далее, пока мы не вернемся в начальную точку. Следовательно, число маршрутов будет равно ( n— 1)·( n— 2)·( n— 3)·… ·3·2·1. Вспомним, что факториалом числа называется произведение всех натуральных чисел от 1 до этого числа включительно (например, 6! = 6·5·4·3·2·1), следовательно, общее число циклов будет равно ( n— 1)!. Так как каждый цикл можно пройти в прямом и обратном направлении, то общее число различных циклов будет в два раза меньше: ( n-1)1/2. Впрочем, и это число будет очень велико: для n— 6 оно составит (6–1)!/2 = 60 циклов.

* * *

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

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

* * *

АЛГОРИТМ БЛИЖАЙШЕГО СОСЕДА

Допустим, что А, B, Си D— города, числа на ребрах графа — расстояние между городами в километрах. Вы находитесь в городе Аи можно выбрать одну из трех дорог длиной в 300 км, 500 км и 600 км. Вы выбираете ближайший город D. Из города Dведут две дороги длиной 350 и 400 км. Вы снова выбираете ближайший город, на этот раз B. Из города Ввы едете в С, затем возвращаетесь в А. Этот алгоритм относится к так называемым «жадным» алгоритмам, так как мы выбираем оптимальное решение на каждом шаге: наименьшие затраты, минимальное время или расстояние (так называемый «жадный» выбор). Этот алгоритм не гарантирует, что конечное решение всегда будет оптимальным. Альтернативой является алгоритм сортировки ребер графа, который также не гарантирует оптимальность решения. В этом алгоритме на каждом шаге выбирается ребро с наименьшим весом, если они не препятствуют построению гамильтонова цикла.

* * *

Решить задачу путешественника на больших графах очень сложно. По этой причине она является классическим примером так называемых NP-полных задач, то есть задач, для которых невозможно найти «быстрый» алгоритм поиска оптимальных решений. В информатике под быстротой алгоритма понимается скорость выполнения компьютерных программ, реализующих этот алгоритм.