Discussion :

[Treuze]

Bonjour,

Je travaille sur un logiciel de recherche d'itinéraires pour un réseau de bus.

Je dois d'abord calculer tous les chemins possibles pour aller d'un arrêt A à un arrêt B.

J'ai donc representer ce système par une matrice de booléen. Par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
   A B C D E F G H
A |0 1 0 0 0 1 0 0|
B |0 0 1 0 0 0 0 0|
C |0 0 0 0 0 0 0 0|
D |0 0 0 0 0 0 0 1|
E |0 0 0 0 0 0 1 0|
F |0 0 0 1 1 0 0 0|
G |0 0 0 0 0 0 0 0|

Cette matrice me sert à modéliser une sorte de graphe dirigé : de A je peux aller en B, de B je peux aller en C ...

Mais voilà, à part explorer tous les chemins possibles afin de voir si il arrive à mon arrêt final, je ne vois pas d'autres solutions.

Est ce qu'il y aurai une representation plus rapide et/ou moins couteuse en mémoire qui me permettrai de faire cette opération ?

Est ce qu'il y a une possibilité de réduire cette matrice ? ou est ce qu'il existe un algorithme qui permet de passer outre l'exploration de tous les chemins ?

Merci d'avance !

[PRomu@ld]

Au lieu d'utiliser une matrice d'adjacence, utilise une liste d'adjacence.

Regardes ceci :

http://lapoire.developpez.com/algori...es/graphes.pdf

[Graffito]

ou est ce qu'il existe un algorithme qui permet de passer outre l'exploration de tous les chemins ?

Pour la recherche du meilleur trajet, on pourra opérerer un traitement "concentrique" dans lequel on traite les points en ordre décroissant du temps (ou de la distance) nécessaire pour les atteindre.

Pour commencer, la liste des points à traiter contient seulement le point de départ. Ensuite, pour chacun des points de la liste non encore traité, on regarde chaque adjacence et on l'ajoute à la liste, si elle n'est pas encore traitée. Si elle a dèjà été traitée et si le nouveau chemin est plus rapide (ou plus court), on met à jour le point et on le fait "avancer" dans la liste pour garder l'ordre de tri.

[Treuze]

Mercibeaucoup, je vais jeter un oeil là dessus