Dijkstra sur un très gros graphe

Bonjour,

Je développe un outil java donnant diverses informations sur un jeu en ligne et la fonctionnalité que j'essaye d'y intégrer en ce moment, c'est le calcul du chemin le plus court entre deux cases.
je pensais donc utiliser l'algorithme de dijkra en lui passant en entrée le graphe de la carte représenté par une matrice d'entier

Néanmoins, je me heurte à un problème.
La carte fait 190 cases sur 190 cases. soit 36100 cases.
ce qui donne une matrice représentant le graphe de 36100 sur 36100 soit plus d'un milliard de cases

Donc rien que le fait d'initialiser mon tableau d'entier

Code:

---

1 2 3

int[][] tab = new int[36100][36100];

---

fait planter la jvm.

Voilà, donc je pars à la pêche aux bonnes idées pour contourner le problème.
Sinon je m'inquiète du temps d'exécution d'un tel calcul, une idée de ce que ça pourrait donner?


Sinon, quelques infos supplémentaires au cas ou:
-la carte du jeu change quotidiennement donc le cout en déplacement d'une case change aussi, ce qui implique que la matrice doit être reconstruite à chaque exécution. Je ne peut donc pas la calculer une bonne fois pour toute.
-il s'agit d'un outil local que les joueurs installent sur leur machine. Donc des bidouilles de la machine utilisateurs sont envisageable mais à éviter autant que possible.

Voilà, merci d'avance pour les réponses :)

Hello,

tu n'as pas du tout besoin d'un tel tableau pour implémenter Dijkstra! Il suffit de 2 listes, qui dans le pire des cas contiennent à elles 2 la totalité des cases. Donc au maximum 36100 cases.

Relis un peu la description de l'algo, et reviens si tu as des questions.

Question perfs, c'est un algorithme qui croit comme n^2, avec n nombre de nœuds du graphe (je crois). Ça risque donc d'être assez lent pour un graphe de ta taille. Utilise plutôt l'algorithme A* qui est la variante optimale de Dijkstra. La différence est l'ajout d'une heuristique qui permet d'estimer les distances et d'améliorer considérablement le temps de calcul dans certains cas. Tu peux étudier cet algo dans un second temps.

Pour info j'ai fait un test sur ma machine (proc@2.67GHz) avec un graphe de 136x136 le temps de calcul pour relier 2 coins opposés est d'environ 8s avec Dijkstra. Avec A*, selon la nature du graphe (simple ou bien tortueux avec de nombreux chemins à évaluer) on va de 8s à 0.01s...

Tu peux également diviser ta "carte" en secteurs, calculer les chemins entre ces secteurs une fois, et ensuite tu n'auras plus qu'à calculer de très petites distances, peu importe le fait que ta carte fasse (10^x)^2.

Exemple:

Ta carte fait 1000*1000 cases: Tu la divises en secteurs de 50*50 (sous-carte). Tu viens de passer d'une carte d'1 million de cases à une carte de 2500 cases.

Tu calcules le chemin entre tous tes secteurs (par exemple pour aller du secteur A au secteur Z il faut passer par le secteur B, D, F, H ).

Ensuite tu n'as plus qu'à calculer, à chaque itération, le chemin entre A et B, puis de B à D, puis de D à F, puis de F à H et finalement de H à Z. Tu peux enregistrer cette donnée sur un fichier.

En gros, au lieu d'avoir 1 calcul sur une matrice de 1000*1000, tu auras au plus 2500 calculs sur des matrices de 50 sur 50.

Le gain de perf est tout simplement énorme.

Bonjour.

déjà, merci pour l'aide :)

comme vous me l'avez suggérez, j'ai essayé de représenter mon graphe autrement que part sa matrice. J'utilise donc une HashMap avec comme clef une case et comme valeur la liste des arcs sortant de la case.

Code:

---

1 2 3

protected HashMap<Case, ArrayList<Arc>> noeuds;

---

les variables d'instance de la classe Case(qui me permet déjà de gérer ma carte pour le reste de l'outil, je ne créé pas de nouvelles cases à mettre dans la hashmap, ce sont des références aux objet existant).

Code:

---

1 2 3 4 5 6 7 8 9 10

public class Case implements Serializable{ public Short terrain; public Short x; public Short y; public Short batiment; public Short niveauBatiment; public Short race; }

---

Et la classe Arc créée pour l'occasion

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

public class Arc implements Serializable { Case arrivee; short cout;   public Arc(Case arrivee, short cout) { super(); this.arrivee = arrivee; this.cout = cout; }     }

---

Néanmoins j'obtiens toujours une erreur du dépassement de la mémoire (java heap space, out of memory) lorsque je remplis la HashMap sur ma machine perso(2 giga de ram proc dual core). L'erreur arrive au bout du traitement d'environs 75 lignes de la carte soit un peu moins de la moitié de la carte.

J'ai fait une sérialisation du hashmap au bout de 30 lignes traités pour avoir une idée de l'espace mémoire utilisé, ça me donne un fichier de 800ko, ce qui pour un traitement complet(mes 190 lignes donc) devrait donner environ 5 mega.

Je viens d'essayer sur mon poste de travail du boulot(4 giga de ram, dual core) et ça passe sans problème avec une création de la hashmap en moins d'une seconde.

Je me demande donc si l'utilisation mémoire de cette façon de faire vous parait raisonnable, le fait que ma machine ne le supporte pas peut'il venir d'un problème de mon pc?

Tes parametres Xms et Xmx sont mis a combien de mega ?

Ah bonne question.
En fait avant ton message je ne savais pas que ça existait.

Donc je vais essayer ce soir voir ce que ça donne en les mettant.
Merci pour la piste:)

Sinon, par curiosité, comment je peux savoir a quelle valeurs sont affecté ses paramètres par défaut?

Citation:

---

Envoyé par ElSpopo

Ah bonne question.
En fait avant ton message je ne savais pas que ça existait.

Donc je vais essayer ce soir voir ce que ça donne en les mettant.
Merci pour la piste:)

Sinon, par curiosité, comment je peux savoir a quelle valeurs sont affecté ses paramètres par défaut?

---

Oui augmente un peu la valeur de xmx genre 256 ou 512 pour etre tranquille.

Je ne suis pas certains mais :

Code:

---

System.err.println("Total memory aivalable : "+Runtime.getRuntime().totalMemory());

---

devrait te retourner la valeur que tu as en Xms. (ou s'approchant).

Sinon par defaut ça doit etre entre 64 et 128 il me semble mais les souvenirs sont rouillés.

Hello,

Je ne sais pas si tu fait référence à mon message, mais je suggérais plutôt d'utiliser un tableau Case[136][136] pour stocker ton graphe.

Tu n'as pas besoin de stocker les nœuds, puisque (si j'ai bien compris) ton graphe est rectangulaire, donc si tu as une case(x, y), tu sais que ses voisins sont (x-1, y-1), (x-1, y), (x-1, y+1) etc ... Ton objet Arc te sert pour stocker le coût, mais cette information peut probablement être déduite de la case de départ et d'arrivée.

Donc tu devrais pouvoir réduire ton usage mémoire de 36100*Case + 36100*ArrayList + 36100*8*Arc à 36100*Case.

Sinon effectivement tu peux simplement monter la RAM maxi allouée à la JVM :)

Citation:

---

Envoyé par vic

Donc tu devrais pouvoir réduire ton usage mémoire de 36100*Case + 36100*ArrayList + 36100*8*Arc à 36100*Case.

---

Oui, je pourrais réduire mon coût en mémoire en ne créant pas d'objets intermédiaire, mais cela m'obligerais à tout calculer à la volée:
-interpréter les coordonnées des cases pour trouver leurs cases adjacentes
-calculer le coût d'une case a une autre(qui dans mon cas dépend de divers paramètres comme le type de la case, la race de mon joueur, le royaume détenant la case)
-faire tourner dijkstra la dessus

Je préfère donc y aller étape par étape et prendre plus de mémoire afin d'éviter de me perdre dans mon code quitte à recoder de façon plus optimale derrière une fois que j'aurais maitrisé le principe.

Sinon la création de ma HashMap passe en augmentant la mémoire,donc je peux maintenant poursuivre sur l'algo.:ccool:

Je mettrais ce que j'ai codé quand je l'aurais fini(si j'ai pas d'autre question entre temps:roll:), ça pourra toujours resservir.

Bon, eh bien ça marche nickel:ccool:

Merci beaucoup pour les conseils.

Je met mon code au cas ou il y aurait des curieux

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

public Chemin calculChemin(Case depart,Case arrivee ){ //liste des noeuds visité HashMap<Case,Chemin> visite = new HashMap<Case,Chemin>(); //liste des noeuds traiter pour lesquels le chemin le plus court est connu HashMap<Case,Chemin> traiter = new HashMap<Case,Chemin>(); //on initialise la liste des noeuds visité avec le noeud de départ visite.put(depart, new Chemin(new ArrayList<Case>(),(short)0)); boolean trouve=false; //tant qu'on a pas trouvé notre chemin le plus court while(!trouve && !visite.isEmpty()){ Case caseProche=null; Chemin dist=null; //on cherche le noeud visité le plus proche du noeud d'origine for(Case caseVisite: visite.keySet()){ if(caseProche==null || visite.get(caseVisite).cout<dist.cout){ dist = visite.get(caseVisite); caseProche = caseVisite; } } //pour ce noeud on vient donc de trouver le chemin optimal //on le met dans la liste des noeud traité traiter.put(caseProche,dist); if(caseProche==arrivee){ trouve=true; break; } //on retire le noeud des noeud visite visite.remove(caseProche); //on récupére les noeud fils de ce noeud //ceux qui ne sont pas encore traité sont ajouté a la liste des noeuds visité for(Arc monArc :noeuds.get(caseProche)){ if(!traiter.containsKey(monArc.arrivee)){ short cout= (short) (dist.cout+monArc.cout); if(!visite.containsKey(monArc.arrivee) || visite.get(monArc.arrivee).cout> cout){ ArrayList<Case> chem = (ArrayList<Case>)dist.trajet.clone(); chem.add(monArc.arrivee); Chemin monChemin=new Chemin(chem,cout); visite.put(monArc.arrivee, monChemin); } } } } if(trouve){ return traiter.get(arrivee); }else{ return null; }   }

---

Ma classe chemin

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

import java.util.ArrayList;   public class Chemin {   public ArrayList<Case> trajet; public short cout;   public Chemin(ArrayList<Case> trajet, short cout) { super(); this.trajet = trajet; this.cout = cout; } }

---