Comment faire une boîte un libre, dans la situation avec les boîtes sur une table, SWI-Prolog?

Question

Je suis un débutant à prolog et j'essaie de résoudre le problème avec les boîtes comme indiqué dans l'image https://i.stack.imgur.com/BechG.png. Mon code est:

box(a). 
box(b). 
box(c). 
table(t). 
on(a,t). 
on(b,t). 
on(c,a). 
free(b). 
free(c). 

move(X,Z),free(Y):- 
    free(X), 
    free(Z), 
    on(X,Y). 

move(X,t):- 
    free(X), 
    not(on(X,t)). 

move(X,Y):- 
    free(X), 
    free(Y). 

Une seule boîte peut être déplacée à au moment, ce qui signifie que je ne peux pas saisir deux boîtes de la table en même temps. J'ai un problème quand il s'agit de boxer être libre quand je mets cette commande move(c,t),move(b,c),move(a,b). Dans SWI-Prolog il me montre faux où il aurait dû être vrai. Dans tous les autres choix, cela montre vrai et je pense que la boîte ne devient jamais libre.

Answer 1

Vous prenez la mauvaise représentation. Utiliser les faits est bien pour représenter un monde immuable, mais une fois que vous commencez à chercher, vous voulez représenter un état mutable du monde, ce qui est mieux réalisé en variables logiques. De cette façon, vous pouvez exploiter le non-déterminisme de Prolog et revenir en arrière pour trouver une série de mouvements qui vous mènera de l'état de départ à l'état final. Donc, , représentons l'état final dans la base de données, puis les règles pour obtenir les états initial et final dans les variables. Notre représentation d'un état est une série de (trois) on(X,Y) termes.

final(a,b). 
final(b,c). 
final(c,t). 

start(State) :- 
    findall(on(X,Y), on(X,Y), State). 
final(State) :- 
    findall(on(X,Y), final(X,Y), FinalState), 
    same_state(State, FinalState). 

same_state(State1, State2) :- 
    sort(State1, State), 
    sort(State2, State). 

Maintenant, nous devons définir libre en termes d'état. C'est facile: celui du haut et la table sont libres:

free(X, State) :- 
    box(X), 
    \+ member(on(_,X), State). 
free(t, _). 

Maintenant, nous pouvons définir un mouvement comme la suppression d'un on(X,Y) de l'état initial et l'ajout d'une nouvelle:

move(State0, move(X,New), [on(X,New)|Rest]) :- 
    select(on(X,_), State0, Rest), 
    free(X, State0), 
    free(New, State0), 
    X \== New. 

Ensuite, nous doit faire plusieurs mouvements. Nous devons veiller à ne pas entrer dans un état que nous avons vu auparavant:

moves(State, [], _Visited, State). 
moves(State0, [Move|T], Visited, State) :- 
    move(State0, Move, State1), 
    \+ (member(V, Visited), 
     same_state(State1, V) 
     ), 
    moves(State1, T, [State1|Visited], State). 

Et maintenant, nous sommes presque fait:

solve(Moves) :- 
    start(State), 
    moves(State, Moves, [State], Final), 
    final(Final). 

Il y a beaucoup de choses à optimiser. Je vais vous laisser ça. Les deux derniers prédicats montrent l'approche globale de la recherche: commencer au début, faire des mouvements, éviter de revenir à l'ancien état et tester que vous avez trouvé l'état cible. Le tout est montré dans un fichier au https://swish.swi-prolog.org/p/BenchG.pl