Discussion :

[titi_lion]

Bonjour je voudrais calculer la plus petite distance entre deux listes.
Je m'explique; j'ai un état initial et un état final et des opérateurs pour passer d'un état à l'autre.Mais je voudrais juste récupérer le plus court chemin en calculant la distance entre l'état final et l'état courant.
Je sais que je dois implémenter l'algorithme A*, mais je n'arrive pas vraiment à le faire .
Merci .

[Trap D]

Montre déjà ce que tu as écrit ...
Et donnes plus de précisions sur ton problème.

[titi_lion]

Mon pb se rapproche plus ou moins du problème des cruches .Il tourne normalement mais il utilise soit le parcours en largeur ou le parcours en profondeur.Ce que je voudrais c'est de l'améliorer afin qu'il n'explore pas tous les chemins en utilisant une heuristiqie qui permet que de prendre celui qui est le minimum.
J'ai fait des recherches et j'ai trouvé des info sur l 'algorithme A*.
Et j'ai trouvé l'implémentation suivante:
Heuristique:
minimiser
F(E) = L + MP
avec
E= état courant
L= longueur du chemin de l’état initial à E
MP= le nombre de carrés mal placés par rapport à la configuration finale.
Pour calculer la longeur je vais utiliser le predicat longueur

Code :

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

1
2
3
longueur:-([], [],0).
longueur:-([T|Q],[T1|Q1],D):-longueur(Q,Q1,D).
longueur:-([T|Q],[T1|Q1],M):-longueur(Q,Q1,D),M is D+1.

je calcule le minimum comme suit:

Code :

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

1
2
3
min([X],X).
min([X|L],X) :- min(L,Y), X<Y.
min([X|L],Y) :- min(L,Y), X>=Y.

mon problème est de trouver comment implémenter MP le nombre de carrés mal placés par rapport à la configuration finale.

[Trap D]

Je ne comprends pas bien l'intérêt de ces deux clauses :

Code :

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

1
2
longueur:-([T|Q],[T1|Q1],D):-longueur(Q,Q1,D).
longueur:-([T|Q],[T1|Q1],M):-longueur(Q,Q1,D),M is D+1.

L'entête est exactement la même au nom près de variable près.
peut-être est-ce ?

Code :

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

1
2
3
4
longueur:-([T|Q],[T|Q1],D):- <= ici c'est le même premier élément de liste 
  longueur(Q,Q1,D).
longueur:-([T|Q],[T1|Q1],M):- <= ici ce n'est pas le même
  longueur(Q,Q1,D),M is D+1.

Si tu utilises SWI-Prolog, tu as un prédicat min_list

Code :

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

1
2
min_list(+List, -Min)
    True  if Min is the smallest number in List.

[titi_lion]

je pense que c'est juste une erreur de syntaxe je voulais écrire:

Code :

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

1
2
longueur([T|Q],[T1|Q1],D):-longueur(Q,Q1,D).
longueur([T|Q],[T1|Q1],M):-longueur(Q,Q1,D),M is D+1.

je vais essayer d'utiliser minlist comme vous avez dit.

[Trap D]

Code :

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

1
2
3
 
longueur([T|Q],[T1|Q1],D):-longueur(Q,Q1,D).
longueur([T|Q],[T1|Q1],M):-longueur(Q,Q1,D),M is D+1.

Je continue à ne pas comprendre ces deux clauses qui ont exactement la même en-tête, on peut intervertir D et M dans la deuxième clause sans rien changer à sa sémantique.
Que sont-elle censées faire ?

[titi_lion]

finalement le predicat longueur ne m'a servi à rien du tout

[AdelBenHassine]

titi_lion, si vous avez trouvé une solution, merci de me la passer parce que en faite je travail sur un prb pareil. merci d'avance

[Trap D]

titi_lion, si vous avez trouvé une solution, merci de me la passer parce que en faite je travail sur un prb pareil. merci d'avance

Inutile de déterrer une discussion d'il y a 6 ans !
Postez-votre code est vos questions plutôt que demander une solution toute faite !