6.10. Матричная форма задачи о переправе

Решим предложенную в предыдущем разделе задачу о переправе через реку миссионеров и людоедов, используя при этом матрицу смежности вершин.

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

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

Заметим, что состояние недопустимо, так как соответствующее состояние на правом берегу будет и единственный миссионер будет съеден. Аналогично, состояние недопустимо и на левом берегу. Образуем матрицу смежности, элементы которой равны 1 или в зазисимости от того, возможен ли переход из одного состояния на левом берегу к другому состоянию также на левом берегу. Переходы, конечно, определяются отъездами лодки. Таким образом, мы выписываем названия вершин слеза и сверху матрицы и расставляем

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

Для правого берега реки мы будем иметь идентичное множество состояний, которые являются дополнительными к состояниям левого берега. Их матрица V является транспонированной относительно выписанной выше матрицы Нетрудно проверить, что для получения матрицы возможных переходов после одного переезда лодки туда и обратно необходимо перемножить V4V. В общем случае, чтобы получить матрицу переходов после переездов лодки туда и обратно, нужно вычислить А так как наша цель заключается в переправе группы на правый берег, то необходимо умножить на Это даст и задача свелась к определению числа двусторонних (т. е. туда и обратно) переездов лодки, при котором элемент, стоящий на пересечении строки и столбца матрицы равен 1, т. е. на левом берегу имеет место переход из состояния в состояние и вся группа оказывается на правом берегу. Заметим, что величина элементов произведений указывает на число способов, которыми можно осуществить соответствующий переход. Это число может быть больше 1. Так как наша цель состоит в определении для каждого состояния одного возможного перехода, то все ненулевые элементы произведений можно положить разными 1. Оказывается, что исходную задачу можно решить путем двусторонних переездов и одного (последнего) одностороннего единичный элемент впервые появляется на пересечении строки и столбца в матрице Результаты последовательных

вычислений имеют следующий вид:

Теперь задача состоит в том, чтобы восстановить решение по найденным матрицам. Рассмотрим элемент последней матрицы Этот элемент является единичным. Найдем возможные ненулевые элементы первой строки матрицы которые при умножении на седьмой столбец давали бы единичное значение рассматриваемого элемента. Одним из таких элементов является элемент в первой строке и четвертом столбце матрицы так как элемент матрицы V также является единичным. Другим элементом V с таким же свойством является (5,7). Выберем первый из названных элементов. Таким образом, получаем, что последний переход есть Далее смотрим, каким способом мог получиться единичный элемент (1,4) матрицы Проверив первую строку и четвертый столбец V, получаем, что рассматриваемый единичный элемент есть результат наличия ненулевого элемента в матрице V (так как соответствующий элемент матрицы также отличен от

нуля). Таким образом, предпоследний переход есть

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

Дадим словесную интерпретацию полученного решения. Так как есть оба людоеда должцы переправиться одновременно, причем один из них должен вернуться (из-за Затем вернувшийся людоед должен высадиться, а два миссионера должны занять место в лодке. После причаливания к правому берегу один из миссионеров должен высадиться (чтобы получить а другой вернуться обратно, чтобы получить Наконец, последний миссионер и людоед переправляются вместе на правый берег. При этом достигается конечное состояние

(см. скан)

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

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

матрицы для любой степени Это уже существенно более простая задача даже при очень больших матрицах. Пусть множество состоит из вершин, соответствующих единичным элементам первой строки матрицы В эти вершины можно попасть из вершины за один круговой проход. Добавим к этому множеству все вершины, которым соответствуют единичные элементы в строке матрицы VV. Новое расширенное множество содержит вершины, в которые можно попасть из за два круговых прохода. Будем повторять такой процесс расширения для всех новых вершин множества до тех пор, пока не переберем всех вершин множества. Множество, полученное в результате такого процесса, состоит из всех вершин, в которые можно попасть из за произвольное число круговых проходов. Если это множество содержит вершины, которым соответствуют ненулевые элементы в столбце матрицы V, то исходная задача имеет решение. В противном случае решение не существует.

Рассмотрим в качестве примера задачу с четырьмя миссионерами и четырьмя людоедами. Пусть вершины графа (число миссионеров, число людоедов)

Задача состоит в том, чтобы перейти из

В 13-м столбце элементы не равны нулю. Следовательно, если задача имеет решение, то элементы первой строки матрицы также должы быть ненулевыми:

Множество вершин, в которые можно попасть из , состоит из Из можно попасть в Поэтому добавим к первоначальному множеству и получим расширенное множество Из можно попасть в Вводя новые вершины, получим множество Из можно перейти в Оба эти перехода не изменяют множества. На этом все возможности исчерпаны. Следовательно, из можно попасть только в и нельзя попасть в ни при каком числе круговых проходов. Но в столбце матрицы V ненулевыми являются только элементы Так как ни один из этих элементов не вошел в окончательное множество, можно сделать вывод, что исходная задача не имеет решения.

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

доказываемое за 2 шага, например, вместе означают Единичные элементы матрицы, являющейся третьей степенью исходной, указывают постулаты или утверждения, которые могут быть доказаны за 2 или за 3 шага. Наконец, степень показывает все утверждения. Возникает интересная задача нахождения наименьшего числа постулатов, из которых можно вывести заданное множество утверждений. Заметим, что существует, по крайней мере, множеств эквивалентных постулатов, позволяющих получить теорем [70], [73].

(см. скан)