123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263 |
- /* Fichier du probleme.
-
- Doit contenir au moins 4 predicats qui seront utilises par A*
-
- etat_initial(I) % definit l'etat initial
-
- etat_final(F) % definit l'etat final
-
- rule(Rule_Name, Rule_Cost, Before_State, After_State) % règles applicables
-
- heuristique(Current_State, Hval) % calcul de l'heuristique
-
-
- Les autres prédicats sont spécifiques au Taquin.
- */
-
-
- %:- lib(listut). % Laisser cette directive en commentaire si vous utilisez Swi-Prolog
-
- % Sinon décommentez la ligne si vous utilisez ECLiPSe Prolog :
- % -> permet de disposer du predicat nth1(N, List, E)
- % -> permet de disposer du predicat sumlist(List, S)
- % (qui sont predefinis en Swi-Prolog)
-
-
- %***************************
- %DESCRIPTION DU JEU DU TAKIN
- %***************************
-
- %********************
- % ETAT INITIAL DU JEU
- %********************
- % format : initial_state(+State) ou State est une matrice (liste de listes)
-
-
- initial_state([ [b, h, c], % C'EST L'EXEMPLE PRIS EN COURS
- [a, f, d], %
- [g,vide,e] ]). % h1=4, h2=5, f*=5
-
-
-
- % AUTRES EXEMPLES POUR LES TESTS DE A*
-
- /*
- initial_state([ [ a, b, c],
- [ g, h, d],
- [vide,f, e] ]). % h2=2, f*=2
-
- initial_state([ [b, c, d],
- [a,vide,g],
- [f, h, e] ]). % h2=10 f*=10
-
- initial_state([ [f, g, a],
- [h,vide,b],
- [d, c, e] ]). % h2=16, f*=20
-
- initial_state([ [e, f, g],
- [d,vide,h],
- [c, b, a] ]). % h2=24, f*=30
-
- initial_state([ [a, b, c],
- [g,vide,d],
- [h, f, e]]). % etat non connexe avec l'etat final (PAS DE SOLUTION)
- */
-
-
- %******************
- % ETAT FINAL DU JEU
- %******************
- % format : final_state(+State) ou State est une matrice (liste de listes)
-
- final_state([[a, b, c],
- [h,vide, d],
- [g, f, e]]).
-
-
- %********************
- % AFFICHAGE D UN ETAT
- %********************
- % format : write_state(?State) ou State est une liste de lignes a afficher
-
- write_state([]).
- write_state([Line|Rest]) :-
- writeln(Line),
- write_state(Rest).
-
-
- %**********************************************
- % REGLES DE DEPLACEMENT (up, down, left, right)
- %**********************************************
- % format : rule(+Rule_Name, ?Rule_Cost, +Current_State, ?Next_State)
-
- rule(up, 1, S1, S2) :-
- vertical_permutation(_X,vide,S1,S2).
-
- rule(down, 1, S1, S2) :-
- vertical_permutation(vide,_X,S1,S2).
-
- rule(left, 1, S1, S2) :-
- horizontal_permutation(_X,vide,S1,S2).
-
- rule(right,1, S1, S2) :-
- horizontal_permutation(vide,_X,S1,S2).
-
- find_all_next_state_from_U0(NextState) :-
- initial_state(Ini),
- rule(_, _, Ini, NextState).
-
- find_all_action_next_state_from_U0(Action, NextState) :-
- initial_state(Ini),
- rule(Action, _, Ini, NextState).
-
- find_all_next_state_from_U0_list(L) :-
- findall(NextState, find_all_next_state_from_U0(NextState), L).
-
- find_all_action_next_state_from_U0_list(L) :-
- findall([Action, NextState], find_all_action_next_state_from_U0(Action, NextState), L).
-
-
-
- find_all_action_next_state(U, Action, NextState) :-
- rule(Action, _, U, NextState).
-
- find_all_action_next_state_list(U, L) :-
- findall([Action, NextState], find_all_action_next_state(Action, NextState), L).
-
- %***********************
- % Deplacement horizontal
- %***********************
- % format : horizontal_permutation(?Piece1,?Piece2,+Current_State, ?Next_State)
-
- horizontal_permutation(X,Y,S1,S2) :-
- append(Above,[Line1|Rest], S1),
- exchange(X,Y,Line1,Line2),
- append(Above,[Line2|Rest], S2).
-
- %***********************************************
- % Echange de 2 objets consecutifs dans une liste
- %***********************************************
-
- exchange(X,Y,[X,Y|List], [Y,X|List]).
- exchange(X,Y,[Z|List1], [Z|List2] ):-
- exchange(X,Y,List1,List2).
-
- %*********************
- % Deplacement vertical
- %*********************
-
- vertical_permutation(X,Y,S1,S2) :-
- append(Above, [Line1,Line2|Below], S1), % decompose S1
- delete(N,X,Line1,Rest1), % enleve X en position N a Line1, donne Rest1
- delete(N,Y,Line2,Rest2), % enleve Y en position N a Line2, donne Rest2
- delete(N,Y,Line3,Rest1), % insere Y en position N dans Rest1 donne Line3
- delete(N,X,Line4,Rest2), % insere X en position N dans Rest2 donne Line4
- append(Above, [Line3,Line4|Below], S2). % recompose S2
-
- %***********************************************************************
- % Retrait d une occurrence X en position N dans une liste L (resultat R)
- %***********************************************************************
- % use case 1 : delete(?N,?X,+L,?R)
- % use case 2 : delete(?N,?X,?L,+R)
-
- delete(1,X,[X|L], L).
- delete(N,X,[Y|L], [Y|R]) :-
- delete(N1,X,L,R),
- N is N1 + 1.
-
-
-
- %*******************
- % PARTIE A COMPLETER
- %*******************
-
- %*******************************************************************
- % Coordonnees X(colonne),Y(Ligne) d une piece P dans une situation U
- %*******************************************************************
- % format : coordonnees(?Coord, +Matrice, ?Element)
- % Définit la relation entre des coordonnees [Ligne, Colonne] et un element de la matrice
- /*
- Exemples
-
- ?- coordonnees(Coord, [[a,b,c],[d,e,f]], e). % quelles sont les coordonnees de e ?
- Coord = [2,2]
- yes
-
- ?- coordonnees([2,3], [[a,b,c],[d,e,f]], P). % qui a les coordonnees [2,3] ?
- P=f
- yes
- */
-
- wellplaced(U, Lettre) :-
- nth1(L, U, Ligne),
- nth1(C, Ligne, Lettre),
- final_state(Uf),
- nth1(L, Uf, Lign2),
- nth1(C, Lign2, Lettre).
-
-
- coordonnees([L,C], Mat, Elt) :-
- nth1(L, Mat, Ligne),
- nth1(C, Ligne, Elt).
-
-
- %*************
- % HEURISTIQUES
- %*************
-
- heuristique(U,H) :-
- % heuristique1(U, H). % au debut on utilise l'heuristique 1
- heuristique2(U, H). % ensuite utilisez plutot l'heuristique 2
-
-
- %****************
- %HEURISTIQUE no 1
- %****************
- % Nombre de pieces mal placees dans l'etat courant U
- % par rapport a l'etat final F
-
-
- % Suggestions : définir d'abord le prédicat coordonnees(Piece,Etat,Lig,Col) qui associe à une pièce présente dans Etat
- % ses coordonnees (Lig= numero de ligne, Col= numero de Colonne)
-
- % Definir ensuite le predicat malplace(P,U,F) qui est vrai si les coordonnes de P dans U et dans F sont differentes.
- % On peut également comparer les pieces qui se trouvent aux mêmes coordonnees dans U et dans H et voir s'il sagit de la
- % même piece.
-
- % Definir enfin l'heuristique qui détermine toutes les pièces mal placées (voir prédicat findall)
- % et les compte (voir prédicat length)
- badplaced(U, Lettre) :-
- coordonnees(Coor, U, Lettre),
- Lettre \= vide,
- final_state(Uf),
- coordonnees(Coor, Uf, Lettre2),
- Lettre \= Lettre2.
-
- heuristique1(U, H) :-
- findall(Lettre, badplaced(U, Lettre), L),
- length(L, H). %********
- % A FAIRE
- %********
-
-
- %****************
- %HEURISTIQUE no 2
- %****************
-
- % Somme des distances de Manhattan à parcourir par chaque piece
- % entre sa position courante et sa positon dans l'etat final
- get_manhattan_cost(U, Lettre, Cost) :-
- final_state(Uf),
- coordonnees([L, C], U, Lettre),
- coordonnees([L2, C2], Uf, Lettre),
- Lettre \= vide,
- Cost is abs(L - L2) + abs(C - C2).
-
- heuristique2(U, H) :-
- findall(Cost, get_manhattan_cost(U, _Lettre, Cost), L),
- sumlist(L, H).
- %********
- % A FAIRE
- %********
-
-
|