| Popis: |
Les techniques de modelisation basees sur le depla-cement d'agents dans une topologie de type graphe s'averent une approche fructueuse. Beaucoup de modeles lies aux deplacements d'agents utilisent l'algorithme de Dijkstra pour construire, a coup sur, les plus courts chemins. Cependant un probleme majeur de ces modeles est la frequence a laquelle les nombreux agents, durant toute la simulation, utilisent Dijkstra pour construire leurs plus courts chemins entre les positions ou ils se trou-vent et les positions ou ils veulent se rendre. Cette utilisation massive de l'algorithme necessite un grand temps de calcul. Dans cet article, nous proposons un algorithme permettant une optimisation spatiale de la representation informatique d'un graphe (matrice d'adjacence, liste d'adjacence), suivi d'un stockage optimise de tout plus court chemin une fois construit. Cette optimisation evite aux agents d'avoir a reconstruire des chemins deja construits et supprimes. Ce qui reduit considerablement le temps de calcul du a la construction de plus court chemins. |
