Studiuję Prolog przy użyciu książki Ivana Bratko: Programowanie dla sztucznej inteligencji i znajduję pewne trudności z wdrożeniem ostatniej części proponowanego ćwiczenia

Ćwiczenie to program, który wykorzystuje wykresy do decydowania o tym, jak przesuwać bloki i układać je w kolejności.

To jest obraz związany z tym, co program musi zrobić:

Jak widać na poprzednim obrazie, bloki A, B, C można przesuwać za pomocą wielu dopuszczalnych ruchów, które są:

Blok można przesunąć tylko wtedy, gdy znajduje się na szczycie stosu

Blok można przesunąć po ziemi (na pustym stosie)

Blok można przesuwać nad innym blokiem (na górze innego stosu, który zawiera inne bloki)

Zatem te dopuszczalne ruchy wywołują wykres możliwych przejść między jednym stanem a innym stanem na wykresie, coś takiego:

Tak więc, jak możesz zobaczyć na poprzednim wykresie, mogę przedstawić sytuację używając listy 3 podlist.

Każda podlista przedstawia stos, w którym mogę umieścić bloki zgodnie z poprzednimi ograniczeniami

Na przykład sytuacja centralnego węzła poprzedniego wykresu może być reprezentowana przez:

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

Ponieważ każdy stos zawiera pojedynczy blok.

Sytuacja reprezentowana przez węzeł w lewym górnym rogu, gdzie ułożyłem jeden poniżej innych bloków C, A, B, może być reprezentowana przez:

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

Ok, więc mój program jest następujący:

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).

W tych ostatnich dniach głęboko go przestudiowałem i rozumiem, jak to działa.

Zasadniczos / 3 predykat jest mójfunkcja następcys(CurrentState, SuccessorState) który oblicza legalny ruch odCurrentState doSuccessorState.

Ten predykat działa dobrze, w rzeczywistości, jeśli uruchomię następujące zapytanie:

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

Zdobywam to[[b, c], [a], []] jeststan następcy dla państwa[[ABC],[],[]] i to jest dobre, ponieważ przeniosłema zablokuj od góry pierwszego stosu na szczycie drugiego stosu (który był nieważny) i jest to całkowicie legalny ruch.

Ok, dalej mamgoal/1 predykat, który mówi, kiedy osiągnęłam stan końcowy (kiedy obliczenie musi się zatrzymać):

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

Mówi, że sytuacja (specyficzna konfiguracja listy stosów) jest sytuacją bramkową, jeśli na liście powiązanych stosów znajduje się stos, który jest listą [a, b, c].

Tak więc następujące sytuacje są sytuacjami bramkowymi:

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

Ok teraz mój problem jest następujący: muszę zaimplementowaćsolve/2 predykat taki jak ten:

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

który zaczyna się od sytuacji, w której przeszedł (w tym przypadku lista stosów, w których znajdują się wszystkie bloki w pierwszym stosiec na ziemi,b w środku ia na górze) i dochodzi do sytuacji bramkowej.

Nie wiem dokładnie, co mam robić i jak muszę to rozwiązać (niestety nie mam nauczyciela)

Próbowałem zainspirować się, patrząc na tę wersję problemu z 8 królowymi, która wykorzystuje podobną technikę programowania (w której mam cel do spełnienia i predykat rozwiązania):

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).