Discussion :

[Fred_ET]

Bonjour à tous!

Voila, j'ai un devoir de prolog mais je suis completement bloqué sur un numéro.
Je vous explique:

Premièrement, on me donne ces 4 faits:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
%--------------------------------------
% Voisin
%--------------------------------------
voisin(lasalle, verdun).
voisin(verdun, westmount).
voisin(westmount, villemarie).
voisin(villemarie, outremont).

Deuxièment, on me demande de faire un predicat: voisins (Lieu, Lieu2) :-
exemples:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
?- voisins (lasalle, X). X = verdun
?- voisins (verdun, X). X = westmount ; lasalle

J'ai fait ce prédicat.. pas tres compliqué:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

voisins(Lieu, Lieu2) :- voisin(Lieu, Lieu2) ; voisin(Lieu2, Lieu).

C'est sur la prochaine question que j'ai un problème.
On me demande de faire un prédicat permettant de consulter les lieux de proche en proche, mais en commençant par les localités immédiatement voisines. A distance égale, je doit essayer d’abord les
voisins à l’Est.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

prédicat: trouver_prochainlieu (Lieu, Lieu2) :-

ex:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
?- trouver_prochainlieu (verdun, X). 
X = westmount ;  
lasalle ;
villemarie ; 
outremont

Si quelqu'un pouvait m'aider sur cet exercice... sa doit faire 8 heures que j'essai des trucs mais au fur et à mesure que j'essai je m'éloigne de plus en plus...

Merci d'avance!

[Trap D]

Salut

J'ai un peu réfléchi à ton problème.
Je pense que ton prédicat voisin doit renvoyer une liste [VilleDroite, VilleGauche], l'une des villes pouvant être [] en cas d'absence.

Ensuite tu peux construire le graphe des villes accessibles à partir de verdun puis faire un parcours en largeur de ce graphe.

Bon courage.

[Fred_ET]

Merci, mais le truc c'est que mon predicat voisins ne doit pas retourné une liste... J'essai encore mais jai rien trouvé.

[Trap D]

Ç'a t'est imposé par le prof ?

Rien ne t'empêche cependant d'écrire un autre prédicat voisins_bis pour les besoins de la cause .

[Trap D]

Bon, je ne sais pas où tu en es, je te propose ceci :

Code prolog :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
voisins(X, Y) :-
	voisin(X, Y); voisin(Y, X).
 
% V  : ville dont on recherche les voisins
% LV : liste des villes voisines (1 ou 2)
tous_les_voisins(V, LV) :-
	bagof(Y, voisins(V, Y), LV).
 
 
% prédicat initial de recherche des voisins
liste_voisins(X, L) :-
	proche_voisin(X, [X], L).
 
% X    : ville à visiter
% LstV : liste des villes déjà visitée
% LFV  : liste finale des voisins
proche_voisin(X, LstV, LFV) :-
	tous_les_voisins(X, L1),
	% L1 est composée d'une liste de 1 ou 2 villes
	etude(L1, LstV, [], LFV).
 
 
% LstV : liste des villes déjà visitée
% LV   : liste des voisins en construction
% LFV  : liste finale des voisins
etude([V1 | T], LstV, LV, LFV) :-
        % ville déjà visitée
        % on passe à la suite
	member(V1, LstV), !,
	etude(T, LstV, LV, LFV).
 
etude([V1 | T], LstV, LV, LFV) :-
	% V1 est une ville acceptable
	% on l'ajoute à la liste des voisins en construction
	append(LV, [V1], LV1),
	% on etudie le reste de la liste
	etude(T, [V1 | LstV], LV, LFV1),
	% on va chercher la liste des voisins de V1
	proche_voisin(V1, [V1 | LstV], LFV2),
	% on concatène dans l'ordre les villes visitées
	append(LV1, LFV1, LFV3),
	append(LFV3, LFV2, LFV).
 
% la liste est vide
% on unifie la liste des voisins en construction
% à la la liste finale
etude([], _LstV, LV, LV).

Tu lances avec liste_voisins(verdun, L).

[Fred_ET]

Merci pour ton aide mais OUI le predicat trouver_prochainlieu doit etre exactement de la forme: trouver_prochainlieu(Lieu, Lieu2) :-

Et je ne dois pas utiliser d'autres prédicat définis par moi autres que voisins cité plus haut qui ne peut retourner une liste................! Je ne comprend plus rien.

et sa doit etre récursif bien sur..

[pcaboche]

On me demande de faire un prédicat permettant de consulter les lieux de proche en proche, mais en commençant par les localités immédiatement voisines. A distance égale, je doit essayer d’abord les voisins à l’Est.

Ce n'est pas exactement ce qui est demandé, mais voici un exemple simple pour que tu comprennes le principe :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
parcours_est(A, A).
parcours_est(A, B) :-
  voisin(A, Est),
  parcours_est(Est, B).

Ici, pas besoin de liste, on parcours les éléments un par un.

[Fred_ET]

Oui, exact..c'est ce type de prédicat qu'il mne faut mais je n'arrive pas a comprendre. Merci pour votre aide je vais continuez d'essayer des choses mais je doit remettre le devoir ce soir et je risque de ne pas avoir trouvé. Si quelqu'un trouve dite le moi quand même j'aimerais savoir même s'il est trop tard.

Merci

edit: a date j'ai sa:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
trouver_prochainlieu(Lieu, Lieu2) :- voisins(Lieu, Lieu2).
trouver_prochainlieu(Lieu, Lieu2) :- voisins(Lieu, X), trouver_prochainlieu(X, Lieu2), \+ Lieu = Lieu2.

J'arrive a sortir en ordre:
westmount ;
lasalle ;
villemarie ;
outremont

pour :
trouver_prochainlieu(verdun, X).

mais sa bug a la fin .. je sais que sa ne fait pas trop de sens mais bon .. je sens que je m'y rapproche quand même. Si quelqu'un peu me dire ce qui cloche et manque dans mon code...

[pcaboche]

Merci pour votre aide je vais continuez d'essayer des choses mais je doit remettre le devoir ce soir et je risque de ne pas avoir trouvé. Si quelqu'un trouve dite le moi quand même j'aimerais savoir même s'il est trop tard.

Pour ton devoir, c'est trop tard (et puis on ne donne pas de solutions toutes faites).

Par contre, si tu veux approfondir la question des algos sur les graphes, il y a cet article :
http://pcaboche.developpez.com/artic.../algo-graphes/

[Fred_ET]

Je crois pas qu'il soit trop tard étant donné que cest une remise par email et qu'il me reste encore 7 heures pour finir.

Je continu d'essayer et si quelqu'un a un indice ou quoique ce soit j'apprecierais.

Merci pour l'article mais la parcontre je crois pas que sa puisse m'aider à court terme...

edit: jai fait une version non récursive qui ne fonctionne que pour ce cas particulier mais qui redonne les résulats exact... je dois maintenant convertir ce code en récursif.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
trouver_prochainlieu(Lieu, Lieu2) :- voisins(Lieu, Lieu2).
trouver_prochainlieu(Lieu, Lieu2) :- voisins(Lieu, X),voisins(X, Lieu2),\+ Lieu = Lieu2,\+ X = Lieu2.
trouver_prochainlieu(Lieu, Lieu2) :- voisins(Lieu, X),voisins(X, Y),voisins(Y, Lieu2),\+ Lieu = Lieu2,\+ X = Lieu2,\+ Y = Lieu2,\+ Y = Lieu.

il ne doit pas manquer grand chose au code ecrit dans mon message précédant mais mis a part les 2 premiers résultats ou il retourne les voisins direct de droit et de gauche en ordre, le code ne fait que le parcour a droite mais je doit alterner doite/gauche a chaque fois que c'est possible.

[pcaboche]

Il faut que tu fasses un prédicat intermédiaire avec 3 paramètres: le point de départ, la liste des points visités, le nouveau point. Tu cherches un voisin, tu regardes s'il n'a pas été visité, tu le retournes comme solution et tu l'ajoutes à la liste des visités avant de faire un appel récursif (parcours en profondeur).

Ensuite, tu modifies cet algo pour prendre en compte les autres règles (localités immédiatement voisines d'abord; à distance égale, d’abord les voisins à l’Est; etc.). (parcours avec heuristique)