A voir également:
- Demande d'un algorithme de plus court chemin
- Algorithme euromillion excel gratuit - Forum Excel
- Dans le gestionnaire de fichiers ci-dessous, suivez ce chemin : ordinateur > photos > album > maison vers quel fichier mène-t-il ? ✓ - Forum Windows 10
- Le chemin d'accès spécifié est introuvable ✓ - Forum Téléchargement
- Lnb court circuit - Forum TNT / Satellite / Réception
- 2 bip long 2 bip court hp ✓ - Forum Matériel & Système
5 réponses
crabs
Messages postés
908
Date d'inscription
lundi 18 avril 2005
Statut
Membre
Dernière intervention
3 août 2008
507
27 oct. 2005 à 20:09
27 oct. 2005 à 20:09
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
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
teebo
Messages postés
33491
Date d'inscription
jeudi 14 octobre 2004
Statut
Modérateur
Dernière intervention
24 février 2011
1 793
28 oct. 2005 à 14:16
28 oct. 2005 à 14:16
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 :)
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 :)
crabs
Messages postés
908
Date d'inscription
lundi 18 avril 2005
Statut
Membre
Dernière intervention
3 août 2008
507
28 oct. 2005 à 17:17
28 oct. 2005 à 17:17
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
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
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
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
teebo
Messages postés
33491
Date d'inscription
jeudi 14 octobre 2004
Statut
Modérateur
Dernière intervention
24 février 2011
1 793
2 nov. 2005 à 15:33
2 nov. 2005 à 15:33
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 :)
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 :)
liza
>
teebo
Messages postés
33491
Date d'inscription
jeudi 14 octobre 2004
Statut
Modérateur
Dernière intervention
24 février 2011
2 nov. 2005 à 16:13
2 nov. 2005 à 16:13
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.
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.
teebo
Messages postés
33491
Date d'inscription
jeudi 14 octobre 2004
Statut
Modérateur
Dernière intervention
24 février 2011
1 793
>
teebo
Messages postés
33491
Date d'inscription
jeudi 14 octobre 2004
Statut
Modérateur
Dernière intervention
24 février 2011
2 nov. 2005 à 16:16
2 nov. 2005 à 16:16
Effectivement ça complique singulièrement les choses :-D
Du coup c'est plus un algo de pathfinding en effet :)
Du coup c'est plus un algo de pathfinding en effet :)
Utilisateur anonyme
10 mai 2009 à 04:08
10 mai 2009 à 04:08
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
www.easytools.zoneforum.com
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
salut,
moi aussi je cherche des algorithmes de calcul de plus courts chemin j'ai trouvé l'algorithme de Malgrange
il doit considére les contraintes suivants:
-le graphe doit etre non orienté connexe
-l'algorithme ne prend pas en compte la notion de poids
-le plus court chemin doit etre elementair
-les chemin ne contienne pas de circuit absorbant
moi aussi je cherche des algorithmes de calcul de plus courts chemin j'ai trouvé l'algorithme de Malgrange
il doit considére les contraintes suivants:
-le graphe doit etre non orienté connexe
-l'algorithme ne prend pas en compte la notion de poids
-le plus court chemin doit etre elementair
-les chemin ne contienne pas de circuit absorbant
28 oct. 2005 à 14:02
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