tpProlog/anerouge/anerougeEtudiants.pl

   1 /* librairie à intégrer */
   2
   3 :-use_module(library(assoc)).
   4
   5
   6 /*  successeurs_liste(L,Sl) est vrai si Sl est la liste
   7     de tous les successeurs de L*/
   8 successeurs_liste(L,Sl):-
   9     maplist(successeurs,L,Lp),
  10     flatten(Lp,Lpp),
  11     list_to_assoc(Lpp,A),
  12     assoc_to_list(A,Sl).
  13
  14
  15 /*  list_minus(L1,L2,L3) est vrai si
  16     L3 est la liste de tous les éléments Conf-_ de L1 dont
  17     Conf n appartient pas à L2 */
  18 list_minus([],_,[]).
  19 list_minus([Conf-_|L1],L2,Res):-
  20     member(Conf,L2),!,
  21     list_minus(L1,L2,Res).
  22 list_minus([El|L1],L2,[El|Res]):-
  23     list_minus(L1,L2,Res).
  24
  25 filtre_conf(X-_,X).
  26
  27 /* but(L,Ch) est vrai si L contient une configuration
  28     finale et si Ch est le chemin qui a mené a cette configuration */
  29 but([Conf-Chemin|_],Chemin):-final(Conf),!.
  30 but([_|L],Chemin):-but(L,Chemin).
  31
  32
  33
  34 /* largeur(Atraiter,Visites,C,Res) est vrai si
  35     Atraiter est la liste des configurations-chemins qu il reste à visiter
  36     Visites est la liste des configurations déjà visités
  37     C est l entier représentant la profondeur de recherche
  38     Res est le chemin menant à une configuration finale */
  39 largeur(Atraiter,_,_,Res):-
  40     but(Atraiter,Res),!.
  41 largeur(Atraiter,Visites,C,Res):-
  42     Cp is C+1,
  43     writef("boucle %d \n",[C]),
  44     maplist(filtre_conf,Atraiter,V1),
  45     append(V1,Visites,Omis),
  46     successeurs_liste(Atraiter,Succ),
  47     list_minus(Succ,Omis,Atraiter2),
  48     largeur(Atraiter2,Omis,Cp,Res).
  49
  50
  51
  52 resoud(_):-
  53     get_time(T0),
  54     init(X),
  55     largeur([X-[]],[],0,Res),
  56     writeln(Res),
  57     get_time(T1),
  58     DT1 is T1 - T0,
  59     writef('Duree : % \n',[DT1]).
  60
  61