Пролог Пересечение реки

Question

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

Проблема указана ниже, как мне решить эту проблему?

Напишите программу Prolog, которая решает проблему со словами ниже. Как часть решения, он должен напечатать все пересечения, с первым в списке.

Тому, Джеку, Биллу и Джиму пришлось пересечь реку, используя каноэ, в котором могли находиться только два человека.
В каждом из трех переходов с левого на правый берег реки на каноэ было по два человека, а на каждом из двух переходов с правого на левый берег на каноэ было по одному человеку. Том не мог грести, когда с ним кто-то был в каноэ.
Джек не мог грести, когда кто-то еще, кроме Билла, был с ним в каноэ. Каждый человек шлепал как минимум по одному переправе.

Это то, что я имею до сих пор, хотя это "работает", но не гарантирует, что все будут веселиться хотя бы один раз.

state(tom(Side),jim(Side),jack(Side),bill(Side),c(Side)).
initial(state(tom(l),jim(l),jack(l),bill(l),c(l))).
final(state(tom(r),jim(r),jack(r),bill(r),c(r))).

canoe(P):-P=p.
canoe(P,C):-P=p,C=c.

bad(state(tom(W),jim(X),jack(Y),bill(Z),c(C))):-
    C=l,(W=c;X=c;Y=c;Z=c).

move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W1),jim(X),jack(Y),bill(Z),c(C1))):-
    ((canoe(W1),W=r,W=C,C1=m);(canoe(W),W1=l,W1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X1),jack(Y),bill(Z),c(C1))):-
    ((canoe(X1),X=r,X=C,C1=m);(canoe(X),X1=l,X1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X),jack(Y1),bill(Z),c(C1))):-
    ((canoe(Y1),Y=r,Y=C,C1=m);(canoe(Y),Y1=l,Y1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X),jack(Y),bill(Z1),c(C1))):-
    ((canoe(Z1),Z=r,Z=C,C1=m);(canoe(Z),Z1=l,Z1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W1),jim(X1),jack(Y),bill(Z),c(C1))):-
    ((canoe(X1,W1),W=l,W=X,W=C,C1=m);
    (canoe(X,W),W1=r,W1=X1,W1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W1),jim(X),jack(Y),bill(Z1),c(C1))):-
    ((canoe(Z1,W1),W=l,W=Z,W=C,C1=m);
    (canoe(Z,W),W1=r,W1=Z1,W1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X1),jack(Y1),bill(Z),c(C1))):-
    ((canoe(X1,Y1),Y=l,Y=X,Y=C,C1=m);
    (canoe(X,Y),Y1=r,Y1=X1,Y1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X1),jack(Y),bill(Z1),c(C1))):-
    ((canoe(Z1,X1);canoe(X1,Z1)),
     Z=l,Z=X,Z=C,C1=m);
    ((canoe(Z,X);canoe(X,Z)),Z1=r,Z1=X1,Z1=C1).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X),jack(Y1),bill(Z1),c(C1))):-
    ((canoe(Y1,Z1);canoe(Z1,Y1)),
     Y=l,Y=Z,Y=C,C1=m);
    ((canoe(Y,Z);canoe(Z,Y)),Y1=r,Y1=Z1,Y1=C1).

find(Path):-initial(S),rez(S,Path).
bkt(State,Path,[Path|State]):-final(State).
bkt(State,Path,Sol):-move(State,Next),not(bad(Next)),
    not(member(Next,Path)),bkt(Next,[Path|Next],Sol).
rez(State,Sol):-bkt(State,[State],Sol).
start:-find(D),writef('%w\n',D).

Answer 1

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

Как уже говорилось в ответах выше, я думаю, что было бы неплохо провести некоторый рефакторинг и попытаться написать более простую, более управляемую модель для этой проблемы. Я имею в виду, что если кто-то попросит вас, например, "быстро модифицировать" ваш код для интеграции, скажем, пятого человека в головоломку, было бы не очень интересно реорганизовать приведенный выше код.

Вы можете начать - это всего лишь один из подходов, чтобы дать вам идею - закодировав конфигурацию из 4 человек в списке, где мы используем 'l' или 'r', чтобы указать, находится ли кто-то слева или справа берега реки. Это дало бы нам начальное состояние примерно так:

% Tom, Jack, Bill, and Jim are all on the left side
[l,l,l,l]

И мы хотим достичь цели государства:

% Tom, Jack, Bill, and Jim are all on the right side
[r,r,r,r]

Это дает нам модель, которую намного легче читать / понимать (imo).

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

transport(StartState,[Persons],EndState)

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

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

% Facts defining a crossing of the river
cross(l,r).
cross(r,l).

% Transport example for Tom
transport([X,Jack,Bill,Jim],[tom],[Y,Jack,Bill,Jim]) :- cross(X,Y).

Как вы можете видеть, мы теперь определили "транспорт" очень простым способом: известно, что Том будет пересекать реку только самостоятельно, поэтому мы используем перекрестный факт, чтобы изменить свое местоположение. (Обратите внимание, что Джек, Билл и Джим - это просто переменные, указывающие либо 'l', либо 'r' в качестве указания, на каком берегу реки находятся эти люди. Поскольку Том только пересекает его самостоятельно, эти переменные не изменятся!). Мы могли бы написать это еще более абстрактно и не подходить конкретно к 'tom', но я стараюсь сделать его простым в этом примере.

Конечно, нам все еще нужно указать, какие пересечения действительны, а какие нет. От вашего вопроса: "На каждом из трех переходов с левого на правый берег реки на каноэ было по два человека, а на каждом из двух переходов с правого на левый берег на каноэ был один человек". Эти условия очень легко можно кодировать с помощью нашего предиката 'transport', поскольку начальное состояние (первый аргумент) сообщает нам, пересекаем ли мы слева направо или наоборот, а наш второй аргумент указывает список людей, которые пересекают. Другими словами, направление пересечения и количество пассажиров уже известны, и кажется немного тривиальным записать эти условия здесь.

Далее: "Джек не мог грести, когда кто-то, кроме Билла, был с ним в каноэ". Опять же, это уже очень легко записать вместе в нашем "транспорте" (обратите внимание, что я использовал подстановочные знаки, чтобы пропустить информацию, которая нас не волнует для этого конкретного условия, но, конечно, это, вероятно, будет отличаться в конечном результате код. Это просто для примера.):

% Transport example for Jack (Persons length = min 1 - max 2)
transport([_,_,_,_],Persons,[_,_,_,_]) :-
    length(Persons,2),
    ( member(jack,Persons) ->
      member(bill,Persons)
    ;
      * other condition(s) *
    ).

% Alternative with pattern matching on Persons
transport([_,_,_,_],[A,B],[_,_,_,_]) :-
    * if jack is A or B, then bill is the other one *    

Другой быстрый пример: "Том не мог грести, когда с ним кто-то был в каноэ".

% Tom cannot peddle in a team of 2
transport([_,_,_,_],Persons,[_,_,_,_]) :-
    length(Persons,2),
    \+ member(tom,Persons).

Как вы, возможно, заметили, теперь мы почти полностью разбили проблему на кусочки, которые очень легко выразить в нашей модели, и мы недалеко от написания реального решателя. Тем не менее, есть достаточно примеров кода, которые можно найти в Интернете, и я не думаю, что нужно разрабатывать больше кода прямо здесь.

Больше вдохновения можно найти в поисках классической головоломки Fox-Goose-Beans/Cabbage.

Всем удачи!