Discussion :

[Benoit_T]

Bonjour,

Je travaille sur l'implémentation d'un algorithme de calcul de distanciers et de plus court chemin. Il s'agit d'un algo très récent (2008) et fort complexe.

Je rencontre le problème suivant: par exemple lors du calcul de plus court chemin, j'ai une contrainte annexe sur le graphe qui m'interdit certains enchainements d'arêtes.

Je cherche un algorithme mathématiques me permettant, à partir du graphe routier initial et des informations de manoeuvres interdites à générer un graphe qui préserve les plus courts chemins du graphe initial et dont la structure intègre les restrictions de manoeuvres (grosso modo turn restriction en anglais).

Soit l'exemple suivant où le chemin u --> v --> w est interdit:


En fait à partir du graphe initial (à gauche), en générant la structure de droite, on empêche le passage u --> v --> w. v1 et v2 étant considérés identiques. Cependant, un demi tour est effectué sur l'arête v <--> w au niveau de w or je n'ai pas le droit de réaliser de demi-tour !

J'ai bien une idée d'algorithme pour empêcher tous ces demis tours. Cependant, ma solution est itérative et fait exploser le nombre de sommet du graphe et augmente aussi le degré moyen du graphe. C'est impensable vu la taille des graphes sur lesquels je travaille (100 méga-arêtes +).

Quelqu'un connait-il un algorithme performant pour empêcher les enchainement de deux arêtes en générant une nouvelle structure de graphe?

Je précise qu'en terme de densité, les arêtes caractérisées par les restrictions de manœuvre représentent entre 1 et 10 % des arêtes du graphe.

Enfin je ne peux pas modifier l'algorithme de plus court chemin pour qu'il intègre "inline" les vérifications de restriction. En fait j'ai démontrer que ces vérifications si elles sont faites durant le calcul augmente la taille de espaces de recherches et le temps de calcul par 4*dm (dm étant le degré moyen du graphe) .

Quelqu'un a-t-il des suggestions pour résoudre ce (joli) problème?
Une solution serait peut être l'utilisation de graphe duals linéaires mais je n'y connais pas grand chose ...

Avis aux amateurs de casse-têtes !

[benDelphic]

d'habitude moi pour interdire des arcs ou des aretes je pondère par plus ou moins l'infini ... il s'agit d'un cas de minimisation ( plus court chemin ) donc j'aurai mis plus l'infini. de façon à ce qu'on ne puisse pas choisir le sommet W apres V... il faut remettre l 'ancienne pondération lors de l'étape suivante de l'algorithme .

[millie]

d'habitude moi pour interdire des arcs ou des aretes je pondère par plus ou moins l'infini

Sauf que là, ce ne sont pas des arcs qui sont interdits, mais des chemins complets

[benDelphic]

oui je sais mais un chemin est composé d'arcs . Si on remplace un arc par un ou une suite d'arcs eh ben ce n'est plus le meme chemin !!! lui il appelle ça un détour ... mais pour ne pas changer son problème il crée un nouveau sommet équivalent ... au lieu de ça on interdit à chaque étape les arcs qui créerons le chemins pas voulu...

[SpiceGuid]

mais pour ne pas changer son problème il crée un nouveau sommet équivalent

Je ne suis pas certain qu'il créer vraiment un nouveau sommet.
Il ne fait que changer le chemin u → v → w en u → v → t → v → w.

En fait il insère le cycle v → t → v, généralement ça rallonge le chemin routier, ce qu'il n'a pas le droit de faire si j'ai bien suivi.
La question telle qu'elle est posée n'a pas de solution sur le graphe tel qu'il est proposé.

[Benoit_T]

en fait le problème a été copieusement étudié et la solution la plus censé est de travaillé sur le graphe dual du graphe initial. Pour faire simple, grosso modo, les arêtes du graphe initial deviennent des sommets du graphe dual, c'est un peu plus compliqué en réallité. Le soucis est que la taille du graphe explose (d'un facteur linéaire sur des graphes routier) de tel sorte que je ne puisse pas vraiment me permettre de les utiliser. En fait, pour un "petit" graphe d'un million d'arêtes, le graphe dual en compte 6,5 millions ...