%******************************************************************************* % AETOILE %******************************************************************************* /* Rappels sur l'algorithme - structures de donnees principales = 2 ensembles : P (etat pendants) et Q (etats clos) - P est dedouble en 2 arbres binaires de recherche equilibres (AVL) : Pf et Pu Pf est l'ensemble des etats pendants (pending states), ordonnes selon f croissante (h croissante en cas d'egalite de f). Il permet de trouver rapidement le prochain etat a developper (celui qui a f(U) minimum). Pu est le meme ensemble mais ordonne lexicographiquement (selon la donnee de l'etat). Il permet de retrouver facilement n'importe quel etat pendant On gere les 2 ensembles de fa�on synchronisee : chaque fois qu'on modifie (ajout ou retrait d'un etat dans Pf) on fait la meme chose dans Pu. Q est l'ensemble des etats deja developpes. Comme Pu, il permet de retrouver facilement un etat par la donnee de sa situation. Q est modelise par un seul arbre binaire de recherche equilibre. Predicat principal de l'algorithme : aetoile(Pf,Pu,Q) - reussit si Pf est vide ou bien contient un etat minimum terminal - sinon on prend un etat minimum U, on genere chaque successeur S et les valeurs g(S) et h(S) et pour chacun si S appartient a Q, on l'oublie si S appartient a Ps (etat deja rencontre), on compare g(S)+h(S) avec la valeur deja calculee pour f(S) si g(S)+h(S) < f(S) on reclasse S dans Pf avec les nouvelles valeurs g et f sinon on ne touche pas a Pf si S est entierement nouveau on l'insere dans Pf et dans Ps - appelle recursivement etoile avec les nouvelles valeurs NewPF, NewPs, NewQs */ %******************************************************************************* :- ['avl.pl']. % predicats pour gerer des arbres bin. de recherche :- ['taquin.pl']. % predicats definissant le systeme a etudier %******************************************************************************* main() :- % initialisations Pf, Pu et Q % lancement de Aetoile initial_state(Init), heuristique(Init,H), empty(Pf), empty(Pu), empty(Qs), insert([[H, H, 0], Init], Pf, Pf_new), insert([Init, [H, H, 0], nil, nil], Pu, Pu_new), aetoile(Pf_new,Pu_new,Qs). %******** % A FAIRE %******** %******************************************************************************* % aetoile([],[], _):- write('PAS de SOLUTION : L_ETAT FINAL N_EST PAS ATTEIGNABLE !'), !. aetoile(Pf, Pu, Qs):- suppress_min([[F,H,G], U], Pf, Pf_tmp), suppress([U,[F,H,G], Pere, Action], Pu, Pu_tmp), Noeud = [U,[F,H,G], Pere, Action], % write('Noeud min : '), % writeln(Noeud), (final_state(U) -> insert(Noeud, Qs, Qs_new), affichage_solution(U, Qs_new) ; expand(Noeud, G, SList), loop_successor(SList, Pf_tmp, Pu_tmp, Qs, Pf_new, Pu_new), insert(Noeud, Qs, Qs_new), /*write('PF height: '), height(Pf_tmp,PFSize), writeln(PFSize), write('PU :'), put_flat(Pu_new), write('\n'), write('QS : '), put_flat(Qs_new),*/ aetoile(Pf_new, Pu_new, Qs_new) % Niter is Niter1+1, % write('iteration n°'), % writeln(Niter) ). %******************************************************************************* affichage_solution(U, Qs):- belongs([U, _Val, Pere, Action], Qs), get_solution(Pere, Tmp), write('\n'), writeln('\nSolution : '), print_l( [[U, Action] |Tmp] ). get_solution(nil,[]):- !. get_solution([U,_Val,Pere, Action], [ [U, Action] | Rest]) :- get_solution(Pere,Rest). print_l([]). print_l([[ [A,B,C], Action] |T]):- print_l(T), write('action : '), writeln(Action), writeln(A), writeln(B), writeln(C), write('\n'). expand([U, Val, P, A], GU, SList):- Noeud = [U, Val, P, A], findall([S,[F,H,G], Noeud , Action], (rule(Action,C,U,S), heuristique(S, H), G is GU+C, F is H+G), SList). loop_successor([],Pf,Pu,_,Pf,Pu). loop_successor([[S,[F,H,G], Pere, Action]| TailS_eval] , Pf , Pu, Qs, Pf_new, Pu_new) :- ( belongs([S, _, _, _], Qs) -> loop_successor(TailS_eval, Pf, Pu, Qs, Pf_new, Pu_new) ; ( belongs( [S, [OldF, _, _], _, _ ], Pu) -> ( F < OldF -> %writeln('dans F <'), maj([S, [OldF, OldH, OldG], _, _], [S,[F,H,G], Pere, Action], Pu, Pu_tmp), maj([[OldF, OldH, OldG], S], [[F,H,G], S], Pf, Pf_tmp) ; %writeln('dans F >'), Pf_tmp = Pf, Pu_tmp = Pu ) ; %writeln('hors belongs'), insert([[F,H,G], S], Pf , Pf_tmp), insert([S,[F,H,G], Pere, Action], Pu, Pu_tmp) ), loop_successor(TailS_eval, Pf_tmp, Pu_tmp, Qs, Pf_new, Pu_new) ). maj(EltDel, EltAdd, AvlAvant, AvlApres):- suppress(EltDel,AvlAvant, AvlTmp), insert(EltAdd, AvlTmp, AvlApres). %******* % TESTS %******* get_pf(1, [[5,5,0], [[b, h, c], [a, f, d], [g,vide,e]] ]). get_pf(2, [[7,6,1],[[b,h,c],[a,f,d],[vide,g,e]]] ). get_current_pu(0, [[H,H,0], State]) :- initial_state(State), heuristique(State,H). get_pu(1, [[[b, h, c], [a, f, d], [g,vide,e]],[5,5,0], nil, nil]). get_pu(2, [[[b,h,c],[a,f,d],[vide,g,e]],[7,6,1],[[[b,h,c],[a,f,d],[g,vide,e]],[5,5,0],nil, nil]]). get_slist_initial_state(SList) :- SList = [ [ [[b, h, c], [a, vide, d], [g, f, e]], [5,4,1], [ [[b, h, c], [a, f, d], [g, vide, e]], [5,5,0], nil, nil], up], [ [[b, h, c], [a, f, d], [vide, g, e]], [7,6,1], [ [[b, h, c], [a, f, d], [g, vide, e]], [5,5,0], nil, nil], left], [ [[b, h, c], [a, f, d], [g, e, vide]], [7,6,1], [ [[b, h, c], [a, f, d], [g, vide, e]], [5,5,0], nil, nil], right] ]. get_pf(Nb,Pos, X) :- getPu(Nb, [[F,_,_], U]), getPf(Nb, Pere), rule(Pos, 1, U, S), heuristique(S,Hn), Fn is Hn+F, X = [S,[Fn,Hn,F],Pere]. get_pf_up(Nb, X) :- getPf(Nb,up, X). get_pf_left(Nb, X) :- getPf(Nb,left, X). get_pf_right(Nb, X) :- getPf(Nb,right, X). get_pf_down(Nb, X):- getPf(Nb, down, X). maj_test(1, A):- getPfUp(EltPfUp), getPfLeft(EltPfLeft), getPfRight(EltPfRight), %******insert 3U from initial_state******* insert(EltPfUp, nil, Pf), insert(EltPfLeft, Pf, Pf2), insert(EltPfRight, Pf2, Pf3), %******Replace LeftU with initial_state**** getPf(1, EltPf), maj(EltPfLeft, EltPf, Pf3, A). insert_test(1, A) :- getPfUp(2,EltPfUp), getPfRight(2,EltPfRight), insert(EltPfUp, nil, Pf2), insert(EltPfRight, Pf2, A), belongs(EltPfRight, A). test_pred_expand() :- get_pf(1,[[_F, _H, G], U]), expand(U, G, SList), get_slist_initial_state(SList).