Дискретно-непрерывная математика (стр. 72 )

МММССК МММК ССК СК

МММСС ММСС МС С

МММСK ММСK МK K

МММС МММ СС 0

Здесь 0 означает, что на берегу А нет ни одного чело­века (читатель может проверить, что в остальных вось­ми состояниях основное правило нарушается либо на одном, либо на другом берегу). Изменения состояний этой системы соответствуют отъезду или возвращению лодки. На графе рис. 5.20 показаны все (25) возможных переходов.

Рис. 5.20.

Для упрощения переходы изображены в ви­де ребра, так как возможно любое направление. Однако каждое ребро следует рассматривать как две проти­воположно ориентированные дуги, соответствующие отъ­езду лодки (направление по часовой стрелке) и возвра­щение лодки (направление против часовой стрелки). Новая формулировка задачи выглядит так: найти (если возможно) путь из МММССК в 0, в котором дуги, соот­ветствующие отъезду и возвращению, чередуются.

Без последнего условия задача решается легко. (На­пример, последовательность состояний МММССК, ММСК, СК, 0 дает решение.) С учетом этого условия задача становится значительно более трудной. Прежде чем двигаться дальше, читатель может поработать некоторое время с графом рис. 5.20 и либо найти реше­ние, либо убедиться, что его нет. Для того чтобы дать систематический способ поиска решения, определим вспо­могательный граф, имеющий те же самые вершины. Вспомогательный граф вводится для того, чтобы отра­зить возможные изменения состояния системы между

двумя последовательными возвращениями лодки. Тем самым исключается необходимость чередовать дуги, со­ответствующие отъезду и возвращению лодки.

Пусть, например, лодка стоит у берега A, а система находится в состоянии МММС. Из рис. 5.20 мы видим, что система может перейти в состояние ММСС или ММСК через состояние МС (заметим, что при этом лод­ка снова окажется у берега a). Поэтому соединяем реб­ра МММС с ММСС и ММСК. На рис. 5.21 показаны все такие ребра (включая ориентированные ребра, ве­дущие в конечное состояние 0, которые соответствуют последнему переезду без возвращения лодки на берег A).

Рис. 5. 21.

Для вспомогательного графа рис. 5.21 задача за­ключается в следующем: определить цепь из МММССК в 0. Легко видеть, что такая цепь существует. Напри­мер, МММССК, МММСК, МММК, ММСК, ММСС, ССК, МС, 0 является искомой цепью. Добавляя (в скоб­ках) промежуточные состояния, получим следующее решение для первоначального графа рис. 5.20: МММССК, (ММСК), МММСК, (МММ), МММ К, (МК), ММСК, [(МС), ММСС, (СС), ССК, (С), МС, 0. Это решение показано на рис. 5.22.

Рис. 5.22.

Отметим, что найденный путь не является простым, так как две дуги входят в ММСК и МС (в каждом случае одна дуга соответствует отъез­ду лодки от берега А, а вторая — возвращению лодки).

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

14. Для ориентированного графа, показанного на рис. 5.23, определить путь из v в w, в котором чередуются сплошные и пунк­тирные дуги, причем первая дуга является сплошной.

Рис. 5.23.

a) Решить задачу, использовав для исследования исходного гра­фа рис. 5.23.

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

c) Отметим, что решение не является простым путем в первона­чальном графе. (Действительно, путь возвращается в v.)

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

Рассмотрим, например, плоский лабиринт, показан­ный на рис. 5.24.

Рис. 5.24.

Этот лабиринт состоит из 36 отделе­ний, некоторые из которых соединены «проходами» (указанными разрывами в линиях). Предположим, что задача заключается в том, чтобы достигнуть точки Q вне лабиринта, начиная из отделения Р. Рассмотрим граф, вершины которого соответствуют отделениям, а ребра указывают, какие пары соседних отделений со­единены проходом. Этот граф показан на рис. 5.24. Для данного графа задача заключается в определении цепи, соединяющей Р и Q. В такой формулировке задача является очень простой. Построив граф, соответствующий данному лабиринту, мы можем применить методы поме­ток и определить дерево, соединяющее Р со всеми другими вершинами (отделениями). При этом, в частности, мы найдем и цепь, соединяющую Р и Q (если задача имеет решение).

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

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

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

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

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

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

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

Для правого берега реки мы будем иметь идентичное множество состояний, которые являются дополнитель­ными к состояниям левого берега. Их матрица V′ явля­ется транспонированной относительно выписанной выше матрицы V. Нетрудно проверить, что для получения матрицы возможных переходов после одного переезда лодки туда и обратно необходимо перемножить V4V′. В общем случае, чтобы получить матрицу переходов после т переездов лодки туда и обратно, нужно вычис­лить (VV')m. А так как наша цель заключается в пере­праве группы на правый берег, то необходимо (VV')m умножить на V. Это даст (VV')mV, и задача свелась к определению числа т двусторонних (т. е. туда и обрат­но) переездов лодки, при котором элемент, стоящий на пересечении строки v1 и столбца v7 матрицы (VV)mV, равен 1, т. е. на левом берегу имеет место переход из состояния (2, 2) в состояние (0, 0) и вся группа оказы­вается на правом берегу. Заметим, что величина элемен­тов произведений VV′, VV'V, VV′VV′ и т. д. указывает на число способов, которыми можно осуществить соот­ветствующий переход. Это число может быть больше 1. Так как наша цель состоит в определении для каждого состояния одного возможного перехода, то все ненуле­вые элементы произведений можно положить разными 1. Оказывается, что исходную задачу можно решить пу­тем т=2 двусторонних переездов и одного (последне­го) одностороннего (т. е. единичный элемент впер­вые появляется на пересечении строки v1 и столбца v7 в матрице (VV')2V). Результаты последовательных вычислений имеют следующий вид: