6.9. Задачи изменения состояний системы

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

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

Рассмотрим с иллюстративной целью задачу миссионеров и людоедов [83], помня при этом, что в реальной жизни читатель может столкнуться с задачами более серьезного характера.

Три миссионера и три людоеда подошли к берегу А реки и должны переправиться на противоположный

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

Для решения этой задачи рассмотрим в качестве системы множество миссионеров и людоедов на берегу Пусть обозначают миссионера, людоеда и умеющего грести людоеда соответственно. Тогда система имеет 24 возможности состояния (так как числа находящихся на берегу могут принимать соответственно 4, 3 и 2 различных значения). Из них допустимыми являются следующие 16:

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

Без последнего условия задача решается легко. (Например, последовательность состояний дает решение.) С учетом этого условия задача становится значительно более трудной. Прежде чем двигаться дальше, читатель может поработать

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

Рис. 6.20.

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

Пусть, например, лодка стоит у берега а система находится в состоянии Из рис. 6.20 мы видим, что система может перейти в состояние или через состояние (заметим, что при этом лодка снова окажется у берега ). Поэтому соединяем ребра и На рис. 6.21 показаны все такие ребра (включая ориентированные ребра, ведущие в конечное состояние 0, которые соответствуют последнему переезду без возвращения лодки на берег ). Для вспомогательного графа рис. 6.21 задача заключается в следующем: определить цепь из в 0. Легко видеть, что такая цепь существует. Например, является искомой цепью. Добавляя (в скобках) промежуточные состояния, получим следующее

решение для первоначального графа рис. 6.20: Это решение показано на рис. 6.22.

Рис. 6.21.

Рис. 6.22.

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

Упражнения

(см. скан)

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

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

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

Рис. 6.24.

При этом, в частности, мы найдем и цепь, соединяющую (если задача имеет решение).

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

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

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