Voici un exemple de graphe orienté simplifié :
Le triangle rouge est la position et l'orientation initiale de la voiture. Le cercle vert est le nœud de destination.
Je souhaite interdire un demi-tour dans un virage et un carrefour mais je l'autorise dans une impasse (nœud 4).
Le tableau de nœuds (3, 6, 8) est donc interdit.
De même (3, 1, 6, 8) est interdit.
En revanche, (3, 1, 2, 3, 6, 8) et (3, 4, 3, 6, 8) sont autorisés. Ce dernier étant le chemin le plus court.
Comment s'il vous plaît modifier la structure de données de mon graphique et l'algorithme A * (ou Dijkstra) pour atteindre mes objectifs?
On m'a parlé de contractions hiérarchiques et du coup j'ai commencé à lire cet article :
https://drops.dagstuhl.de/opus/vollt...MOS-2020-9.pdf
Vous pensez que le modèle compact répond à ma problématique ?
Le modèle compact [18, 11] conserve les intersections comme sommets, mais associe
une table de virages p × q Tv avec chaque sommet v, où p et q sont les nombres de
arêtes entrantes et sortantes, respectivement. L'entrée Tv(i, j) représente le coût du virage du i-ème
arête entrante e vers le j-ième arête sortante f, c'est-à-dire Tv(i, j) = c(e, f). Pour chaque arête (v, w),
sa queue correspond à un point de sortie en v et sa tête correspond à un point d'entrée en w.
On note v|i la i-ième sortie (ou
point d'entrée) en v et par (v|i, w|j) l'arête dont la queue correspond au i-ième point de sortie en
v et dont la tête correspond au j-ième point d'entrée en w. Le principal avantage de la
modèle compact est sa faible surcharge d'espace puisque les tables de virages peuvent être partagées entre les sommets.
Merci