Рекомендуемая литература. Упражнения.
Упражнение 6
Рассмотрите головоломку "миссионеры и каннибалы", схематически представленную на рис. 2.6.
Рис. 2.6. Головоломка "миссионеры и каннибалы"
Условия головоломки следующие.
На левом берегу реки находятся три миссионера и три каннибала. К этому же берегу причалена единственная лодка. На этой лодке нужно переправить всех миссионеров и всех каннибалов на правый берег при условии, что лодка одновременно может перевозить не более двоих, в обратный путь на лодке должен отправиться хотя бы один человек. Таким образом, дозволены следующие варианты шагов (переправ):
- К › одного каннибала с левого берега на правый
- КК › двух каннибалов с левого берега на правый
- МК › одного миссионера и одного каннибала с левого берега на правый
- ММ › двух миссионеров с левого берега на правый
- М › одного миссионера с левого берега на правый
К этому нужно добавить такие же варианты переправы с правого берега на левый. Но есть еще одно обстоятельство, существенно влияющее на весь процесс: если окажется, что каннибалов на любом из берегов больше, чем миссионеров, то несчастных просто съедят. Решение головоломки – это последовательность шагов с учетом описанных ограничений, переводящая систему в заданное конечное состояние.
Конечно, эту головоломку можно решить и простым перебором и испытанием всех возможных состояний, поскольку пространство поиска не так уж велико. На рис. 2.7 показано, как образуется пространство поиска рекурсивным применением дозволенных операторов, причем на графе состояний особо выделены узлы, приводящие к образованию петель, и узлы, соответствующие недозволенным состояниям (когда кто-либо из миссионеров обречен).
Рис. 2.7. Построение пространства поиска в головоломке "миссионеры и каннибалы"