назад

3.8 Кратчайшие пути в цепи

1. Есть известная задача о волке, козе и капусте. Хозяин должен переправить их с левого берега реки на правый, пользуясь лодкой, в которой кроме него может поместиться только один из трех "пассажиров" При этом по понятным причинам нельзя в отсутствие хозяина вместе волка с козой, а также козу с капустой. В каком порядке проводить переправу? Задача довольно легко решается в уме из-за малого числа вариантов, однако рассмотрим ее с прицелом на более общий случай.

На правом берегуНа левом берегу На правом берегу
123       4
Рисунок 14

На рисунке 14 - сеть, вершинами которой являются всевозможные расположения на двух берегах четырех участников: X (хозяин), Кз (коза),. Кп (капуста), В (волк). Каждую ситуацию, возникающую в процесс переправы, можно охарактеризовать подмножеством А персонаже находящихся на этом этапе на левом берегу; дополнение подмножества - участники, перевезенные на правый берег. Общее; количество подмножеств 4-элементного множества равно 24 = 16. Ребра графа связывают вершины и β, если из ситуации можно перейти ситуацию β за одну ходку (переправу). Поскольку возможен и обратный рейс из β в , то можно считать граф неориентированным.

Множество вершин естественно разбивается на 2 части: с присутствием (столбец 2 на рисунке 14) или отсутствием (столбец 3 рисунок 14) на левом берегу хозяина; очевидно, что граф - двудольный, т.к. при каждой переправе этот признак меняется. Например, вершина <Х Кз Кп> связана с вершинами <Кп> (если хозяин перевозит на правый берег козу), <Кз> (если перевозит капусту) и <Кз Кп> (если переправляется один). Вершина <Кп В> (хозяин с козой находятся на правом берегу) связана с вершинами <Х Кз Кп В> (если хозяин возвращается на, левый берег с козой) и <Х Кп В> (если он возвращается один). В крайних столбцах рисунок 14 для наглядности представлены дополнения к подмножествам-вершинам.

Задачу теперь можно сформулировать так: найти цепь из полюса <Х Кз Кп В> (все на левом берегу) в полюс <Ø> (все на правом берегу, на левом - никого), причем нельзя проходить через запрещенные вершины, обозначенные на рисунке 14 двойной рамкой: например, ситуация <Кз В> означает опасную пару без хозяина на левом берегу, а ситуация <Х В> - на противоположном берегу коза соседствует с капустой.


Рисунок 15

Удалим теперь из сети запрещенные вершины вместе с инцидентными им ребрами: результат представлен на рисунке 15. Теперь достаточно изобразить полученную сеть в более удобном виде, как на рисунке 16. Здесь решение очевидно: обнаруживаются даже две различные элементарные цепи.



Рисунок 16

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

Один из них основан на следующей конструкции. Будем присваивать вершинам сети S ранг (целочисленную метку): входному полюсу s - ранг 0; вершинам, смежным с полюсом s, - ранг 1i непомеченным вершинам, смежным с вершинами первого ранга, - ранг-2 и т.д. На k-ом этапе процесса непомеченным вершинам, смежным с вершинами (k - 1)-го ранга, присваивается ранг k. Ранг вершины равен расстоянию до нее от полюса s. На каждом этапе вершины очередного ранга образуют как бы фронт распространения волны от полюса s. Процесс закончится, когда ранг будет присвоен выходному полюсу βS (если это не произойдет, то сеть S несвязна). Кратчайшая цепь [s, βs] (не единственная) определяется некоторой последовательностью вершин различных рангов: каждая вершина k-ro ранга, начиная с βS, связана ребром со смежной вершиной (k - 1)-го ранга (например, с той, по которой получила свой ранг).

Для графа на рисунке 17 представлены ранги вершин при определении . расстояния и кратчайшей цепи из А в В и указана одна из них.


Рисунок 17

Модификация этого алгоритма состоит в одновременном построении двух фронтов волн, исходящих из s и βs: процесс заканчивается, когда эти волны встретятся.

3. Для ориентированной сети с присвоенными ее дугам длинами {/(ек)} алгоритм построения кратчайшего пути несколько иной. Метки (Vi), присваиваемые вершинам, могут изменяться в процессе построения. Первоначально пометим полюс s числом 0, а каждую из остальных вершин -.достаточно большим числом L (например, превышающим сумму длин всех дуг сети). Далее будем, пока возможно, производить-следующее преобразование (смену) меток (vi). Если для некоторой дуги е = (v1, v2) выполнено строгое неравенство (v2) - (v1) > /(е), то присвоим вершине v2 (концу дуги е) новую, меньшую метку: (v2)=(v1 + l(е). Через конечное число таких операций для любой дуги е будет выполнено нестрогое неравенство (v2) - (v1)≤ l(е). Тогда s) будет равно длине кратчайшего пути [s, βs]. Отыскать этот путь можно, двигаясь подобно предыдущему, обратным ходом из βs в s по дугам е = (v', v"), для которых (v") = (v') + l(е).

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


Рисунок 18

Таблица 3
α0          0
A100         5
B100  16D   8A   8
C100   21B   13B  13
D100 14α       11B11
β100    27C21D  19C 8D

 

Вопросы для самоконтроля

  1. Разберитесь с общими случаями решения задачи о переправе волка, козы и капусты на другой берег.
  2. Изучите алгоритм отыскивания цепи в произвольной сети, в ориентированном и неориентированном графах.