[Prolog] débutant..

débutant.. [Prolog] - Divers - Programmation

Marsh Posté le 08-04-2007 à 12:45:45    

Salut!
 
j'ai un petit probleme prolog pas bien compliqué je pense mais je voie pas trop comment le résoudre  
 
C'est par rapport à ce prédicat :  
 

Code :
  1. deplacementdroiteinutile(X,Y) :- vision(A,B) , A is (X+1) , vue(A,B) , voisin(A,B,C,D) , vue(C,D).


 
En fait à partir d'une case de coordonnée X et Y je récupere les voisins à droite de cette case ( (X,Y+1) , (X,Y) , (X,Y-1) )  
 
J'en ai donc au maximums trois et à partir de ces trois nouvelles cases je récupère la liste des voisins de ces trois cases grace au prédicat voisin ( je suis sûr qu'il fonctionne je l'ai testé) et je voudrai que TOUS ces voisins soient vus (grace au prédicat vue(C,D) )  
 
Mon problème c'est que le prédicat déplacementdroiteinutile est vrai si il y a au moins un vue(C,D) vrai. or je voudrai qu'ils soient tous vrai mais je ne voie pas comment faire..
 
merci d'avance :mrgreen:


Message édité par guiguivts le 08-04-2007 à 12:46:16
Reply

Marsh Posté le 08-04-2007 à 12:45:45   

Reply

Marsh Posté le 08-04-2007 à 13:08:46    

En fait pour réduire le problème  
 
Pour ce prédicat :  
 

Code :
  1. toto :- case(X,Y) , paire(X).


 
Il me sort vrai car il existe une case de coordonnée X paire mais comment faire si je veux que toutes les cases aient X paire ?

Message cité 1 fois
Message édité par guiguivts le 08-04-2007 à 13:13:02
Reply

Marsh Posté le 08-04-2007 à 16:24:56    

guiguivts a écrit :

En fait pour réduire le problème  
 
Pour ce prédicat :  
 

Code :
  1. toto :- case(X,Y) , paire(X).


 
Il me sort vrai car il existe une case de coordonnée X paire mais comment faire si je veux que toutes les cases aient X paire ?

essaie :

Code :
  1. toto :-
  2.   forall(case(X,_), paire(X)).

Valalble avec SWI-Prolog.


Message édité par Trap D le 08-04-2007 à 16:25:32
Reply

Marsh Posté le 08-04-2007 à 18:17:47    

J'ai trouvé un moyen détourner mais ça peut toujours servir merci ;)

Reply

Marsh Posté le 09-04-2007 à 12:07:39    

Salut , toujours question de débutant :  
 
J'ai un damier de créer avec des cases des murs etc..
 
Je cherche à faire un prédicat me disant s'il y a un chemin entre une case et une autre :  
 
j'ai fait ça :  
 
existechemin(X,Y,A,B) :- voisin(X,Y,A,B).
existechemin(X,Y,A,B) :- existechemin(C,D,A,B) , voisin(X,Y,C,D).  
 
L'ennui c'est que bien sûr ça boucle.. je voie bien d'ou ça vient et comment corriger le problème en utilisant des listes. (enfin je pense..) mais est ce que c'est possible sans utiliser de listes ?  

Reply

Marsh Posté le 09-04-2007 à 16:01:56    

On touche aux graphes là, et sans les listes, je ne vois pas trop comment t'en sortir.

Reply

Marsh Posté le 09-04-2007 à 19:05:26    

Oki j'ai trouvé des tutos intéressants je vais donc devoir me les taper :(  
 
J'ai déjà vu djikstra et autres en cours mais de là à les faire en prolog :( berk!

Message cité 1 fois
Reply

Marsh Posté le 09-04-2007 à 21:53:26    

guiguivts a écrit :

Oki j'ai trouvé des tutos intéressants je vais donc devoir me les taper :(  
 
J'ai déjà vu djikstra et autres en cours mais de là à les faire en prolog :( berk!

Pas berk  :??:  
Je t'invite à y réfléchir sérieusement, tu auras beaucoup à y gagner.
Cette adressepour te montrer ce qu'on peut faire

Reply

Marsh Posté le 11-04-2007 à 13:55:09    

J'ai commencer à voir comment tester si un chemin existait en utilisant les listes mais je bloque. j'ai ça comme prédicat :  
 

Code :
  1. existechemin(X,Y,X,Y,_).
  3. existechemin(X,Y,A,B,_) :- voisin(X,Y,A,B),!.
  5. existechemin(X,Y,A,B,L) :- voisin(X,Y,C,D) , not(membre(case(C,D),L)) ,existechemin(C,D,A,B,[case(X,Y)|L]).
  9. membre(case(X,Y),[case(X,Y)|_]).
  11. membre(case(X,Y),[_|S]) :- membre(case(X,Y),S).


 
mais bien sûr ça ne fonctionne pas :)


Message édité par guiguivts le 11-04-2007 à 13:55:25
Reply

Marsh Posté le 11-04-2007 à 14:36:29    

Etonnant j'ai rajouté dans mon troisieme existe chemin un prédicat estliste(L) décrit comme ça :  
 
estliste([]).
estliste([X|S]).
 
et ça fonctionne, à priori ça ne marche pas sans ça car on ne sait pas ce que c'est L mais j'avoue que je voie pas tres bien pourquoi !

Reply

Marsh Posté le 11-04-2007 à 14:36:29   

Reply

Marsh Posté le 11-04-2007 à 15:13:36    

Enfin de compte ça ne marche pas si le chemin n'existe pas, il boucle...

Reply

Marsh Posté le 11-04-2007 à 15:54:38    

Y a pas des connaisseurs en prolog par ici ? :(

Reply

Marsh Posté le 11-04-2007 à 17:40:35    

?

Reply

Marsh Posté le 11-04-2007 à 17:48:14    

non apparement. [:dawa]

Reply

Marsh Posté le 11-04-2007 à 17:49:26    

FUIS PENDANT QU4IL EN EST ENCORE TEMPS PAUVRE FOU §§§§ [:gandalf]


---------------
Töp of the plöp
Reply

Marsh Posté le 11-04-2007 à 17:49:52    

Plusieurs choses
Choisis, travaille avec des cases ou avec des coordonnées mais là tu mélangers un peu.
 
Ton prédicat membre/2, tu peux l'écrire comme ça, ce sera plus général :

Code :
  1. membre(X, [X| _]) :- !.
  2. membre(X, [_ | T] :-
  3.     membre(X, T).


 
 
Sans test aucun car je n'ai pas Prolog sous la main, je ferais comme ça :
Je pars de la case (X,Y) et je veux aller à la case (A,B)

Code :
  1. existechemin(X,Y,X,Y,[]). % le chemin est vide entre les deux mêmes cases
  3. existechemin(X,Y,A,B,[case(A,B)]) :- voisin(X,Y,A,B),!.
  5. existechemin(X,Y,A,B,[case(A,B) | L] ) :-
  6.     % La case(C,D) est proche de la case (A,B)
  7.     voisin(X,Y,C,D) ,
  8.     % je regarde s'il existe un chemin de la case(X,Y) à la case(C,D)
  9.     existechemin(X,YC,D,L),
  10.     %  On regarde si la case n'a pas déjà été visitée.
  11.     not(membre(case(A,B),L)).

Attention ce code te donne le chemin à l'envers.
Maintenant, personnellement, je chercherais toutes les cases accessibles en 1 pas, puis toutes celles accessibles en 2, puis 3 jusqu'a arriver à la case(A,B). Cette méthode te donnera en plus le plus court chemin.
 
_darkalt3_ [:alana21]


Message édité par Trap D le 11-04-2007 à 17:53:16
Reply

Marsh Posté le 11-04-2007 à 18:20:47    

J'ai fait plus ou moins pareil je trouve non ?  
 
Tu pars de la case X,Y pour aller à la case A,B donc tu cherches récursivement s'il existe un chemin de X,Y à C,D C,D étant proche de A,B  
 
Moi je pars de X,Y pour aller à A,B et je cherche s'il existe un chemin entre C,D et A,B C et D étan proche de X,Y ça revient au même je trouve mais je peux me tromper.  
 
J'ai tester ton code ça revient au même que le mien ça boucle dans certains cas lorsque le chemin n'existe pas :(  
 
bye

Reply

Marsh Posté le 12-04-2007 à 00:05:55    

Bon, je suis devant SWI-Prolog et maintenant ça fonctionne.
 
Voilà comment j'ai travaillé.
J'ai défini le prédicat voisin comme ceci :

Code :
  1. voisin(case(X,Y),case(A,B)) :-
  2.       (   A is X - 1, B = Y, case(A,B));
  3.       (   A is X + 1, B = Y, case(A,B));
  4.       (   A = X, B is Y - 1, case(A,B));
  5.       (   A = X, B is Y + 1, case(A,B)).

Pour pouvoir, en interrogeant la base de fait  de cette façon : voisin(case(X,Y),Z). obtenir toutes les cases voisines de la case(X,Y).
 
J'utilise maintenant un prédicat existechemin(X,Y,L, NL) donc à 4 arguments où
X est la case de départ,  
Y est la case d'arrivée,  
L est le chemin déjà parcouru
NL le chemin final  
 
Maintenant on construit le chemin :

Code :
  1. % Quand les deux case sont voisines on ajoute simplement
  2. % les deux cases au chemin déjà parcouru (on a terminé).
  3. existechemin(X,Y,L, L1) :-
  4. voisin(X,Y),
  5. !,
  6. append([X,Y], L, L1).
  9. % Sinon, on va chercher une case voisine
  10. existechemin(X , Y, L, L1) :-   
  11. % La case Z est proche de la case Y
  12. voisin(Y,Z),
  13. % la case n'a pas déjà été visitée
  14. \+membre(Z,L),
  15. % je calcule le chemin de la case X à la case Z
  16. existechemin(X, Z, [Y | L], L1).


Le chemin est construit dans l'ordre.
Maintenant, pour rechercher un chemin, tu fais par exemple

Code :
  1. existechemin(case(1,1), case(5,4), [], L).


Message édité par Trap D le 12-04-2007 à 00:16:31
Reply

Marsh Posté le 12-04-2007 à 11:29:13    

Bon bien ça ne marche pas il aime pas ton append et même sans rajouter de L1 en gardant juste L il boucle j'utilise sicstus prolog mais je crois que je vais arréter je perd trop de temps

Reply

Marsh Posté le 12-04-2007 à 11:43:59    

Dommage, utilise SWi-Prolog, c'est mieux.
 
PS : si c'est la append qui te gène, fais

Code :
  1. existechemin(X,Y,L, [X, Y | L]) :-   
  2.     voisin(X,Y),    !.


Message édité par Trap D le 12-04-2007 à 11:52:56
Reply

Marsh Posté le 12-04-2007 à 11:54:44    

je peux utiliser que sicstus car je l interface avec java  
 
merci en tous cas

Reply

Marsh Posté le 12-04-2007 à 12:06:09    

en fait le soucis c'est que dans ce prédicat  
 
existechemin(X , Y, L, L1) :-    
voisin(Y,Z),
/+membre(Z,L),
 existechemin(X, Z, [Y | L], L1).
 
Ptet que ça marche mais je ne comprend pas dans ce cas , comme on rajoute La nouvelle case Y dans l'appel récursif il est possible que l'on teste quand même deux fois ce Y.  
 
Par exemple on appelle une premiere fois ce prédicat et X à plusieurs voisins Z On rappelle ce prédicat récursivement avec le premier voisins et donc le premiers voisin va rajouter ses propres voisins à L. Mais lorsque cet appel sera terminé le permier appel du prédicat va reprendre avec un autre voisin mais avec l'ancienne liste L et donc il est possible de tester plusieurs fois la même case c'est peut etre ce qui boucle je ne sais pas.
 
ça ne boucle que sur certain cas c'est bizarre.

Reply

Marsh Posté le 12-04-2007 à 13:35:22    

Peux-tu m'indiquer tes cases valides ?
Moi j'ai défini dans ma base de faits
case(1,1).
case(1,2).
case(1,3).
etc, de manière à avoir plusieurs possibilités de chemins pour aller d'une case à une autre, et je les obtiens tous. Le problème vient peut-être de cette définitions de case.
 
voisin(Y,Z) doit fournir un voisin de Y à chaque appel, c'est essentiel.
Par le phénomène de backtrack, quand un parcours échoue on revient sur ses pas et on essaye avec un nouveau voisin.
 
 
 

Reply

Marsh Posté le 12-04-2007 à 14:01:10    

Oui je comprend pas non plus. en fait j'ai un damier de 10 sur 10 avec des murs à l'intérieur si je prend un nombre assez petit de case par exemple 10 12 ça fonctionne mais si j'en prend 50 ça ne marche plus.
 
Il y a donc 100 cases mais elles ne sont pas forcément accessibles.

Reply

Marsh Posté le 12-04-2007 à 14:24:36    

Voilà mon code : voisin j'ai testé à beaucoup de reprises et il fonctionne :  
 
le prolog :
 

Code :
  1. membre(X,[X|_]) :- !.
  3. membre(X,[_|T]) :- membre(X,T).
  5. voisindeux(case(X,Y),case(A,B)) :- voisin(X,Y,A,B).
  7. existechemin(X,Y,L,[X,Y|L]) :- voisindeux(X,Y) , ! .
  9. existechemin(X,Y,L,L1) :- voisindeux(Y,Z) , \+membre(Z,L) , existechemin(X,Z,[Y|L],L1).


 
 
le java
 

Code :
  1. if(sp.boolRequete("existechemin(case(1,1),case(10,1),[],L)." ))
  2. {
  3. System.out.println("il y a un chemin" );
  4. }
  5. else
  6. {
  7. System.out.println("il n y a pas de chemin" );
  8. }


 
Je pige pas..
 
 
 

Reply

Marsh Posté le 12-04-2007 à 15:52:55    

Pourquoi ça marche pas :'(

Reply

Marsh Posté le 12-04-2007 à 17:39:40    

Tu es sûr de l'interface avec Java ?
D'autre part cette méthode bouffe pas mal de mémoire, des algos plus élaborés seraient sans doute plus adaptés.
Cependant, je viens de faire le test avec ça,  

Code :
  1. damier(L) :-
  2. L = [[1,1,1,0,0,0,1,1,1,0],
  3.      [1,0,1,0,0,0,1,1,1,1],
  4.      [1,1,1,1,1,1,1,0,0,1],
  5.      [1,1,1,0,0,0,1,0,1,0],
  6.      [1,0,1,1,1,1,1,1,1,0],
  7.      [1,1,0,0,0,0,1,0,1,0],
  8.      [0,1,1,0,0,0,1,0,1,0],
  9.      [0,1,0,0,0,0,1,0,1,0],
  10.      [1,1,1,0,0,0,1,1,1,0],
  11.      [1,1,1,1,1,1,1,1,1,1]].
  12. cell(X,Y):-
  13. damier(L),
  14. nth1(X,L, R),
  15. nth1(Y,R,1).

Ca fonctionne très bien.


Message édité par Trap D le 12-04-2007 à 17:57:59
Reply

Marsh Posté le 12-04-2007 à 18:05:13    

honnetement je comprend pas ça fait 24h que je suis dessus quand même :p  
 
je viens de passer 10 minutes à faire exactement la même chose en utilisant java et prolog juste pour tester si les faits existent et ça fonctionne donc je voie pas mais bon ça a l'air de marcher :)  
 
Par contre comme prévu c'est long et lourd en java alors qu'en prolog c'est censé faire 3 lignes..

Reply

Marsh Posté le 12-04-2007 à 18:15:37    

Pour Plus de renseignements sur l'interface Java, reagarde là :
http://groups.google.de/group/comp.lang.prolog/topics

Reply

Marsh Posté le 12-04-2007 à 18:18:18    

merci pr tout ;)

Reply

Marsh Posté le 13-04-2007 à 14:41:06    

Ce petit programme en java fonctionne très bien avec l'interface jpl de SWI-Prolog.

Code :
  1. import java.util.Hashtable;
  2. import jpl.*;
  3. import jpl.Query;
  6. public class Labyrinthe
  7. {
  8. public static void
  9. main( String argv[] )
  10. {
  12.  String t1 = "consult('Labyrinthe.pl')";
  13.  Query q1 = new Query(t1);
  15.  System.out.println( t1 + " " + (q1.hasSolution() ? "succeeded" : "failed" ) );
  19.  String t2 = "existechemin(cell(7,9), cell(10,10), [], L)";
  20.  Query q2 = new Query(t2);
  22.  System.out.println( "first solution of " + t2 + ": L = " + q2.oneSolution().get("L" ));
  24.  //--------------------------------------------------
  26.  java.util.Hashtable[] ss2 = q2.allSolutions();
  28.  System.out.println( "all solutions of " + t2);
  29.  for ( int i=0 ; i<ss2.length ; i++ ) {
  30.   System.out.println( "L = " + ss2[i].get("L" ));
  31.  }
  33.  //--------------------------------------------------
  35.  System.out.println( "each solution of " + t2);
  36.  while ( q2.hasMoreSolutions() ){
  37.   java.util.Hashtable s2 = q2.nextSolution();
  38.   System.out.println( "L = " + s2.get("L" ));
  39.  }
  40. }
  41. }

Code de Labyrinthe.pl

Code :
  1. damier(L) :-
  2. L = [[1,1,1,0,0,0,1,1,1,0],
  3.      [1,0,1,0,0,0,1,1,1,1],
  4.      [1,1,1,1,1,1,1,0,0,1],
  5.      [1,1,1,0,0,0,1,0,1,0],
  6.      [1,0,1,1,1,1,1,1,1,0],
  7.      [1,1,0,0,0,0,1,0,1,0],
  8.      [0,1,1,0,0,0,1,0,1,0],
  9.      [0,1,0,0,0,0,1,0,0,0],
  10.      [1,1,1,0,0,0,0,1,0,0],
  11.      [1,1,1,1,1,1,1,1,1,1]].
  12. cell(X,Y):-
  13. damier(L),
  14. nth1(X,L, R),
  15. nth1(Y,R,1).
  17. voisin(cell(X,Y),cell(A,B)) :-
  18.       (   A is X - 1, B = Y, cell(A,B));
  19.       (   A is X + 1, B = Y, cell(A,B));
  20.       (   A = X, B is Y - 1, cell(A,B));
  21.       (   A = X, B is Y + 1, cell(A,B)).
  24. %  existechemin(X,X,L,[X | L]). % le chemin est vide entre les deux
  25. %  mêmes cases
  27. existechemin(X,Y,L, [X,Y |L]) :-
  28. voisin(X,Y),
  29. !.
  30. %append([X,Y], L, L1).
  32. existechemin(X , Y, L, L1) :-   
  33. % La case Z est proche de la case Y
  34. voisin(Y,Z),
  35. \+membre(Z,L),
  36. % je regarde s'il existe un chemin de la case X à la case Z
  37. existechemin(X, Z, [Y | L], L1).
  40. membre(X,[X |_]):- !.
  41. membre(X,[_|S]) :-
  42. membre(X,S).


Reply

Marsh Posté le 04-05-2007 à 19:01:25    

Salut,  
 
merci pour ton dernier message. J'avais un peu laissé tombé mais quand même réussi à faire fonctionner chemin
 
là j'essaye de récupérer la liste des chemin mais ça ne fonctionne malheureusement pas :-(
 
donc j'ai plus ou mon les mêmes prédicats pour existe chemin :  
 

Code :
  1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  2. % prédicat permettant de trouver un chemin entre deux cases %
  3. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  5. voisindeux(case(X,Y),case(A,B)) :- voisin(X,Y,A,B).
  7. existechemin(X,X,L,[X | L]). % le chemin est vide entre les deux
  9. existechemin(X,Y,L, [X,Y |L]) :- voisindeux(X,Y) , !.
  11. existechemin(X , Y, L, L1) :-  voisindeux(Y,Z) , \+membre(Z,L), existechemin(X, Z, [Y | L], L1).


 
 
Pour récuperer une liste de résultat nous utilisons une fonction faite par le prof :  
 

Code :
  1. public LinkedList listeresultat(String texte,String terme){
  2.  HashMap resultat = new HashMap();
  3.  LinkedList retour = new LinkedList();
  4.  try {
  5.   SPQuery query=sp.openQuery(texte,resultat);
  6.   while (query.nextSolution ()) {
  7.       retour.add(((SPTerm)resultat.get(terme)).toString());
  8.   }
  9.   query.close();
  10.  } catch (Exception e) {e.printStackTrace();}
  12.  return retour;
  13. }


 
 
Et j'appelle ça comme ça :  
 
listechemin =_sp.listelisteresultat("existechemin(case(1,1),case(3,1),[],L).", "L" );
 
malheureusement ça boucle..
 
J'ai une autre méthode pour récuperer le premier résultat de cette liste  :  
 

Code :
  1. public String premierresultat(String texte, String terme){
  2.  HashMap result = this.requete(texte);
  3.  if (result.size()>0) return ((SPTerm)result.get(terme)).toString();
  4.  else return "";
  5. }


 
Cela fonctionne pourtant !  
 
bye

Reply

Marsh Posté le 04-05-2007 à 20:48:49    

:)

Reply

Marsh Posté le 05-05-2007 à 11:37:48    

Je ne m'y connais malheureusement pas assez en Java pour te conseiller.  
Tout ce que je peux dire, c'est que dans l'exemple que j'ai posté, je récupère tous les chemins. Il est adapté des exemples de JPL de SWI-Prolog.

Reply

Marsh Posté le 05-05-2007 à 12:11:21    

Oui moi aussi il le fait bien, l'ennui c'est que lorsqu'il n'y a plus de chemins  possibles ça boucle :( de même avec ton exemple quand je teste sur un chemin qui n'existe pas il boucle :(

Reply

Marsh Posté le 05-05-2007 à 15:16:34    

Je viens de faire le test, le programme génère une exception que tu peux intercepter si le chemin n'existe pas, (toujours avec SWI-Prolog et JPL).

Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed