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 :

deplacer arbres


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre à l'essai
    Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5
    Par défaut deplacer arbres
    salut
    j ai un probleme ou j ai un tableau(de dimensiosn carrees) et dans ce tableau j ai un arbre que je veux deplacer d une position a une autre pour cela j ai 5 mouvements a ma diposition :
    haut : qui deplace mon arbre d un cran vers le haut
    bas : idem mais vers le bas
    gauche : idem vers la gauche
    droite : idem vers la droite
    rotation : qui tourne l arbre dans le sens des aiguille d une montre de 90 degres

    et mon probleme est de trouver un chemin(pas forcement l optimal) du depart jusqu a l arrivee et bien sur il y a des obstacles sur le chemin et les mouvements ne peuvent se faire que si il n y pas d obstacles les empechant

    Exemple :
    B 0 0 1 1
    B 0 0 0 0
    B 0 0 0 0
    1 1 0 0 0
    E E E 0 0
    la ligne des B represente le placement de l arbre au depart

    un des chemin est
    droite,droite,bas,droite,tourner,bas,bas,gauche,gauche;

    j espere que j ai ete suffisament claire et merci d avance.
    la lignes des E represente le placement de l arbre a l arrivee
    0 : emplacement vide
    1 : obstacles

  2. #2
    Membre chevronné
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 52
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Par défaut
    Est-ce qu'un arbre est toujours un segment (un tronc?) ou est-ce que cela peut être un objet plus compliqué?

    Quand on tourne y a-t-il des contraintes autres que: l'emplacement de départ et d'arrivée sont libres?

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
     X00        000
     X10        010
     X00        XXX
    est-il possible?

  3. #3
    Membre chevronné
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 52
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Par défaut
    Quoi qu'il en soit, on peut représenter un graphe des états possibles où les noeuds (les états) sont définis par (x,y,p). x et y sont les coordonnées de l'arbre et p est la position verticale ou horizontale.

    On relie par un arc deux états s'il est possible de passer d'un état à l'autre par un déplacement/rotation et on cherche s'il y a un chemin dans ce graphe d'états.

    Si le labyrinthe initial est très grand, on a intérêt à faire du A* sinon, n'importe quel algo de chemin fait l'affaire.

  4. #4
    Membre à l'essai
    Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5
    Par défaut
    pour la rotation elle se fait par rapport au centre de l arbre qui a toujours une longueur impaire pour justement toujours avoir un centre mais aussi la rotation ne peut ce faire que si rien ne la gene c est a dire:

    avant rotation:

    0 0 0 0
    0 0 B 0
    0 0 B 0
    1 0 B 0

    la rotation est possible car il n y a pas de "1" sur la zone en gras

    si la map etait comme ca :
    0 0 0 0
    0 1 B 0
    0 0 B 0
    1 0 B 0

    le "1" souligne n empeche la rotation la rotation car l arbre tourne dans le sens des aiguilles d une montre maissi la map etait comme ca :

    0 0 0 0
    0 0 B 0
    0 0 B 0
    1 1 B 0

    alors le 1 souligne empecherait la rotation de meme pour la droite de l arbre en haut = genant et en bas =pas genant

  5. #5
    Membre à l'essai
    Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5
    Par défaut
    le probleme est que je na sais pas utiliser les graphes donc....difficile de mettre en applications ton aide.

  6. #6
    Membre chevronné
    Profil pro
    Enseignant
    Inscrit en
    Avril 2004
    Messages
    440
    Détails du profil
    Informations personnelles :
    Localisation : France, Puy de Dôme (Auvergne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2004
    Messages : 440
    Par défaut
    A mon avis tu devrais chercher des cours dessus (je me souviens par ex en avoir fait beaucoup en automatisme) ou si tes arbres sont assez grands efectivement l'algo A* est tout indiqué... Et là il y a vraiment plein de doc partout, c'est un algo ultra classique, bien que un peu compliqué au premier abord, il finit par se laisser dompter ....

    A+

  7. #7
    Membre chevronné
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 52
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Par défaut
    Citation Envoyé par brennus
    le probleme est que je na sais pas utiliser les graphes donc....difficile de mettre en applications ton aide.
    Il y a plein de références sur le web.
    Par exemple dans wikipedia:
    http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
    Sinon, ce livre est bien
    http://www.univ-valenciennes.fr/sp/sevaux/graphes/

Discussions similaires

  1. Des déformations pas jolie lors du deplacement de la cam
    Par scorpiwolf dans le forum OpenGL
    Réponses: 4
    Dernier message: 01/11/2002, 13h12
  2. Qu'est ce qu'un arbre
    Par sandrine dans le forum C
    Réponses: 8
    Dernier message: 23/10/2002, 13h12
  3. créer une arborescence windows sous forme d'arbre java
    Par chupachoc dans le forum Composants
    Réponses: 3
    Dernier message: 01/10/2002, 16h48
  4. [VB6] [Form] Interdire le déplacement d'une feuille
    Par Loïc dans le forum VB 6 et antérieur
    Réponses: 9
    Dernier message: 23/09/2002, 15h02
  5. arbre de parcour d'arborescence windows
    Par chupachoc dans le forum Composants
    Réponses: 7
    Dernier message: 09/09/2002, 08h09

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