2.4. Поиск путей в графе.

Исторически сложилось 3 знаменитые задачи о поиске путей (цепей).

Задача № 1.

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

Позиции данной игры изображаем вершинами графа, а ходы из одной позиции в другую – дугами (ребрами).

Проблема в том, чтобы найти любой путь из данной позиции в выигрышную.

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

Для больших игр (шахмат и т. д) даже современные компьютеры не позволяют получить полное описание игры и описания стратегии.

Задача № 2.

Найти кратчайший путь из A в B. (в смысле количество ребер или дуг).

Существует простой и эффективный алгоритм решения задачи 1 для любого графа. Будем постепенно присваивать вершинам графа целые числа – индексы.

Шаг 1

Вершине A присваиваем индекс 0.

Шаг 2.

Всем вершинам, смежным с A, присваиваем индекс 1.

Шаг 3.

Всем вершинам смежным с вершинам индекса 1 и не имеющим индекса присваиваем индекс 2. И так далее.

Процесс останавливается, когда вершина B получит некоторый индекс n (даже если остались вершины без индекса).

Число n- это и есть длина кратчайшего пути.

Шаг 4.

Среди вершин, смежных с B обязательно найдется вершина с С индексом n-1.Возвращаемся в С и повторим этот процесс.

Ровно через n шагов мы придем в вершину индекса 0, то есть А.

Вывод: Один или несколько путей построены.

Задача 3.Найти кратчайший путь из A в B во взвешенном графе, в смысле суммы весов всех ребер (дуг).

Существует эффективный алгоритм решения задачи 3 для любого взвешенного графа (поиск в ширину).

План.

Будем постепенно приписывать всем вершинам графа числовые индексы.

Шаг 1.

Вершине А припишем индекс 0, а всем остальным индексы +∞.

Замечание: в различных программах в качестве +∞ берут большое число, заведомо больше суммы всех весов графа.

Шаг 2.

Последовательно переберем все пары смежных вершин x и у.

Каждый раз, проверяя неравенство

ɱy>ɱx+λxy

Если оно выполняется, то уменьшим индекс ɱy заменив его на ɱx+λy

Шаг 3.

Процесс останавливается, когда ни один индекс уже не уменьшается.

В этот момент вершина B имеет некоторый индекс ɱB – это и есть наименьшая сумма весов.

Построим этот путь, возвращаясь из вершины B в вершину A.

Шаг 4.

Среди вершин, смежных с B обязательно найдется С, для которой выполняется точное равенство.

ɱB= ɱс+λСB

Возвращаемся в С и повторим этот процесс.

Так как при этом индексы все время уменьшаются, то через несколько шагов мы придем в вершину индекса 0, то есть в вершину A.

Один или несколько путей построены.

Задача коммивояжера.

Коммивояжер – коммерческий путешественник. Его задача – обойти заданные точки продаж с наименьшими затратами ресурсов.

Видим, что это задача из теории графов. Нужно построить путь (цепь), пропущенный через все вершины графов, с наименьшей суммой весов.

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

Поэтому, проблема в том, чтобы отбрасывать заведомо плохие варианты, оставляя небольшое число «хороших».

Разработано несколько методов: метод ветвей и границ, сведение к задаче линейного программирования и т. д.

Но столь эффективного алгоритма, как для задачи 3, видимо, не существует.