Systemes a base de connaissances:Travaux pratiques de Prolog

De Wiki de Romain RUDIGER
Aller à : navigation, rechercher

Rapport du TP2 d'Intelligence Artificielle Recherche de Chemin dans un Graphe

Nous avons une liste de routes détaillées de deux villes reliées entre elles et de leur distance qui les sépare. Exemple : Pour les besoins de l'éxercice, une route étant à double sens, il est nécessaire d'avoir un graphe non-orienté des routes. Voici le code qui effectue cette opération : L'éxemple précédent devient :

Tous les Chemins entre Deux Villes

Réalisation

Pour réaliser cette opération, nous avons besoin d'une première fonction permettant de savoir si une ville à déjàs été parcourue :

route1(nantes,rennes,110).
route1(brest,saint_malo,230).
/*création d'un graphe non-orienté*/
route(X,Y,D):-
route1(Y,X,D).
route(X,Y,D):-
route1(X,Y,D).
route(nantes,rennes,110).
route(brest,saint_malo,230).
route(rennes,nantes,110).
route(saint_malo,brest,230).
/*permet de detecter la presence ou non d'un element dans une liste.
Retourne yes si non present.*/
/*Fin de récursivité : n'importequel élément, liste vide. */
pasDejaVu(_,[]).
/*Lélément recherché, la liste de recherche.*/
pasDejaVu(X,[Y|S]):-
X\=Y,
pasDejaVu(X,S).

Calcul de tous les chemins entre deux villes

Le principe est de prendre n'importe quelle ville suivante à condition qu'elle n'est pas déjàs été parcourue. Si la ville choisie ne correspond pas à la ville d'arrivée, donc l'appel récursif ne correspond pas au fait de la terminaison de récursivité, alors on recommence en prenant soin de rajouter la ville trouvée à la liste des villes parcourues. La récursivité se termine lorsque la ville d'arrivée correspond à la ville suivante. Pour lancer la recherche, il faut passer en paramètre le nom de la ville de départ, celui de la ville d'arrivée, un nom de variable correspondant à la distance, une liste comprenant la ville départ (elle sert à initialiser la liste des villes déjas vues), et une variable permettant de sauvegarder la liste des villes parcourues.

Amélioration de l'appel de la fonction

Permet juste de simplifier la syntaxe d'appel en évitant de répéter la ville de départ pour la liste des villes déjas parcourues.

Liste des Chemins

Pour créer la liste, nous utilisons la fonctions donnée par Prolog findall. Elle permet d'enregistrer tous les résultat dans une liste dont nous choisissons les éléments et leur position.

/*permet de terminer la récusivité*/
chemin(V,V,0,_,[]).
/*ville depart, ville arrivée, distance solution, ville parcourue, itinéraire*/
chemin(X,Y,D,VDV,ITI):-
/*trouver une route entre la ville de départ et une autre ville étape*/
route(X,VSUIV,D1),
/*vérifier que la ville suivante n'est pas deja parcourue*/
pasDejaVu(VSUIV,VDV),
/*recommencer la recherche en remplaçant la ville de départ par la ville
suivante.*/
chemin(VSUIV,Y,D2,[VSUIV|VDV],ITI2),
/*trés rare, on construit la liste VDV en descendant ! ITI2
permet de sauvegarder la liste des villes lorsque l'on remonte.*/
/*en remontant la récursivité, on calcul la distance solution...*/
D is D1 + D2,
/*...et construit l'itinéraire solution.*/
ITI = [VSUIV|ITI2].
/*permet de simplifier la syntaxe d'appel*/
itineraire(V1,V2,D,C):-
chemin(V1,V2,D,[V1],C1),
C = [V1|C1]. /*met la ville de départ en tête de liste.*/
/*trouver toutes les solutions.*/
tousChemins(X,Y,LISTE):-
findall([X,Y,D,ITI],itineraire(X,Y,D,ITI),LISTE). /*realise
tous les chemins possibles, met tout dans la LISTE au format [ville
de départ, ville d'arrivée, distance solution, toutes les villes du
chemin]*/

Algorithme du plus court chemins

Pour rechercher le plus court chemin, nous nous sommes basé sur l'algorithme de Dijkstra abordée l'année dernière en théorie des graphe.

/*Le dernier point visité est le point d'arrivée => on s'arrête*/
choixChemin( [ D-[V|ITI] |_], V, [V|ITI], D).
/*ville depart, ville arrivée, itinéraire, distance solution*/
choixChemin( X, Y, ITI, D) :-
listerSuivants(X, ListeSuivant),
choixSuivant(ListeSuivant, Suivant),
choixChemin( [Suivant|X], Y, ITI, D).
/*ville depart, ville arrivée, itinéraire, distance solution*/
plusPetitChemin(X, Y, ITI, D) :-
choixChemin([0-[X]], Y, ITI, D).
/*Chemin des villes déjà parcourrues, Suivant sera la ville suivante la moins
éloignée*/
listerSuivants(VDV, ListeSuivant) :-
/* Recherche de tous les fils de la dernière ville de VDV*/
findall(ListeSortie,
(
member( Len-[X|Chemin], VDV), % - le point P2 a déjà été visité
/*trouve une route entre la ville du noeud et une autre ville*/
route(X,Y,D2),
/*vérifie que la ville suivante n'est pas deja dans l'arbre*/
\+dejaVu(Y, VDV),
/* on calcul la nouvelle distance avec la ville suivante en cours*/
NewD is Len+D2,
/* Ajout du résutat dans la liste du findall : distance, chemin */
ListeSortie=NewD-[Y,X|Chemin]
),
ListeSuivant).
/*Liste des fils, choix du meilleur fils*/
choixSuivant(ListeSuivant, Suivant) :-
keysort(ListeSuivant, [Suivant|_]). /*tri dans l'ordre croissant, puis sélection du
premier élément sans le pain au chocolat */
/*permet de detecter la presence ou non d'un element dans une liste. Retourne yes si
present.*/
dejaVu(X, VDV) :- /*n'importequel élément, liste vide.*/
memberchk(_-[X|_], VDV).

Code Source

dijkstra

route1(nantes,rennes,110).
route1(brest,saint_malo,230).
route1(nantes,vannes,120).
route1(saint_malo,mont_saint_michel,60).
route1(nantes,saint_nazaire,60).
route1(bordeaux,tours,350).
route1(nantes,bordeaux,340).
route1(mont_saint_michel,caen,200).
route1(nantes,angers,90).
route1(rennes,caen,180).
route1(rennes,brest,250).
route1(caen,le_mans,160).
route1(rennes,angers,130).
route1(le_mans,angers,100).
route1(rennes,saint_malo,70).
route1(le_mans,tours,90).
route1(rennes,mont_saint_michel,70).
route1(le_mans,orleans,110).
route1(angers,tours,130).
route1(cherbourg,caen,120).
route1(vannes,brest,190).
route1(cherbourg,mont_saint_michel,170).

/*recherche de tous les chemins entre 2 villes*/

/*création d'un graphe non-orienté*/
route(X,Y,D):-
	route1(Y,X,D).
route(X,Y,D):-
	route1(X,Y,D).

/*Le dernier point visité est le point d'arrivée => on s'arrête*/
choixChemin( [ D-[V|ITI] |_], V, [V|ITI], D).

/*ville depart, ville arrivée, itinéraire, distance solution*/
choixChemin( X, Y, ITI, D) :-
  listerSuivants(X, ListeSuivant), 
  choixSuivant(ListeSuivant, Suivant),
  choixChemin( [Suivant|X], Y, ITI, D).

/*ville depart, ville arrivée, itinéraire, distance solution*/
plusPetitChemin(X, Y, ITI, D) :-
  choixChemin([0-[X]], Y, ITI, D).

/*Chemin des villes déjà parcourrues, Suivant sera la ville suivante la moins éloignée*/
listerSuivants(VDV, ListeSuivant) :-

/* Recherche de tous les fils de la dernière ville de VDV*/ 
  findall(ListeSortie,
    (
      member( Len-[X|Chemin], VDV),  % - le point P2 a déjà été visité

	/*trouve une route entre la ville du noeud et une autre ville*/
      route(X,Y,D2),

	/*vérifie que la ville suivante n'est pas deja dans l'arbre*/        
      \+dejaVu(Y, VDV),

	/* on calcul la nouvelle distance avec la ville suivante en cours*/
      NewD is Len+D2,

	/* Ajout du résutat dans la liste du findall : distance, chemin */
      ListeSortie=NewD-[Y,X|Chemin]
    ),
    ListeSuivant).


/*Liste des fils, choix du meilleur fils*/
choixSuivant(ListeSuivant, Suivant) :-
  keysort(ListeSuivant, [Suivant|_]). /*tri dans l'ordre croissant, puis sélection du premier élément sans le pain au chocolat */

/*permet de detecter la presence ou non d'un element dans une liste. Retourne yes si present.*/
dejaVu(X, VDV) :- /*n'importequel élément, liste vide.*/
  memberchk(_-[X|_], VDV).

liste

route1(nantes,rennes,110).
route1(brest,saint_malo,230).
route1(nantes,vannes,120).
route1(saint_malo,mont_saint_michel,60).
route1(nantes,saint_nazaire,60).
route1(bordeaux,tours,350).
route1(nantes,bordeaux,340).
route1(mont_saint_michel,caen,200).
route1(nantes,angers,90).
route1(rennes,caen,180).
route1(rennes,brest,250).
route1(caen,le_mans,160).
route1(rennes,angers,130).
route1(le_mans,angers,100).
route1(rennes,saint_malo,70).
route1(le_mans,tours,90).
route1(rennes,mont_saint_michel,70).
route1(le_mans,orleans,110).
route1(angers,tours,130).
route1(cherbourg,caen,120).
route1(vannes,brest,190).
route1(cherbourg,mont_saint_michel,170).

/*recherche de tous les chemins entre 2 villes*/

/*création d'un graphe non-orienté*/
route(X,Y,D):-
	route1(Y,X,D).
route(X,Y,D):-
	route1(X,Y,D).

/*permet de detecter la presence ou non d'un element dans une liste. Retourne yes si non present.*/
pasDejaVu(_,[]). /*n'importequel élément, liste vide.*/
pasDejaVu(X,[Y|S]):-
	X\=Y,
	pasDejaVu(X,S).

/*permet de terminer la récusivité*/
chemin(V,V,0,_,[]).

/*ville depart, ville arrivée, distance solution, ville parcourue, itinéraire*/
chemin(X,Y,D,VDV,ITI):-
	route(X,VSUIV,D1), /*trouve une route entre la ville de départ et une autre ville étape*/
	pasDejaVu(VSUIV,VDV), /*vérifie que la ville suivante n'est pas deja parcourue*/
	chemin(VSUIV,Y,D2,[VSUIV|VDV],ITI2), /*recommence la recherche en remplaçant la ville de départ par la ville suivante.*/
		/*trés rare, on construit la liste VDV en descendant ! ITI permet de sauvegarder la liste des villes lorsque l'on remonte.*/
	D is D1 + D2, /*en remontant la récursivité, on calcul la distance solution...*/
	ITI = [VSUIV|ITI2]. /*...et construit l'itinéraire solution.*/

/*permet de simplifier la syntaxe d'appel*/
itineraire(V1,V2,D,C):-
	chemin(V1,V2,D,[V1],C1),
	C = [V1|C1]. /*met la ville de départ en tête de liste.*/

/*trouver toutes les solutions.*/
tousChemins(X,Y,LISTE):-
	findall([X,Y,D,ITI],itineraire(X,Y,D,ITI),LISTE). /*realise tous les chemins possibles, met tout dans la LISTE au format [ville de départ, ville d'arrivée, distance solution, toutes les villes du chemin]*/