Я изучаю Пролог, используя книгу Ивана Братко: Программирование для искусственного интеллекта, и нахожу некоторые трудности в реализации заключительной части предложенного упражнения.

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

Это изображение, связанное с тем, что должна делать программа:

Как вы можете видеть на предыдущем изображении, блоки A, B, C можно перемещать, используя несколько допустимых перемещений:

Блок может быть перемещен, только если он находится на вершине стека

Блок может быть перемещен на земле (в пустом стеке)

Блок может быть перемещен поверх другого блока (в верхней части другого стека, который содержит некоторые другие блоки)

Таким образом, эти допустимые шаги индуцируют график возможных переходов между одним состоянием и другим состоянием в графе, что-то вроде этого:

Итак, как вы можете видеть на предыдущем графике, я могу представить ситуацию, используя список из 3 подсписков.

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

Например, ситуация с центральным узлом предыдущего графа может быть представлена как:

[[A], [B], [C]]

Потому что каждый стек содержит один блок.

Ситуация, представленная узлом в верхнем левом углу, где я сложил один ниже других блоков C, A, B, может быть представлена как:

[[C,A,B], [], []]

Итак, моя программа следующая:

del(X, [X|Tail], Tail).

del(X, [Y|Tail], [Y|Tail1]) :- del(X, Tail, Tail1).

/* s(CurrentState, SuccessorState): Predicate that calculate a legal move from
                                    the CurrentState to the SuccessorState:
*/
s(Stacks, [Stack1, [Top1|Stack2] | OtherStacks]) :- 
                                     del( [Top1|Stack1], Stacks, Stacks1),
                                     del( Stack2, Stacks1, OtherStacks).

goal(Situation) :- member([a,b,c], Situation).

В эти последние дни я глубоко изучил это, и я понимаю, как это работает.

Существеннос / 3 мой предикатфункция преемникаs(CurrentState, SuccessorState) который рассчитывает законный ход отCurrentState к.SuccessorState

Этот предикат работает хорошо, на самом деле, если я запускаю следующий запрос:

[debug]  ?- s([[a,b,c],[],[]],R).
R = [[b, c], [a], []] 

Я получаю это[[Ь, с], [а], []] этогосударство-преемник для государства[[А, Ь, с], [], []] и это хорошо, потому что я переместилa блок сверху первого стека сверху второго стека (это было недействительно), и это совершенно законный ход.

Хорошо, у меня естьgoal/1 Предикат, который говорит, когда я достиг конечного состояния (когда вычисления должны быть остановлены):

goal(Situation) :- member([a,b,c], Situation).

Это говорит о том, что ситуация (конкретная конфигурация списка стеков) является целевой ситуацией, если в списке связанных стеков есть стек, который является списком [a, b, c].

Таким образом, следующие ситуации являются целевыми ситуациями:

[[a,b,c],[],[]]
[[], [a,b,c],[]]
[[],[], [a,b,c]]

Хорошо, теперь моя проблема заключается в следующем: я должен реализоватьsolve/2 Предикат как это:

solve([[c,a,b],[],[]], Situation)

который начинается с пройденной ситуации (в этом случае список стеков, которые имеют все блоки в первом стеке сc на земле,b в середине иa на вершине) и прибывает в целевую ситуацию.

Я нене знаю точно, что я должен делать и как я должен это решить (к сожалению, у меня нет учителя)

Я пытался вдохновить себя, глядя на эту версию проблемы 8 ферзей, которая использует похожую технику программирования (в которой у меня есть цель удовлетворить и предикат решения):

s(Queens, [Queen|Queens]) :- member(Queen, [1,2,3,4,5,6,7,8]),
                             noattack(Queen, Queens, 1).

goal([_,_,_,_,_,_,_,_]).

noattack(_,[],_) :- !.
noattack(Y,[Y1|Ylist],Xdist) :-   Y =\= Y1,
                                  Y1-Y =\= Xdist,
                                  Y-Y1 =\= Xdist,
                                  Dist1 is Xdist + 1,
                                  noattack(Y,Ylist,Dist1).

solve(N,[N]) :- goal(N).      % sample call: solve([], X).

solve(N, [N|Sol1]) :- s(N,N1),
                      solve(N1,Sol1).