Parcours d'un tableau en C
Fermé
DCTProgra
-
9 janv. 2018 à 14:45
mamiemando Messages postés 33435 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 18 décembre 2024 - 28 févr. 2018 à 12:19
mamiemando Messages postés 33435 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 18 décembre 2024 - 28 févr. 2018 à 12:19
A voir également:
- Parcours d'un tableau en C
- Tableau croisé dynamique - Guide
- Tableau ascii - Guide
- Comment faire un tableau - Guide
- Trier un tableau excel - Guide
- Comment imprimer un tableau excel sur une seule page - Guide
1 réponse
mamiemando
Messages postés
33435
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
18 décembre 2024
7 810
28 févr. 2018 à 12:19
28 févr. 2018 à 12:19
Bonjour,
L'idéal serait de traduire ta matrice sous la forme d'un graphe pondéré orienté :
Une fois le graphe construit, il suffit d'utiliser l'algorithme de Dijkstra. Le sommet source correspond à celui associé à la case 1. Une fois l'arbre de plus courts chemins calculés, il suffit d'extraire la branche qui emmène au sommet associé à la case 2. Note que dans le cas où tu pars sur cet algorithme, tu as meilleur temps de représenter ton graphe par une matrice A, ou la case A[u][v] contient le poids de l'arc connectant le sommet u au sommet v du graphe. Tu aurais donc typiquement A[u][v] == 1 si la case associée au sommet u est voisine de la case associée au sommet v et A[u][v] = INFINITY (avec INFINITY une valeur très grande) dans le cas contraire.
D'autres algorithmes pourraient faire l'affaire une fois le graphe construit. Par exemple un simple BFS (ou un DFS) peut permettre de trouver un chemin mais calculerait un chemin sous optimal dans le cas général. À noter que l'algorithme de Dijkstra est une version améliorée de BFS.
Note aussi que dans ton cas ton graphe peut être vu comme non orienté (A[u][v] == A[v][u]) et donc tu pourrais considérer par exemple l'algorithme de Prim et extraire de l'arbre couvrant un chemin (sous optimal dans le cas général).
Bref le sujet est très souple, et tout dépend du compromis que tu cherches (entre facilité de programmation et optimalité).
Bonne chance
L'idéal serait de traduire ta matrice sous la forme d'un graphe pondéré orienté :
- chaque case dont la valeur diffère de 9 correspond à un sommet
- chaque direction (nord, ouest, est, sud) connectant deux cases dont la valeur diffère de 9 correspond à un arc
- comme tous les mouvements ont le même coût, on mettrait le même poids (strictement positif) sur chacun des arc (par exemple 1).
Une fois le graphe construit, il suffit d'utiliser l'algorithme de Dijkstra. Le sommet source correspond à celui associé à la case 1. Une fois l'arbre de plus courts chemins calculés, il suffit d'extraire la branche qui emmène au sommet associé à la case 2. Note que dans le cas où tu pars sur cet algorithme, tu as meilleur temps de représenter ton graphe par une matrice A, ou la case A[u][v] contient le poids de l'arc connectant le sommet u au sommet v du graphe. Tu aurais donc typiquement A[u][v] == 1 si la case associée au sommet u est voisine de la case associée au sommet v et A[u][v] = INFINITY (avec INFINITY une valeur très grande) dans le cas contraire.
D'autres algorithmes pourraient faire l'affaire une fois le graphe construit. Par exemple un simple BFS (ou un DFS) peut permettre de trouver un chemin mais calculerait un chemin sous optimal dans le cas général. À noter que l'algorithme de Dijkstra est une version améliorée de BFS.
Note aussi que dans ton cas ton graphe peut être vu comme non orienté (A[u][v] == A[v][u]) et donc tu pourrais considérer par exemple l'algorithme de Prim et extraire de l'arbre couvrant un chemin (sous optimal dans le cas général).
Bref le sujet est très souple, et tout dépend du compromis que tu cherches (entre facilité de programmation et optimalité).
Bonne chance
