Bonjour,
 
J'ai décidé de me lancer dans un petit défi de programmation (qui sera peut-etre simple pour certains   ) dont voici les étapes :
 

• Etape 1 - Génération aléatoire d'une matrice

- Une matrice de 5*5 de chiffres aléatoires est générée
 

 

• Etape 2 - Création d'une nouvelle matrice à partir de la première

On génère la matrice 2 avec les régles suivantes :
- On pars du point (1,1)
- On peut se déplacer en haut, en bas, à droite et à gauche uniquement
- Les déplacements se font uniquement d'une case adjacente
- Le déplacement est autorisé uniquement si la valeur du chiffre en (1,1) est supérieur ou égal à la valeur de la case où l'on veut se rendre
 
On arrive à cela :
 

 

• Etape 3 - Calcul du chemin optimal à partir de la matrice précedante

- On calcul un chemin optimal pour aller de la case (1,1) à la case (5,5)
 
Là je coince, je voudrais arriver à cela (meme s'il existe plusieurs chemins optimaux, le programme n'en choisira qu'un aléatoirement) :
 

 
Je ne sais pas comment construire l'algo qui permet d'obtenir ce chemin optimal...
 
Merci pour votre aide.

Un autre exemple d'une génération d'une matrice de départ et du calcul des autres (pour ceux qui ont pas bien compris mes explications)
 

 
Dans ce cas, il n'y a qu'un chemin optimal.

tu fais tous les chemins et tu prend celui qui à le moins de case ...

Ca c'est bon, je suis assez intelligent pour avoir aussi trouvé cette méthode. Le problème c'est pour l'implanter...
 
Je demande pas un algorithme tout pret, mais au minimum la logique d'ensemble de l'algo.  

ben tu prend la premiere case tu autorise d'aller partout sauf de revenir sur ses pas (chemin moisie) et tu fais toutes les directions pour toutes les cases ou tu vas, tu garde juste les chemins qui arrivent au bout et tu prend le plus petit  
 
mais bon c'est super nul comme algorithme (ca rame ca bouffe de la memoire c'est le plus bourrin des algos possible) apres pour opti c'est des maths ...

regarde du coté des algorithme A*. Ca permet de trouver le chemin le plus court sans parcourir tous les chemins (en fait l'algorithme A* est plus général que ça, on l'applique juste dans un cas particulier du labyrinthe ici). Le seul inconveniant de cet algorithme c'est qu'il va parcourir toutes les cases si aucun chemin entre les deux points (depart et arrivé) existe.
 
http://leri.univ-reims.fr/~nocent/lectures/Astar.pdf

 
Merci  

 
Fait le, tu verras que c'est bien plus compliqué que ca a programmer      
Mais merci quand meme  

J'ai fini l'implantation de l'algorithme A*. Mais j'ai un petit probleme :
 

 
En fait ca ne me donne pas forcement le meilleur chemin possible mais "un des meilleurs"
Erreur d'implantation ou l'algorithme A* ne donne pas forcement le meilleur ?    
Sachant que je n'ai pas regardé l'algorithme en lui meme mais j'ai uniquement extrait la logique de l'algorithme à partir des schémas et je l'ai implanter "à ma sauce".
 
   
 
NB : Vous pouvez télécharger le programme ici : http://www.phlos.com/ovh/astar.zip
Il suffit d'appuyer sur ENTRER a chaque fois pour générer une nouvelle matrice.

Par curiosité, ta règle de "- Le déplacement est autorisé uniquement si la valeur du chiffre en (1,1) est supérieur ou égal à la valeur de la case où l'on veut se rendre " elle vient d'où ?

 
De nul part, en fait cette règle c'était pour construire la matrice aléatoire que tu vois sur le dernier screenshot, oublie là  

pour l algortithme de plus court chemin, je te conseille de regarder du cote de Dijkstra, Google va t aider pour ça, par exemple :  
http://brassens.upmf-grenoble.fr/I [...] jkstra.htm
 
c est un des premeirs algo qu on apprend en therie des graphes
 
je l ai deja implémenté en C  à l epoque et une fois que tu sais manipuler des matrices, bah ca va ^^

Merci je vais regarder ça. Mais j'aimerai d'abord savoir si j'ai commis une faute d'implantation ou si l'algo A* ne donne pas forcement le meilleur chemin ?  

A* doit donner le meilleur chemin; ça doit donc être une erreur d'implantation...

 
Es tu sur de ce que tu dis ?
Je viens de faire une recherche sur google, je tombe sur cette page : "http://www.vieartificielle.com/art [...] cle&id=179"
 
Et dans les commantaires je vois ca :

 
Donc je ne suis maintenant plus sur du tout que j'ai bien commis une erreur d'implantation    

A mon avis le gars qui a fait ce commentaire se trompe... Je ne vois rien qui justifie ce qu'il dit dans les dernières images de l'article (je ne l'ai pas lu en entier). Dans l'avant-dernière image, le chemin qui "remonte" après l'obstacle est choquant à première vue, mais dans la légende il est bien écrit que les "diagonales sont aussi coûteuses que les lignes droites" et ce chemin est donc bien optimal.
J'ai vérifié dans mon bouquin d'IA et il est bien précisé que A* est à la fois complet (trouve toujours une solution si elle existe) et optimal (trouve la meilleure solution), à condition que l'estimation de la distance au but ne surestime jamais cette distance...

En fait je ne vois pas comment l'algorithme A* pourrait obtenir le meilleur chemin des la premiere fois...
 
Parcequ'en fait il arrive plusieurs fois lors de l'évalution des noeuds qu'ils ont exactement le meme "poids". Donc dans ce cas, il faut bien qu'il fasse un choix et c pas toujours le "meilleur". Bref je vois pas quoi  

Qu'entends-tu par 'dès la première fois' ? C'est une recherche "best-first"; mais il faut quand-même parfois revenir en arrière et défaire une partie du chemin déjà effectué... D'ailleurs en regardant le chemin généré par ton programme, on dirait que tu le fais mais pas dans tous les cas:

On dirait que tu ne défais pas les noeuds tant que le meilleur noeud trouvé est adjacent au précédent, alors que c'est le noeud adjacent de poids minimum (celui qui a permis d'insérer le noeud trouvé dans la file de priorité si je ne me trompe pas) qui devrait être le prédécesseur. Je sais pas si je suis très clair...

 
on peut aussi utiliser A* avec une heuristique nulle, ça donne dijsktra
à tester, si là encore ça ne donne un chemin pas optimal, ya un pb avec l'implémentation de A*.
 

 
A* ne donne pas forcément le meilleur chemin si l'heuristique n'est pas minorante, mais ici la distance de manhattan devrait toujours l'être.

C'est une question de vocabulaire... Je considérais que A* doit utiliser une heuristique minorante, sinon ce n'est pas A*... Mais vérification faite, tu as raison, on peut utiliser A* avec une heuristique non minorante et ça s'appellerait quand-même A*...