Accueil Ti-Gen Foire Aux Questions Chat sur le chan #tigcc sur IRC
Liste des membres Rechercher Aide
Bienvenue Invité !   Se connecter             Mes sujets   
Administrer
0 membre(s) et 1 visiteur(s) actif(s) durant les 5 dernières minutes Utilisateurs actifs : Aucun membre + 1 visiteur
Avant de poster sur le forum, il y a des régles de bases à respecter pour une bonne entente et un respect de tous.
Veuillez lire la charte du forum.
  :: Index » Forum TI-Nspire » Algorithmie et optimisation » Orientation d'un graphe (7 réponse(s))
./POST DE DEPART (post n°0)   Marquer comme non lu.
LionelA Ecrit le: Samedi 8 janvier 2005 à 19:59 Déconnecté(e)    Voir le profil de LionelA Envoyer un email à LionelA Visiter le site WEB de LionelA Envoyer un message privé à LionelA  


Bon voilà j'ai besoin de savoir si il existe un algorithme capable d'orienter un graphe non orienté :

http://anton.lionel.free.fr/TI68k/graphe1.GIF

Le point en bleu est considéré comme le départ et c'est le seul noeud ayant 2 arcs, les autres en ont 3.

On lui donne l'orientation de départ :

http://anton.lionel.free.fr/TI68k/graphe2.GIF

et le résultat doit être ca :

http://anton.lionel.free.fr/TI68k/graphe3.GIF

S'il vous plaît aidez moi (et si vous pouvez essayez de répondre en langage humain :p (pas trop de termes mathématiques si possible))

note : le graphe ne contient pas de portions non orientables (cf. ici)
Auteur de Mode7 Engine pour ti68k
Auteur de F-ZERO for TI68k
Membre de Orage Studio
Mon site perso : http://www.tigen.org/lionela/
Le gite de mes parents à coté de Narbonne :
http://chaletdenis.free.fr/
    
./Post n°1   Marquer comme non lu.
geogeo Ecrit le: Samedi 8 janvier 2005 à 20:16 Déconnecté(e)    Voir le profil de geogeo Envoyer un email à geogeo Visiter le site WEB de geogeo Envoyer un message privé à geogeo  


Je peux te donner du code mais bon ça risque de ne pas être utile car ça dépend de ton format de graph. Bref comment un circuit s'organise et comment l'info d'orientation se présente elle?
Webmaster du site.
Programmeur sur TI68K. Arkanoid, Nebulus, GFA-Basic.

Plus d'informations sur GFA-Basic (un langage Basic pour TI68K).
http://www.tigen.org/gfabasic
    
./Post n°2   Marquer comme non lu.
Jfg Ecrit le: Samedi 8 janvier 2005 à 20:23 Déconnecté(e)    Voir le profil de Jfg Envoyer un email à Jfg Visiter le site WEB de Jfg Envoyer un message privé à Jfg  


Moi je vois même pas où est le problème.

[EDIT: je n'avais pas compris le pb.]
-Edité le Samedi 8 janvier 2005 à 20:32 par jfg-
Kill Mario
    
./Post n°3   Marquer comme non lu.
geogeo Ecrit le: Samedi 8 janvier 2005 à 21:02 Déconnecté(e)    Voir le profil de geogeo Envoyer un email à geogeo Visiter le site WEB de geogeo Envoyer un message privé à geogeo  


Voilà l'arbre que je ferai:
http://tisofts.free.fr/divers/circuit_mode7.png

Les noeuds représentent les marqueurs de ton squelette de ton circuit et plus précisément un virage! Sur le schéma les noeuds de même couleur forment un seul et unique noeud mais pour que ça soit plus compréhensible je représentais toutes les branches!

Le principe est que ton arbre se construit au premier virage donc au premier noeud qui sera la racine et l'arbre doit se finir forcément soit avec des noeuds NULL ou noeud DEPART.

Dès que tu as un noeud (0), tu parcours la route de gauche en premier jusqu'à arriver à un noeud (1) que tu mémorise à la fin, ensuite tu passes à la partie droite du circuit en partant du noeud (0) jusqu'à ce que tu tombe sur un noeud (2), tu reviens sur le noeud (1) tu parcours la partie gauche, tu sauves le noeud (1 - 1), partie droite du noeud (1), tu sauves noeud (1 - 2), tu reviens au noeud (2), partie gauche tu sauves noeud (2 - 1), partie droite, tu sauves (2 - 2) et ainsi de suite. Si tu arrives à un noeud qui a déjà était sauvegardé, noeud précédent le noeud que tu parcours alors c'est que la branche qui va suivre est interdite (orientation incorrecte et donc marquée NULL). Sur le schéma j'ai représenté cette branche mais normalement elle n'existe pas!

Voilà la première approche que je peux faire du sujet, bien sûr on peut simplifier je pense en faisant plusieurs passes mais la méthode que je viens d'exposer demande une seule passe!
-Edité le Samedi 8 janvier 2005 à 21:33 par geogeo-
Webmaster du site.
Programmeur sur TI68K. Arkanoid, Nebulus, GFA-Basic.

Plus d'informations sur GFA-Basic (un langage Basic pour TI68K).
http://www.tigen.org/gfabasic
    
./Post n°4   Marquer comme non lu.
geogeo Ecrit le: Dimanche 9 janvier 2005 à 01:22 Déconnecté(e)    Voir le profil de geogeo Envoyer un email à geogeo Visiter le site WEB de geogeo Envoyer un message privé à geogeo  


Plus de détails:
http://tisofts.free.fr/divers/circuit_mode72.png

Structure d'un noeud selon moi:

- Visité = 0 ou 1
- Branche_gauche = *noeud_x;
- Branche_droite = *noeud_x;
- Indicator = ?;
- Gauche_title = ?;
- Droite_title = ?;


L'arbre commence réellement au premier noeud, ici [color=#00ff00]noeud vert.
Arriver au noeud vert on le note visité et on met un indicateur pour le repérer facilement!
On compléte Gauche_title pour indiquer le début de la route de gauche et Droite_tile pour indiquer le début de la route droite à partir de ce noeud.

On commence par créer la partie gauche de l'arbre à partir de la racine (noeud vert)!
On parcourt la route de gauche et on arrive au noeud Bleu, on le note visité on compl_te indicator et Gauche_title et Droite_title pour indiquer les routes! Ne pas oublier de compléter Branche_gauche du noeud vert pointant vers le noeud bleu.

Arriver au bleu on parcours la route de gauche et on arrive au départ, ainsi on met quelque chose pour signifie que l'arbre s'arrête ici, ensuite on parcours la route de droite du noeud bleu et on arrive au noeud jaune.

Sauvegarde Gauche_title, Droite_title, met visité à 1... pour noeud jaune et on n'oublie pas de compléter Branche_droite du noeud bleu!
On parcourt route gauche du noeud jaune on arrive au rouge qu'on note visité...
On parcourt route droite du noeud jaune, on arrive au rouge mais celui-ci est déjà noté visité alors on regarde l'indicateur de la branche gauche du noeud jaune et si égalité on constate que le noeud jaune va directement au noeud rouge ainsi on détermine une seule et unique voie qui doit correspondre forcément à un noeud différent du noeud jaune à partir du noeud rouge, donc on parcourt la route de gauche à partir du noeud rouge et on revient au jaune donc pas bon mauvaise route donc on parcours la route de droite et on arrive au vert mais erreur car déjà visité et ne correspond en aucun cas à l'autre branche inverse du noeud rouge. Ainsi on modifie le noeud rouge pour lui dire forcément que sa bracnhe gauche et sa branche droite pointe sur le même noeud, c'est à dire le vert mais comme je l'ai dit précédement ce noeud est déjà visité donc on a une impossibilité que l'on doit noté! Notre arbre s'arrête ici!

Reste pour finir la partie droite de notre arbre à partir de la racine (noeud vert)!
On arrive au noeud rouge on fait comme d'hab, on parcourt route gauche du noeud rouge on créer le noeud jaune que l'on note visité... On parcourt route droite du noeud rouge et on observe qu'on tombe sur un noeud visité qui est le noeud jaune, on compare avec la branche gauche du noeud rouge et on voit une égalité donc forcément on a une seule et unique voie pour le noeud rouge qui pointe directement vers le noeud jaune. Donc arrivé au jaune on parcourt la route droite mais erreur on retombe sur le rouge donc c'est l'autre route qu'il faut, donc forcément Banche_gauche et Branche_droite du noeud rouge pointe sur le noeud bleu.
Arrivé au bleu on parcourt la route de gauche et erreur on arrive au noeud vert, l'arbre ce termine ici, on parcourt la route de droite du noeud bleu et enfin on arrive au départ!

Ensuite pour finir reste à traiter ton arbre en supprimant les mauvaise branches, berf toutes celles qui donne un chemin qui ne permet pas d'arriver à FIN!

En gros tu as ta racine,
Tu parcourt côté gauche, tu vois un autre noeud, tu sauves dans racine->branche_gauche le noeud (0) en question et tu complètes les infos du noeud (0) après tu parcours côté droit de la racine...
Ensuite lorsque tu arrive sà une situation où 2 routes se rejoignent:

Côté gauche arrive à un noeud tu note et complètes comme d'hab, partie droite arrive à un nom visité, tu compares avec la branche gauche si égalité alors voie unique sinon mauvais chemin donc fin de l'arbre.
Ensuite tu viens au noeud que tu as trouvé terminant la voie unique, tu parcours la voie de gauche, si tu retombe sur le noeud précédent c'est le mauvais chemin donc tu dois forcément parcourir la route de droite, dans ce cas tu notes le noeud suivant dans les 2 branches du noeud. Si tu trouves directement la bonne voie en parcourant la route de gauche c'est que forcément la route de droite est mauvaise.
Si c'est pas clair n'hésites pas. :)

Quand je dis route de gauche et route de droite je prend comme point de repère la voie où on est arrivé sur un noeud!

Théoriquement ça fonctionne dans tous les cas maintenant la structure peut être plus complexe et tout dépend de comment tu parcours les routes sur ta map!


-Edité le Dimanche 9 janvier 2005 à 01:25 par geogeo-
Webmaster du site.
Programmeur sur TI68K. Arkanoid, Nebulus, GFA-Basic.

Plus d'informations sur GFA-Basic (un langage Basic pour TI68K).
http://www.tigen.org/gfabasic
    
./Post n°5   Marquer comme non lu.
geogeo Ecrit le: Dimanche 9 janvier 2005 à 01:37 Déconnecté(e)    Voir le profil de geogeo Envoyer un email à geogeo Visiter le site WEB de geogeo Envoyer un message privé à geogeo  


A noter que si tu conserves l'arbre que tu généreras pour orienter ton niveau, tu peux développer une bonne intelligence artificielles en calculant le plus court chemin à partir des distances séparant les noeuds et ainsi trouver le chemin idéal que devra parcourir l'IA pour finir le niveau.
Après tu peux peut pousser le bouchon un peu plus loin en signalant au joeur qu'il est en sens inverse...
-Edité le Dimanche 9 janvier 2005 à 11:52 par geogeo-
Webmaster du site.
Programmeur sur TI68K. Arkanoid, Nebulus, GFA-Basic.

Plus d'informations sur GFA-Basic (un langage Basic pour TI68K).
http://www.tigen.org/gfabasic
    
./Post n°6   Marquer comme non lu.
LionelA Ecrit le: Dimanche 9 janvier 2005 à 12:15 Déconnecté(e)    Voir le profil de LionelA Envoyer un email à LionelA Visiter le site WEB de LionelA Envoyer un message privé à LionelA  


Encore merci de vous etre penché sur le pb :)

Voici la toute nouvelle solution que je viens de trouver (elle tue) :

au départ le graphe est non orienté :

http://anton.lionel.free.fr/TI68k/theorie%20ultime/graphe1.GIF

on connait l'orientation de deux arcs (ceux accrochés au noeud de départ) :

http://anton.lionel.free.fr/TI68k/theorie%20ultime/graphe2.GIF

on propage leurs orientations (un coup celle de l'arc du haut, un coup l'arc du bas), ce qui donne l'évolution suivante :


http://anton.lionel.free.fr/TI68k/theorie%20ultime/graphe3.GIF

http://anton.lionel.free.fr/TI68k/theorie%20ultime/graphe4.GIF

http://anton.lionel.free.fr/TI68k/theorie%20ultime/graphe5.GIF

et voila le résultat :)

j'ai testé sur papier avec un graphe énorme et ca a marché !

Si vous trouvez une faille dans cette théorie dites le moi vite avant que je n'ai fini de l'implémenter

Merci


EDIT : faille découverte pas Hibou su yN -> j'abandonne les complications, pas de dédoublements imbriqués

-Edité le Dimanche 9 janvier 2005 à 12:59 par LionelA-
Auteur de Mode7 Engine pour ti68k
Auteur de F-ZERO for TI68k
Membre de Orage Studio
Mon site perso : http://www.tigen.org/lionela/
Le gite de mes parents à coté de Narbonne :
http://chaletdenis.free.fr/
    
./Post n°7   Marquer comme non lu.
Kevin Kofler Ecrit le: Lundi 10 janvier 2005 à 02:31 Déconnecté(e)    Voir le profil de Kevin Kofler Envoyer un email à Kevin Kofler Visiter le site WEB de Kevin Kofler Envoyer un message privé à Kevin Kofler  


Il suffit de faire un backtracking en cas de problèmes comme le suggère geogeo.
Membre de l'équipe de TIGCC: http://tigcc.ticalc.org
Mainteneur du portage Linux/Unix de TIGCC: http://tigcc.ticalc.org/linux/
Membre de l'équipe de CalcForge: http://www.calcforge.org:70/

Participez à la reprise de Ti-Gen!
    
  :: Index » Forum TI-Nspire » Algorithmie et optimisation » Orientation d'un graphe (7 réponse(s))
Pages : 1/1     « [1] » »|

.Répondre à ce sujet
Les boutons de code
[B]old[I]talic[U]nderline[S]trikethrough[L]ine Flip Hori[Z]ontallyFlip [V]erticallySha[D]ow[G]low[S]poilerCode [G][C]ite
Bullet [L]istList Item [K] Link [H][E]mail[P]icture SmileysHelp
Couleurs :
Saisissez votre message
Activer les smileys
     

Forum de Ti-Gen v3.0 Copyright ©2004 by Geoffrey ANNEHEIM
Webmaster: Kevin KOFLER, Content Admins: list, Server Admins: Tyler CASSIDY and Kevin KOFLER, DNS Admin: squalyl
Page générée en 63.04ms avec 18 requetes