Trouver un chemin sur une carte

[Résolu]
Signaler
Messages postés
163
Date d'inscription
mercredi 22 octobre 2003
Statut
Membre
Dernière intervention
3 février 2012
-
Messages postés
163
Date d'inscription
mercredi 22 octobre 2003
Statut
Membre
Dernière intervention
3 février 2012
-
Bonjour,

Je dois programmer en php d'apres une carte dont je connasi les coordonnees des poitns de depart et d'arrivee des rues une fonction permettant d'aller d'un point A a un point B.

Si quelqu'un a uen idée merci de m'en faire part.

Merci. ++ Nexus

Chaque problème a sa solution. S'il n'y a pas de solution c'est qu'il n'y a pas de problème.

9 réponses

Messages postés
10839
Date d'inscription
lundi 24 février 2003
Statut
Modérateur
Dernière intervention
2 mars 2010
25
Je m'en doutais un peu...;-)

Bon ben bon courage !!

Ca s'appelle de la recherche operationnelle, et ce n'est pas un domaine tres tres simple.

Tien :

http://www.sm.u-bordeaux2.fr/~corsini/Cours/mainRO/

Si tu as le courage de tout lire...

Maintenant il y a des moyens simples (et peu efficaces, mais bon) de
faire ca. Il y a quelques annees j'avais ecrit ca en C pour une
simulation de livraisons de colis...c'etait simple, pas genial genial,
mais ca fonctionnait a peu pres. Je n'avais pas envie de me prendre la
tete sur de grosses recherche pour cet algo.

Le truc con, je ne me souviens absolument plus de l'algo utilise, et il
est quelquepart chez moi en France (or, je bosse maintenant en
Allemagne...).

On peut imaginer un truc du genre :

A interroge ses voisins B C et D pour savoir s'ils connaissent F

Ils ne savent pas, alors interrogent leurs voisin (sauf A, et les deux autres).

Si ces voisins ne savent pas, ils interrogent leurs voisins...

Disons que D a une reponse positive de E qui connait F.

A sait donc qu'il peut envoyer son colis a D qui sait qu'il peut l'envoyer a E qui va l'envoyer a F.



Mais a mon avis, c'est lourd...et puis si on a plusieurs
possibilites...et puis pour arreter les interrogations dans le vide
aussi!

Un moyen de limiter ca est de decouper la carte en zones.

A veut envoyer vers H.

A sait que pour aller vers F, G ou H, il doit envoyer son colis a B.

B sait que pour envoyer son colis vers G ou H, il doit l'envoyer a D.

D est voisin de H.
Messages postés
10839
Date d'inscription
lundi 24 février 2003
Statut
Modérateur
Dernière intervention
2 mars 2010
25
Hello,



ce n'est pas tres clair ton truc.

Mettons que tu as 4 points A B C et D

Tu peux aller de A a D en passant par :

A C D

A B D

A B C D

A C B D



ce que je t'explique la, c'est que sans restriction, aller d'un point a
un autre peut tres bien impliquer de passer par TOUS les autres points
avant d'arriver a destination. Dans ce cas, on peut meme faire ca au
hasard, et s'arreter des qu'on arrive au point de destination.



Tu veux faire quoi, au juste ?
Messages postés
163
Date d'inscription
mercredi 22 octobre 2003
Statut
Membre
Dernière intervention
3 février 2012

Exact je comprend,


a chaque debut et fin de rue sur une carte tu as dans une BDD les coordonnées.


Effectivement le mieux serait le chemin le plus court pour aller du point A au point B.


J'avasi penser a m'arreter des que j'ai trouver mais ca risque d'etre un peu gros voir meme lourd surtout si la BDD est grosse.

Pour info je n'ai toujours pas creer la structure de la BDD.

Merci. ++ Nexus

Chaque problème a sa solution. S'il n'y a pas de solution c'est qu'il n'y a pas de problème.
Messages postés
163
Date d'inscription
mercredi 22 octobre 2003
Statut
Membre
Dernière intervention
3 février 2012

Exact je comprend,


a chaque debut et fin de rue sur une carte tu as dans une BDD les coordonnées.


Effectivement le mieux serait le chemin le plus court pour aller du point A au point B.


J'avasi penser a m'arreter des que j'ai trouver mais ca risque d'etre un peu gros voir meme lourd surtout si la BDD est grosse.

Pour info je n'ai toujours pas creer la structure de la BDD.

Merci. ++ Nexus

Chaque problème a sa solution. S'il n'y a pas de solution c'est qu'il n'y a pas de problème.
Messages postés
163
Date d'inscription
mercredi 22 octobre 2003
Statut
Membre
Dernière intervention
3 février 2012

Exact je comprend,


a chaque debut et fin de rue sur une carte tu as dans une BDD les coordonnées.


Effectivement le mieux serait le chemin le plus court pour aller du point A au point B.


J'avasi penser a m'arreter des que j'ai trouver mais ca risque d'etre un peu gros voir meme lourd surtout si la BDD est grosse.

Pour info je n'ai toujours pas creer la structure de la BDD.

Merci. ++ Nexus

Chaque problème a sa solution. S'il n'y a pas de solution c'est qu'il n'y a pas de problème.
Messages postés
163
Date d'inscription
mercredi 22 octobre 2003
Statut
Membre
Dernière intervention
3 février 2012

Exact je comprend,


a chaque debut et fin de rue sur une carte tu as dans une BDD les coordonnées.


Effectivement le mieux serait le chemin le plus court pour aller du point A au point B.


J'avasi penser a m'arreter des que j'ai trouver mais ca risque d'etre un peu gros voir meme lourd surtout si la BDD est grosse.

Pour info je n'ai toujours pas creer la structure de la BDD.

Merci. ++ Nexus

Chaque problème a sa solution. S'il n'y a pas de solution c'est qu'il n'y a pas de problème.
Messages postés
163
Date d'inscription
mercredi 22 octobre 2003
Statut
Membre
Dernière intervention
3 février 2012

Exact je comprend,


a chaque debut et fin de rue sur une carte tu as dans une BDD les coordonnées.


Effectivement le mieux serait le chemin le plus court pour aller du point A au point B.


J'avasi penser a m'arreter des que j'ai trouver mais ca risque d'etre un peu gros voir meme lourd surtout si la BDD est grosse.

Pour info je n'ai toujours pas creer la structure de la BDD.

Merci. ++ Nexus

Chaque problème a sa solution. S'il n'y a pas de solution c'est qu'il n'y a pas de problème.
Messages postés
163
Date d'inscription
mercredi 22 octobre 2003
Statut
Membre
Dernière intervention
3 février 2012

Oups vraiment desole pour touts ces sujets pareils mais le site n'avait pas l'air de marcher quand j'allasi dessus je ne voyais pas le sujet poste ou je voyait un message d'erreur

Merci. ++ Nexus

Chaque problème a sa solution. S'il n'y a pas de solution c'est qu'il n'y a pas de problème.
Messages postés
163
Date d'inscription
mercredi 22 octobre 2003
Statut
Membre
Dernière intervention
3 février 2012

Ok je te remercie de tout ca je vais etudiez le tes reponses.

Merci. ++ Nexus

Chaque problème a sa solution. S'il n'y a pas de solution c'est qu'il n'y a pas de problème.