High-Tech Santé Médecine Droit-Finances

Réalisation

vidéo numérique

Rechercher : dans
Par :

Demande d'un algorithme de plus court chemin

Dernière réponse le 10 mai 2009 à 04:08:55 liza, le 27 oct 2005 à 19:57:54 
 Signaler ce message aux modérateurs

Bonjour tout le monde,

Est-ce que quelqu'un pourrait me dire quel algorithme je pourrais utiliser pour trouver un plus court chemin.
On m'a dit que je pouvais utiliser Dijkstra de manière récursive mais je ne vois pas comment.
Si vous avez de meilleures idées ou si vous pouvez tout simplement m'éclairer sur celle-là ça m'aiderait vraiment beaucoup.

Merci merci.

liza

Posez votre question Répondre

1

crabs, le 27 oct 2005 à 20:09:08

Salut,
Pas de récursivité, mais du vrai Dijkstra : attention le graphe ne doit pas
contenir de boucle.
http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
Sinon y a Floyd, mais il manque d"efficacité sur les graphes important...
http://www.nimbustier.net/publications/djikstra/floyd.html
Ce site explique aussi Dijkstra...
A+, crabs ..., I think Slackware sounds better than 'Microsoft,'
-- Patrick Volkerding - founder and maintainer of Slackware

   
Répondre à crabs

2

liza, le 28 oct 2005 à 14:02:32

Merci crabs

D'après ce que j'ai compris il faut faire un tableau à deux dimensions de taille nombre_de_positions * nombre_de_positions et ça me paraît énorme. Et je pense que si on pouvait caser une récursivité quelque part ça optimiserait un peu l'algo, non?

J'ai aussi entendu parler de l'algorithme A* mais apparemment il ne garantit pas de trouver le plus court chemin.

Qu'est-ce que tu en penses?

liza

   
Répondre à liza

3

teebo, le 28 oct 2005 à 14:16:56

Salut, un petite remarque en passant...

si on pouvait caser une récursivité quelque part ça optimiserait un peu l'algo

Ca pas vraiment, quand tu cherches à caser une récursivité en force tu fais plus de mal que de bien :)


Always forgive your enemies
Nothing annoys them so much.

(Oscar Wilde)

   
Répondre à teebo

4

crabs, le 28 oct 2005 à 17:17:55

Salut,
Là je suis en parfait accord avec teebo.
Maintenant si tu réfléchis un peu, un graphe avec 100 noeud ça te prendra
moins d' 1 Mo.
Dijkstra, c'est l'algo retenu pour le routage à la place de RIP, et il est très
certainement le plus efficace.
Sinon l'algo A-star c'est surtout pour les labyrinthes, il part du principe qu'il
faut s'approcher de la sortie.
A+, crabs ..., I think Slackware sounds better than 'Microsoft,'
-- Patrick Volkerding - founder and maintainer of Slackware

   
Répondre à crabs

5

liza, le 2 nov 2005 à 15:26:53

Bonjour,

En fait c'est un projet que j'ai à faire. J'ai une matrice de taille 26*26 et je dois trouver (comme tu l'as déjà compris j'imagine) le plus court chemin entre deux positions (déterminées) dans la matrice.
Au départ je pensais représenter les positions de la matrice par un tableau et le parcourir en largeur mais ça m'a l'air drôlement compliqué.
Pour Dijkstra, le problème est que je n'ai jamais étudié les graphes et je ne comprends pas bien les algorithmes que j'ai lu sur le net.
Quand on est à une position donnée (par exemple au départ), comment est-ce que je choisis vers quelle direction aller en premier sachant qu'une arrête entre 2 positions a toujours une valeur de 1. Ou alors, à chaque position, comment traiter tous les successeurs en même temps?
Ça fait beaucoup de questions je sais mais en faite je suis assez perdue avec cet algorithme.

Merci de m'aider.

liza

   
Répondre à liza

6

teebo, le 2 nov 2005 à 15:33:11

C'est pas nécessairement un cas typique et il n'y a pas 1 plus court chemin (sauf cas particuliers) mais plusieurs...

Tu as le droit aux diagonales ou pas?

Dans le cas ou ta réponse est non:

Calcul Dx et Dy, si un des deux est nul=> la solution est immédiate plus besoin de faire des calculs savant

Sinon tu avances te déplaces d'abord sur un axe et ensuite sur l'autre, pas besoin de chercher un optimum, tant que tu te déplaces dans le bon sens sans aller trop loin tu seras sur un des plus courts chemins...

Si tu as le droit aux diagonales, c'est plus compliqué (sauf dans le cas ou les deux sont sur une même ligne (Dy=0) ou une même colonne (Dx=0) où là la solution est encore une fois immédiate...

Mais dans l'absolu il faut que tu te déplaces dans la diagonale vers ton point d'arrivée autant de fois que le plus petit de tes deux D puis après sur l'autre axe du nombre de fois restant, pas bien compliqué tout ça, rien à voir avec un parcours d'arbre :)
Always forgive your enemies
Nothing annoys them so much.

(Oscar Wilde)

   
Répondre à teebo

7

liza, le 2 nov 2005 à 16:13:30

Merci teebo

Arggg!! J'ai oublié de préciser certaines choses je crois. Je dois coder un genre de sokoban en mode automatique avec une caisse et des murs à l'intérieur de l'aire de jeu.
Ça complique un peu les choses. Javais pensé aux distances un moment mais il est possible qu'à cause des murs il faille provisoirement éloigner le bonhomme et la caisse de la cible.
Donc je ne peux pas savoir à l'avance quel chemin je vais utiliser.

   
Répondre à liza

8

teebo, le 2 nov 2005 à 16:16:26

Effectivement ça complique singulièrement les choses :-D

Du coup c'est plus un algo de pathfinding en effet :)
Always forgive your enemies
Nothing annoys them so much.

(Oscar Wilde)

   
Répondre à teebo

9

 redhop, le 10 mai 2009 à 04:08:55

Voilà un site qui va t'aider qui donne de l'assistance sur un projet comme le tien sur les graphe tu dois le visité

www.easytools.zoneforum.com

   
Répondre à redhop
Posez votre question Répondre
Ils ont besoin de votre aide