Discussion :

[Elmilouse]

Je modelise un graphe de cette facon : un arc = un fait.

Code :

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

1
2
3
4
5
6
7
 
distance(a,b,10).
distance(a,c,5).
distance(b,f,10).
distance(c,f,15).
distance(c,e,20).
distance(f,e,15).

ensuite, je voudrais calculer ts les points distance de moins de 30 d'un point donné.
J'ai donc ecrit ces regles :

Code :

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

1
2
3
4
 
proximite(X,Y) :- distant(X,Y,Z),Z<30.
distant(X,Y,Z) :- distance(X,Y,Z).
distant(X,Y,Z) :- distant(X,W,U),distant(W,Y,V), Z is U+V.

Evidemment ca marche pas(sinon , je serais pas là )
ca met une erreur : out of local stack , quand je lance par exemple proximite(a,X).

Saurez-vous trouver l'erreur?

Merci bcp de vous pencher sur mon probleme.

[Trap D]

Salut
A première vue, c'est le

Code :

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

distant(X,Y,Z) :- distance(X,Y,Z).

qui n'est pas bon, mais comme je ne suis pas chez moi ...

[Elmilouse]

pourquoi cette ligne serait fausse à ton avis?

j ai arrangé un peu le programme :

Code :

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

1
2
3
4
5
6
 
listeProx(A,L) :- setof(T,proximite(A,T),L).
proximite(X,Y) :- chemin(X,Y,Z),Z<30.
chemin(A,B,X) :- distance(A,B,X).
chemin(A,B,X) :- distance(B,A,X).
chemin(A,B,X) :- distance(A,Z,Y),chemin(Z,B,W), X is Y+W.

listeProx(a,L) va me donner L=[a,b,c,e,f].
mais si jamais il y a un cycle dans le graphe, le programme boucle.

Je pense qu'il faudrait memoriser le chemin parcouru , mais je vois pas comment faire.

[Trap D]

Tout à fait, j'ai lu trop rapidement et j'avis compris :

Code :

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

distant(X,Y,Z) :- distant(X,Y,Z).

[Trap D]

je crois qu'il faudrait rajouter un argument a chemin:
chemin(A,B,X,V) où V est la liste des noeuds déjà visités.
Essaye ça :

Code :

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

1
2
3
4
5
absent(X,[]).
absent(X,[H|T]):- X \== H, absent(X, T).   
chemin(A,B,X,V) :- V=[], distance(A,B,X). 
chemin(A,B,X,V) :- V=[], distance(B,A,X).
chemin(A,B,X,[Z|V]) :- absent(Z, V), distance(A,Z,Y),chemin(Z,B,W,V), X is Y+W.

J'obtiens

chemin(a,f,X,Y).

X = 20
Y = [b] ;

X = 20
Y = [c] ;

X = 40
Y = [c, e] ;

X = 50
Y = [b, f, e] ;

X = 50
Y = [c, f, e] ;

Mais après ça boucle.

[edit] J'ai édité le post pour avoir plus de solutions.
[/edit]

[billynirvana]

J'ai résolu ton problème!

Pour la syntaxe t'inquiète pas adapte le à la version de Prolog que tu possèdes.

A bientôt.

Code :

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
%- Problème du plus court chemin
 
%-                8
%-	A ----------------- B
%-       -                   ----   4
%-        -  2                    -----
%-         -              9            ------
%-          C ------------------------------- F
%-          - -                         -----
%-        5 -  --- 6               -----
%-          -     ---        -----   8
%-          D ------- E -----
%-               3
 
 
distance(areteA, areteB, 8)->;
distance(areteA, areteC, 2)->;
distance(areteB, areteF, 4)->;
distance(areteC, areteD, 5)->;
distance(areteC, areteE, 6)->;
distance(areteC, areteF, 9)->;
distance(areteD, areteE, 3)->;
distance(areteE, areteF, 8)->;
 
 
plus_court_chemin(x, y, s)->
	findall(c, chemin_sans_boucles(x, y, nil, c), l)
	trier(l, s.l');
 
chemin_sans_boucles(x, x, p, <x.nil, 0>)->;
chemin_sans_boucles(x, y, p, <x.l, d_ist>)->
	distance(x, z, d)
	hors_de(z, p)
	chemin_sans_boucles(z, y, x.p, <l, d'>)
	val(d+d', d_ist);
chemin_sans_boucles(x, y, p, <x.l, d_ist>)->
	distance(z, x, d)
	hors_de(z, p)
	chemin_sans_boucles(z, y, x.p, <l, d'>)
	val(d+d', d_ist);
 
 
%- tri par ordre croissant
trier(nil, nil)->;
trier(<x, d>.l, m)->
	trier(l, l')
	inserer_bon_endroit(<x, d>, l', m);
 
inserer_bon_endroit(<x, d>, nil, <x, d>.nil)->;
inserer_bon_endroit(<x, d>, <y, d'>.l, <x, d>.<y, d'>.l)->
	val(d '<' d', 1)!;
inserer_bon_endroit(<x, d>, <y, d'>.l, <y, d'>.m)->
	inserer_bon_endroit(<x, d>, l, m);
 
 
hors_de(x, nil)->;
hors_de(x, y.l)->
	dif(x, y)
	hors_de(x, l);
 
 
/*
> chemin_sans_boucles(areteA, areteB, nil, s);
{s=<areteA.areteB.nil,8>}
{s=<areteA.areteC.areteD.areteE.areteF.areteB.nil,22>}
{s=<areteA.areteC.areteE.areteF.areteB.nil,20>}
{s=<areteA.areteC.areteF.areteB.nil,15>}
> chemin_sans_boucles(areteA, areteE, nil, s);
{s=<areteA.areteB.areteF.areteC.areteD.areteE.nil,29>}
{s=<areteA.areteB.areteF.areteC.areteE.nil,27>}
{s=<areteA.areteB.areteF.areteE.nil,20>}
{s=<areteA.areteC.areteD.areteE.nil,10>}
{s=<areteA.areteC.areteE.nil,8>}
{s=<areteA.areteC.areteF.areteE.nil,19>}
> 
> tous_les_chemins(areteA, areteB, s);
{s=<areteA.areteB.nil,8>.<areteA.areteC.areteD.areteE.areteF.areteB.nil,22>.<areteA.areteC.areteE.
areteF.areteB.nil,20>.<areteA.areteC.areteF.areteB.nil,15>.nil}
> 
> plus_court_chemin(areteA, areteB, s);
{s=<areteA.areteB.nil,8>}
> plus_court_chemin(areteA, areteE, s);
{s=<areteA.areteC.areteE.nil,8>}
> plus_court_chemin(areteD, areteB, s);
{s=<areteD.areteC.areteA.areteB.nil,15>}
*/

[amo-said]

Salut !
Est-ce que quelqu'un peut l'adapter à la version Turbo-Prolog
En plus il manque d'indiquer DOMAINS, PREDICATES..

Rq: il existe une erreur dans l'utilisation de "findall".. il faut utiliser les parametres C et Cs à la place de c et l..
Solution voir :http://wwwcgi.rdg.ac.uk:8081/cgi-bin...oghelp/findall


J'ai essaié de le changer mais il y a un autre probleme : celle de " x.l " et " s.l' " (probleme dans le point!) [est-ce que elle veut dire une concatenation?]
Solution(pour la concatenation):
concat([],Ys,Ys).
concat([X|Xs], Ys, [X|Whatever]) :-concat(Xs,Ys,Whatever).

J'attend la version final !
Cordialement.