---

Тут виден также вспомогательный предикат, возвращающий противоположный берег (west-

>east и наоборот).
В ходе поиска решения программа будет перебирать состояния, для каждого из которых надо проверять допустимо ли оно. Допустимость - это не только Миссионеров >= Людоедов, ведь если миссионеров нет - то людоедов на берегу можно оставить сколько угодно. Это также оформлено в виде отдельного правила:


можно_оставить(берег(Миссионеров, Людоедов)):-

% если миссионеров больше Миссионеров >= Людоедов;

% или если некого есть Миссионеров is 0.



Сама по себе смена состояний - это не так просто ведь:

• 
  исходя из состояния лодки и берега надо понять кто поплывет назад;
  
• 
  исходя из состояния лодки и берега надо определить кто там на противоположном берегу.
  

Поэтому предикат поиска следующего состояния разбит на 2 части - разгрузку/загрузку, которые выполняются в рамках текущего берега, а также - переправы (при этом меняется берег):


следующее_состояние(Состояние, Следующее):- разгрузка_загрузка(Состояние, СостояниеПослеПерегрузки), переправа(СостояниеПослеПерегрузки, Следующее).



Цель разгрузки и загрузки - сформировать лодку для отплытия назад из тех людей, что есть в лодке и на текущем берегу:


разгрузка_загрузка( state(БерегЛодки,

берег(МиссионеровБерег, ЛюдоедовБерег), лодка(МиссионеровЛодка, ЛюдоедовЛодка)),
state(БерегЛодки,

берег(МиссионеровБерегПосле, ЛюдоедовБерегПосле), лодка(МиссионеровЛодкаПосле, ЛюдоедовЛодкаПосле))):-
% выгрузка (всех сложить):

ВсегоМиссионеров is МиссионеровБерег + МиссионеровЛодка, ВсегоЛюдоедов is ЛюдоедовБерег + ЛюдоедовЛодка,
% выбрать кто плывет назад: between(0, 2, МиссионеровЛодкаПосле),

МиссионеровЛодкаПосле =< ВсегоМиссионеров,
between(0, 2, ЛюдоедовЛодкаПосле), ЛюдоедовЛодкаПосле =< ВсегоЛюдоедов,
% проверка емкости лодки

---

Назад поплывет 0, 1 или 2 миссионера, а также 0, 1 или 2 людоеда. Для перебора их количества используется встроенная функция between. Она работает так:


% Вызов:

?- between(3, 7, X).

% Результаты:

X = 3;

X = 4;

X = 5;

X = 6;

X = 7.



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


переправа(state(БерегЛодки, берег(МиссионеровБерег, ЛюдоедовБерег), лодка(МиссионеровЛодка, ЛюдоедовЛодка)),
state(ДругойБерегЛодки, берег(МиссионеровДругойБерег, ЛюдоедовДругойБерег), лодка(МиссионеровЛодка, ЛюдоедовЛодка))):-
другой_берег(БерегЛодки, ДругойБерегЛодки), расчет_друго_берега(

берег(МиссионеровБерег, ЛюдоедовБерег), лодка(МиссионеровЛодка, ЛюдоедовЛодка), берег(МиссионеровДругойБерег, ЛюдоедовДругойБерег)

).



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


% поиск в глубину dfs(Состояние, _, Path):-

Состояние = state(west,

берег(МиссионеровБерег, ЛюдоедовБерег), лодка(МиссионеровЛодка, ЛюдоедовЛодка)),

ВсегоМиссионеров is МиссионеровБерег + МиссионеровЛодка, ВсегоЛюдоедов is ЛюдоедовБерег + ЛюдоедовЛодка,

---

Это правило состоит из двух частей. Первая часть проверяет окончание переправы. Такое случится если ложка окажется на правом берегу west и если собрать лодку и текущий берег - то на них окажутся все 3 людоеда и все 3 миссионера.
Такой случай описан отдельно, так как если из этого состояния выполнить генерацию следующих - то программа обязательно сформирует назад НЕПУСТУЮ лодку, а значит - на берегу будут не все люди.
Если же текущее состояние не конечное - то на его основе формируется следующее состояние и программа ищет из него.
Чтобы один людоед не плавал вечно с одного берега на другой - программа хранит список уже посещенных состояний (передается в dfs в виде второго аргумента - списка).
Вызывать функцию надо так:


CurrentState = state(east, берег(3, 3), лодка(0, 0)), dfs(CurrentState, [], Path).



Результат ее работы:

---

Смотрите также файлы

• Организация высшего образования центросоюза российской федерации российский университет кооперации поволжский кооперативный институт.doc

• Отчет по лабораторной работе 1 Программирование линейного вычислительного процесса.doc

• Білім беру йымы (балабаша шаын орталы, мектепалды сыныбы).docx

• До этого времени в течение почти 500 лет вт сводилась к простейшим устройствам для выполнения арифметических операций над числами.docx

• Адиабатический, или адиабатный1 процесс от др греч. непроходимый.docx