Sujet Précédent Sujet Suivant

DFG

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008 - 24 févr. 2006 à 09:39
rambc Messages postés 224 Date d'inscription mercredi 21 avril 2004 Statut Membre Dernière intervention 29 mars 2009 - 24 févr. 2006 à 12:23
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/36216-dfg
rambc Messages postés 224 Date d'inscription mercredi 21 avril 2004 Statut Membre Dernière intervention 29 mars 2009
24 févr. 2006 à 12:23
On parle de MATRICE CREUSE quand elles ont plein de zéros. Ceci peut être la traduction de SPARSE MATRIX.
cs_GoldenEye Messages postés 527 Date d'inscription vendredi 14 septembre 2001 Statut Membre Dernière intervention 6 octobre 2008 4
24 févr. 2006 à 10:34
Pour les PriorityQueues avec AStar
http://www.cppfrance.com/code.aspx?ID=33092
cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
24 févr. 2006 à 09:39
L'algo de Dijkstra impose que les poids entre les noeuds ne soient pas négatifs, mais ils peuvent être nuls. Tu devrais donc associer une valeur négative (par exemple, -1) aux poids des connexions absentes. Tu ne te priverais alors pas de la liberté de faire des connexions "gratuites", ce qui peut arriver (téléporteur par exemple).

Aussi, je ne pense pas que ta structure de données pour sauvegarder les poids soit appropriée. Ton graphe est "sparse" (en anglais): il y a beaucoup de -1 (enfin, de 0) dans ton tableau, en réalité, il y a relativement peu de connexions par rapport au maximum possible (tout le monde connecté à tout le monde dans les deux sens: n*(n-1) ~n² beaucoup. Pour ce genre de graphe, on préfèrera des "adjacency lists" plutôt qu'une "adjacency matrix" comme tu as fait ici. C'est plus performant point de vue mémoire (mais de fait (un peu) plus lent et (bcp) plus chiant à gérer). Ton tableau ne tiendra plus la route au-delà de 10000 noeuds, et on y est vite: regarde une carte de jeu de 100 x 100 cases. Ca ferait 10000 * 9999 * sizeof(int) octets = 400 Mo réservés à ton graphe, alors que de façon évidente, il y aurait, ds un jeu en cases, un nombre borné de cases attachées à une autre. Mais la remarque ne se limite pas aux jeux sur grilles: c'est vrai pour tous les graphes "sparses" (je sais pas le dire en français, dsl :().

Tu trouveras très facilement bcp d'infos sur les adjacency lists sur internet. Pour le reste, si je peux te donner un conseil si tu désires approfondir le pathfinding,

- cherche des infos sur l'usage des files à priorité (priority queue) dans l'algo de dijkstra: ça te booste cet algo, un truc de malade :D
- essaye d'écrire ton algo de façon générique, et pour chaque type d'implémentation, fournit un lot de fonctions différentes: get_next_node(), get_cout(n, m) etc etc. Là, tu gères le fait que ce soit une matrice, ou des listes, ou encore le fait que tu as une file à priorités. Ca te permettra de facilement essayer des améliorations (comme le A* aussi) et de les comparer aux versions précédentes sans devoir récrire tout l'algo: le noyau de base sera toujours le même.

Le meilleur pour ça, c'est d'utiliser une méthode virtuel dijkstra(...) avec des méthodes virtuelles pures get_next_node() etc qui sont implémentées différemment dans différentes classes héritées de celle-ci.
Rejoignez-nous