Discussion :

[SteelBox]

Re :-)
Alors,encore une question sur les listes. J'ai besoin de sélectionner le minimum dans une liste. J'ai essayé ceci :

Code :

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

1
2
3
4
5
6
7
8
9
 
% minimum entre 2 entiers
min(X,Y,X) :- X =< Y.
min(Y,X,X) :- X =< Y.
 
% minimum pour la liste
% X contient le minimum de la liste fournise en deuxième paramètre
mininum(D,[D|[]]).
minimum(X,[_|B]):- minimum(X,B),min(A,X,R),X is R.

Voici la réponse :

[trace]
?- minimum(X,[1,2,3]).
Call: (8) minimum(_G495, [1, 2, 3]) ? creep
Call: (9) minimum(_G495, [2, 3]) ? creep
Call: (10) minimum(_G495, [3]) ? creep
Call: (11) minimum(_G495, []) ? creep
Fail: (11) minimum(_G495, []) ? creep
Fail: (10) minimum(_G495, [3]) ? creep
Fail: (9) minimum(_G495, [2, 3]) ? creep
Fail: (8) minimum(_G495, [1, 2, 3]) ? creep

Pourquoi ne répond t-il pas succès avec X=3 lorsqu'il arrive sur :

Call: (10) minimum(_G495, [3]) ? creep

Merci

[Trap D]

Voilà ce que je te propose :

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
% X est la liste, Y reçoit le minimum
%J'initialise la recherche en mettant liste vide comme plus petit élément
minimum(X, Y) :- minimum(X, [], Y).
 
% le principe est d'utiliser une variable intermédiaire qui va mémoriser
% le plus petit élément de la liste déjà parcourue.
 
% si la liste est terminée, X est le plus petit élément
% on l'unifie avec la valeur retour
minimum([], X, X).
 
% astuce d'initialisation de la recherche,
% le premier élément de la liste est forcément le plus petit 
minimum([A|B],[],Y) :- minimum(B, A, Y). 
 
% ensuite si le premier élément est le plus petit
% on continue en remplaçant X par la A
% sinon on continue avec la même valeur de X
minimum([A|B], X, Y) :-
	A =< X -> minimum(B, A, Y); minimum(B, X, Y).

[SteelBox]

Arg !
C'était juste une erreur de frappe, j'avais mis mininum :-(

C'est corrigé :

Code :

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

1
2
3
 
minimum(D,[D]).
minimum(X,[A|B]):- minimum(Y,B),minimum(A,Y,R),X is R.

Ta solution est équivalente en tout cas, je pense pas que l'une des 2 soit meilleure, qu'en penses-tu ?
Merci

[Trap D]

Salut
J'ai essayé ton bout de code, mais ça me donne des erreurs. Pourrais-tu poster ton code complet ?
Pour déterminer la meilleure il faudrait regarder l'arbre de démonstration.

[SteelBox]

Pardon, voici le code complet (j'ai pas recopié le minimumentre 2 entiers en fait qui était dans mon premier post ) :

Code :

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

1
2
3
4
5
6
7
 
% minimum entre 2 entiers
minimum(X,Y,X) :- X =< Y.
minimum(Y,X,X) :- X =< Y. 
 
minimum(D,[D]).
minimum(X,[A|B]):- minimum(Y,B),minimum(A,Y,R),X is R.

[Trap D]

Salut

Je me suis amusé à tracer les appels avec ma fonction et la tienne (appelée minimum1)

Trace avec ma fonction
1 ?- minimum([2,5,7,0,8,3,9,10], X).
T Call: (8) minimum([2, 5, 7, 0, 8, 3, 9, 10], [], _G743)
T Call: (9) minimum([5, 7, 0, 8, 3, 9, 10], 2, _G743)
T Call: (10) minimum([7, 0, 8, 3, 9, 10], 2, _G743)
T Call: (11) minimum([0, 8, 3, 9, 10], 2, _G743)
T Call: (12) minimum([8, 3, 9, 10], 0, _G743)
T Call: (13) minimum([3, 9, 10], 0, _G743)
T Call: (14) minimum([9, 10], 0, _G743)
T Call: (15) minimum([10], 0, _G743)
T Call: (16) minimum([], 0, _G743)
T Exit: (16) minimum([], 0, 0)
T Exit: (15) minimum([10], 0, 0)
T Exit: (14) minimum([9, 10], 0, 0)
T Exit: (13) minimum([3, 9, 10], 0, 0)
T Exit: (12) minimum([8, 3, 9, 10], 0, 0)
T Exit: (11) minimum([0, 8, 3, 9, 10], 2, 0)
T Exit: (10) minimum([7, 0, 8, 3, 9, 10], 2, 0)
T Exit: (9) minimum([5, 7, 0, 8, 3, 9, 10], 2, 0)
T Exit: (8) minimum([2, 5, 7, 0, 8, 3, 9, 10], [], 0)

X = 0

Yes

Trace avec ta fonction :

[debug] 2 ?- minimum1(X, [2,5,7,0,8,3,9,10]).
Call: (7) minimum1(_G579, [2, 5, 7, 0, 8, 3, 9, 10]) ? creep
Call: (8) minimum1(_L189, [5, 7, 0, 8, 3, 9, 10]) ? creep
Call: (9) minimum1(_L210, [7, 0, 8, 3, 9, 10]) ? creep
Call: (10) minimum1(_L231, [0, 8, 3, 9, 10]) ? creep
Call: (11) minimum1(_L252, [8, 3, 9, 10]) ? creep
Call: (12) minimum1(_L273, [3, 9, 10]) ? creep
Call: (13) minimum1(_L294, [9, 10]) ? creep
Call: (14) minimum1(_L315, [10]) ? creep
Exit: (14) minimum1(10, [10]) ? creep
Call: (14) minimum1(9, 10, _L316) ? creep
^ Call: (15) 9=<10 ? creep
^ Exit: (15) 9=<10 ? creep
Exit: (14) minimum1(9, 10, 9) ? creep
^ Call: (14) _L294 is 9 ? creep
^ Exit: (14) 9 is 9 ? creep
Exit: (13) minimum1(9, [9, 10]) ? creep
Call: (13) minimum1(3, 9, _L295) ? creep
^ Call: (14) 3=<9 ? creep
^ Exit: (14) 3=<9 ? creep
Exit: (13) minimum1(3, 9, 3) ? creep
^ Call: (13) _L273 is 3 ? creep
^ Exit: (13) 3 is 3 ? creep
Exit: (12) minimum1(3, [3, 9, 10]) ? creep
Call: (12) minimum1(8, 3, _L274) ? creep
^ Call: (13) 8=<3 ? creep
^ Fail: (13) 8=<3 ? creep
Redo: (12) minimum1(8, 3, _L274) ? creep
^ Call: (13) 3=<8 ? creep
^ Exit: (13) 3=<8 ? creep
Exit: (12) minimum1(8, 3, 3) ? creep
^ Call: (12) _L252 is 3 ? creep
^ Exit: (12) 3 is 3 ? creep
Exit: (11) minimum1(3, [8, 3, 9, 10]) ? creep
Call: (11) minimum1(0, 3, _L253) ? creep
^ Call: (12) 0=<3 ? creep
^ Exit: (12) 0=<3 ? creep
Exit: (11) minimum1(0, 3, 0) ? creep
^ Call: (11) _L231 is 0 ? creep
^ Exit: (11) 0 is 0 ? creep
Exit: (10) minimum1(0, [0, 8, 3, 9, 10]) ? creep
Call: (10) minimum1(7, 0, _L232) ? creep
^ Call: (11) 7=<0 ? creep
^ Fail: (11) 7=<0 ? creep
Redo: (10) minimum1(7, 0, _L232) ? creep
^ Call: (11) 0=<7 ? creep
^ Exit: (11) 0=<7 ? creep
Exit: (10) minimum1(7, 0, 0) ? creep
^ Call: (10) _L210 is 0 ? creep
^ Exit: (10) 0 is 0 ? creep
Exit: (9) minimum1(0, [7, 0, 8, 3, 9, 10]) ? creep
Call: (9) minimum1(5, 0, _L211) ? creep
^ Call: (10) 5=<0 ? creep
^ Fail: (10) 5=<0 ? creep
Redo: (9) minimum1(5, 0, _L211) ? creep
^ Call: (10) 0=<5 ? creep
^ Exit: (10) 0=<5 ? creep
Exit: (9) minimum1(5, 0, 0) ? creep
^ Call: (9) _L189 is 0 ? creep
^ Exit: (9) 0 is 0 ? creep
Exit: (8) minimum1(0, [5, 7, 0, 8, 3, 9, 10]) ? creep
Call: (8) minimum1(2, 0, _L190) ? creep
^ Call: (9) 2=<0 ? creep
^ Fail: (9) 2=<0 ? creep
Redo: (8) minimum1(2, 0, _L190) ? creep
^ Call: (9) 0=<2 ? creep
^ Exit: (9) 0=<2 ? creep
Exit: (8) minimum1(2, 0, 0) ? creep
^ Call: (8) _G579 is 0 ? creep
^ Exit: (8) 0 is 0 ? creep
Exit: (7) minimum1(0, [2, 5, 7, 0, 8, 3, 9, 10]) ? creep

X = 0

Yes

[SteelBox]

Est ce qu'on peut se fier au nombre d'appel pour comparer 2 règles ? En tout cas, il y a largement moins d'appels chez toi.
Ce qui m'étonne, c'est qu'il n'y a pas l'appel à A<=X dans ton trace alors qu'avec le trace de mon programme :

Call: (12) 0=<3 ? creep

Autre chose, j'essais actuellement d'implémenter une heuristique dans mon jeu de taquin afin d'introduire moi même l'ordre de parcours de l'arbre.

J'ai déjà la règle :

findall(R,suivant(E,A,R,[]),L).

Elle me retourne dans L toutes les listes qui sont posibles dans l'état actuelle.
Si par exemple, j'ai ([1,2,3,4,0,6,7,8,9], il me retourne entre autre :

[1, 2, 3, 0, 4, 6, 7, 8, 9]

Le problème, c'est que L est une liste et que je veux passer à une autre règle : l'état initial, une liste final et un résultat H qu'il va compléter et que je devrais minimiser. Donc, je dois appeler cette règle pour chaque liste dans L et je dois ensuite minimiser le résultat H.
Comment faire ? Je n'ai aps encore d'idée. J'ai essayé avec findall mais sans succès, ile faut que je puisse prendre chaque membre de la liste L, non ?

Merci

[Trap D]

Pourrais-tu donner un exemple de ce que tu veux, car là, j'avoue que j'ai rien compris

[SteelBox]

En fai, je pars d'une liste initiale qui est : [1,2,3,4,0,6,7,8,9].
La règle "suivant" me donne les actions possibles sur cette liste avec la liste qui résulte de cette action.
Par exemple, si j'applique l'action h(haut) sur ma liste, j'obtiendrai :

[1,0,3,4,2,6,7,8,9]

Le 0(case vide du taquin) est monté et le 2 est descendu.

Pour avoir toutes les listes possibles, je fais donc :

Code :

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

findall(R,suivant(E,A,R,[]),L).

J'obtiens le résultat dans L (une liste de toutes les listes possibles, dont celle citée plus haut.

Ce que je veux, c'est ajouter une heuristique pour savoir quel action je dois faire (haut, bas gauche ou droite). J'ai donc fait une règle qui me retourne un résultat (je l'ai appelé H dans le précédent post) en fonction de la liste initiale : [1,2,3,4,0,6,7,8,9] et d'une liste finale.
Déjà, il faut que je puisse appeler cette règle pour chaque liste de L et ensuite appliquer ma règle minimum afin de récupérer l'action à effectuer et/ou la liste finale.

Est ce plus clair ?
Merci

[Trap D]

Je ne suis pas sûr d'avoir tout bien compris.

Déjà, il faut que je puisse appeler cette règle pour chaque liste de L et ensuite appliquer ma règle minimum afin de récupérer l'action à effectuer et/ou la liste finale.

Le prédicat

sublist(+Pred, +List1, ?List2)
Unify List2 with a list of all elements of List1 to which Pred applies.

n'est pas applicable ?

[SteelBox]

En fait je ne crois pas. Par exemple, si j'ai L=[ [1,2], [3,4]], je veux appliquer ma fonction heuristique avec [1,2] puis [3,4]. Il me faut faire une sorte de for ...

[Trap D]

Pourquoi, il suffit que ton prédicat réussisse à chaque fois, non ?
Sinon tu as maplist.

[SteelBox]

Alors en fait, j'ai fait une procédure qui prend une liste de listes en paramètre et refait elle même le minimum sauf que j'ai un problème sur la syntaxe en prolog.

Voici la règle :

Code :

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

1
2
3
 
chercheMin(E,[[C]],M):-coefDesordre(E,C,M). /* première clause */
chercheMin(E,[[C]|AutresListes],M):-chercheMin(E,AutresListes,M),coefDesordre(E,C,R),minimum(E,R,M2),M is M2.

Voici comment je l'appelle en test (je veux l'appeler ensuite dans un autre règle mais ca ne marche pas) :

chercheMin([1,2,3,4,0,6,7,8,9],[[0,1,3,4,2,6,7,8,9]],R).

Je pensais que ma première clause serait appellée mais non, et je ne vois pas pourquoi ?

[Trap D]

Salut
Je pense que tu devrais les appeler de cette manière tout simplement:

Code :

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

1
2
3
% en enlevant une paire de crochets, C est une liste
chercheMin(E,[C],M):-coefDesordre(E,C,M). /* première clause */
chercheMin(E,[C|AutresListes],M):-chercheMin(E,AutresListes,M), coefDesordre(E,C,R),minimum(E,R,M2),M is M2.

Celà ne marche pas ?
J'ai commencé à réfléchir à la résolution d'un taquin, je m'oriente vers une solution du style,

ranger la première ligne
ranger les deux derniers nombres de la première colonne.
ranger les deux derniers nombres de la deuxième colonne.
ranger les deux derniers nombres de la troisième colonne.

C'est ce que j'avais fait en C, mais là je manque de pratique du Prolog.

Je viens de voir cette règle :

Code :

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

chercheMin(E,[C|AutresListes],M):-chercheMin(E,AutresListes,M), coefDesordre(E,C,R),minimum(E,R,M2),M is M2.

Je ne suis pas bien sûr qu'elle puisse fonctionner, à cause de M, celui ci étant unifié avec M2 à chaque appel de ChercheMin, donc tu perds des valeurs (je peux me tromper, je ne vois pas tout ton code).

[SteelBox]

Oui, mais j'ai besoin de prendre en paramètre une liste de listes, comment faire ?
Sinon, il faut que je fasse un "for" dans la clause appelante pour parcourir chaque liste de ma liste. Tu vois le problème ?
Merci

[Trap D]

Je vois le problème, mais je ne pense pas pouvoir le résoudre rapidement, je pars ce soir pour une semaine de vacances. Bon courage
Je crois que tu devrais te pencher sur la manière de traiter les listes en Prolog.
As-tu l'excellent bouquin "L'art de Prolog" de Sterling et Shapiro ?

[SteelBox]

C'est bon, le problème est résolu.

En voici un autre surement le dernier. En fait, la clause ci-dessous fonctionne mais je pense sincèrement qu'il ya beaucoup mieux.
Le but est d'enlever de la liste initiale (premier paramètre) les états que l'on a déjà vus et qui sont stockés dans Vu. Le résultat est ensuite fournis dans le deuxième paramètre.

Code :

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

1
2
3
nonDejaVu([],[],_).
nonDejaVu([A|B],Lf2,Vu):-nonDejaVu(B,Lf,Vu),not(member(A,Vu)),append(Lf,[A],Lf2),!.
nonDejaVu([_|B],Lf,Vu):-nonDejaVu(B,Lf,Vu).

Le problème ici est que je dois tout dépiler pour initialiser la deuxième liste à []. Ensuite j'ajoute si l'élément courant s'il n'est pas dans Vu (not member...).
Par contre, sans la troisième clause, je n'aurais pas un résultat qui soit vrai, d'ou la troisième clause (celle qui me gène).
Voyez vous une autre solution ?

Merci

[Trap D]

Salut

Je te propose cette version

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
% oter(Arg1, Arg2, Arg3, Arg4)
% Arg1 liste des états à traiter
% Arg2 liste de référence contenant les états dejà rencontrés
% Arg3 liste en construction contient les états corrects, au départ c'est []
% Arg4 recupère la liste définitive
% appel par oter(ATester, Vu, [], X).
 
% quand la liste à tester est vide, 
% on unifie les deux derniers paramètres
oter([], _, X, X).
 
% On regarde le premier élément de la liste à tester
% s'il est présent dans la liste Vu, 
%     on continue l'opération oter avec B et les autres arguments
% sinon
%    on mémorise A dans X en utilisant une liste intermédiaire X1 
%    et on continue avec B, Vu, X1 et Y
oter([A|B], Vu, X, Y) :-
	member(A, Vu) -> oter(B, Vu, X, Y);(append([A], X, X1), oter(B, Vu, X1, Y)).

[SteelBox]

Encore une fois, merci pour cette version :-)