2-Кувшин для воды в прологе

Я пытаюсь решить проблему двух кувшинов с водой в swi-prolog: учитывая 2 кувшина емкостью 4 и 3 галлона соответственно, я хочу найти шаги, чтобы получить 2 галлона в кувшине емкостью 4 и 0 в другом.

Я написал программы для этой задачи на C++, используя как bfs, так и dfs: //kartikkukreja.wordpress.com/2013/10/11/проблема с кувшином для воды/. Теперь я пытаюсь решить проблему в прологе. Я совершенно новичок в этом языке, и мой код не завершается.

Вот код, который у меня есть до сих пор:

% state(0, 0) is the initial state
% state(2, 0) is the goal state
% Jugs 1 and 2 have capacities 4 and 3 respectively
% P is a path to the goal state
% C is the list of visited states

solution(P) :-
    path(0, 0, [state(0, 0)], P).

path(2, 0, [state(2, 0)|_], _).

path(0, 2, C, P) :-
not(member(state(2, 0), C)),
path(2, 0, [state(2, 0)|C], R),
P = ['Pour 2 gallons from 3-Gallon jug to 4-gallon.'|R].

path(X, Y, C, P) :-
X < 4,
not(member(state(4, Y), C)),
path(4, Y, [state(4, Y)|C], R),
P = ['Fill the 4-Gallon Jug.'|R].

path(X, Y, C, P) :-
Y < 3,
not(member(state(X, 3), C)),
path(X, 3, [state(X, 3)|C], R),
P = ['Fill the 3-Gallon Jug.'|R].

path(X, Y, C, P) :-
X > 0,
not(member(state(0, Y), C)),
path(0, Y, [state(0, Y)|C], R),
P = ['Empty the 4-Gallon jug on ground.'|R].

path(X, Y, C, P) :-
Y > 0,
not(member(state(X, 0), C)),
path(X, 0, [state(X, 0)|C], R),
P = ['Empty the 3-Gallon jug on ground.'|R].

path(X, Y, C, P) :-
X + Y >= 4,
X < 4,
Y > 0,
NEW_Y = Y - (4 - X),
not(member(state(4, NEW_Y), C)),
path(4, NEW_Y, [state(4, NEW_Y)|C], R),
P = ['Pour water from 3-Gallon jug to 4-gallon until it is full.'|R].

path(X, Y, C, P) :-
X + Y >=3,
X > 0,
Y < 3,
NEW_X = X - (3 - Y),
not(member(state(NEW_X, 3), C)),
path(NEW_X, 3, [state(NEW_X, 3)|C], R),
P = ['Pour water from 4-Gallon jug to 3-gallon until it is full.'|R].

path(X, Y, C, P) :-
X + Y =< 4,
Y > 0,
NEW_X = X + Y,
not(member(state(NEW_X, 0), C)),
path(NEW_X, 0, [state(NEW_X, 0)|C], R),
P = ['Pour all the water from 3-Gallon jug to 4-gallon.'|R].

path(X, Y, C, P) :-
X + Y =< 3,
X > 0,
NEW_Y = X + Y,
not(member(state(0, NEW_Y), C)),
path(0, NEW_Y, [state(0, NEW_Y)|C], R),
P = ['Pour all the water from 4-Gallon jug to 3-gallon.'|R].

Любая помощь приветствуется.


infinite-loop prolog non-termination water-jug-problem
person Kartik Kukreja    schedule 01.11.2013    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

NEW_Y = Y - (4 - X)

с участием

NEW_Y is Y - (4 - X)

OT: также Prolog, как и любой другой язык, выигрывает от факторинга кода: большинство правил path/4 раскрывают один и тот же шаблон, поэтому код может быть более чистым с вспомогательным предикатом: снова, например

path(0, 2, C, P) :-
  not(member(state(2, 0), C)),
  path(2, 0, [state(2, 0)|C], R),
  P = ['Pour 2 gallons from 3-Gallon jug to 4-gallon.'|R].

может быть

path(0, 2, C, ['Pour 2 gallons from 3-Gallon jug to 4-gallon.'|R]) :-
  upd_path(2, 0, C, R).

данный

upd_path(X, Y, C, R).
      not(member(state(X, Y), C)),
      path(X, Y, [state(X, Y)|C], R).

редактировать: еще одна подсказка OT: используйте memberchk/2 вместо member/2. Это более эффективно и может упростить отслеживание выполнения, будучи детерминированным.

редактировать Кроме того, базовый случай рекурсии не закрывает список описаний: попробуйте

path(2, 0, [state(2, 0)|_], []).
person CapelliC    schedule 01.11.2013