IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Pathfinding sur un graphe incluant des règles de circulation routière


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre très actif Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    Juillet 2006
    Messages
    728
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : Juillet 2006
    Messages : 728
    Par défaut Pathfinding sur un graphe incluant des règles de circulation routière
    Bonjour,

    Existe-t'il s'il vous plait un algorithme de pathfinding sur un graphe du genre "A star" incluant certaines règles de circulation ?

    Par exemple : possibilité de faire un demi tour sur un sommet de type "cul de sac", mais interdiction sur un sommet de type "virage" ou "carrefour".

  2. #2
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2008
    Messages
    26 772
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : Août 2008
    Messages : 26 772
    Par défaut


    Ne s'agit-il pas plutôt de règles à appliquer quand tu crées ton graphe ? Mon idée : les nœuds du graphe représentent les routes à emprunter, avec des arêtes pour chaque carrefour, qui indiquent les transitions possibles.

    Sinon, des Coréens ont déjà développé des extensions de Dijkstra et Floyd-Warshall pour ces cas : https://patents.google.com/patent/KR100653036B1/en. (La différence entre Dijkstra et A*, c'est une distance heuristique, ça devrait donc aussi s'appliquer.)

    En parlant de routes, A* n'est pas le plus approprié pour ce genre de graphe. Regarde du côté des construction hierarchies (CH).
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  3. #3
    Membre très actif Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    Juillet 2006
    Messages
    728
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : Juillet 2006
    Messages : 728
    Par défaut
    Merci beaucoup je vais creuser de ce côté

  4. #4
    Membre très actif Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    Juillet 2006
    Messages
    728
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : Juillet 2006
    Messages : 728
    Par défaut
    Bonjour,

    Voici un exemple de graphe orienté simplifié :

    Nom : graph.gif
Affichages : 197
Taille : 11,1 Ko

    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 ?

    Modèle compact. 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

  5. #5
    Expert confirmé Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 293
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 293
    Par défaut
    Bonjour

    Parce que ton vrai graphe, c'est ça :
    Nom : output_fdp.jpg
Affichages : 144
Taille : 63,8 Ko
    Ou ça:
    Nom : output_dot.jpg
Affichages : 146
Taille : 48,3 Ko

  6. #6
    Membre très actif Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    Juillet 2006
    Messages
    728
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : Juillet 2006
    Messages : 728
    Par défaut
    Merci d'avoir pris le temps de dessiner mon graphe.

    Donc si j'ai bien compris il y a un graphe global pour toutes mes voitures qu'on va nommer G et un graphe propre à chaque voiture qu'on va nommer Gi (avec i compris entre 1 et le nombre de voiture). En effet vu l'interdiction de faire demi tout dans un noeud qui n'est pas un cul de sac, le graphe Gi (dont tu viens de dessiner un exemple) va dépendre de l'orientation et la position initiale de chaque voiture Vi
    Est ce que je vais pas avoir un soucis de mémoire si j'ai spawn 5000 voitures et que G contient 2000 noeuds ?

Discussions similaires

  1. Réponses: 3
    Dernier message: 31/07/2014, 12h17
  2. Réponses: 2
    Dernier message: 18/01/2011, 19h10
  3. Réponses: 7
    Dernier message: 20/03/2007, 16h32
  4. [Excel][Debutant VB] Obtenir des infobulles sur un graphe
    Par Masmeta dans le forum Macros et VBA Excel
    Réponses: 2
    Dernier message: 29/11/2006, 09h21

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo