Trouver un chemin sur une carteRésolu

Question

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&#233;e merci de m'en faire part.

Merci. ++ Nexus

Chaque probl&#232;me a sa solution. S'il n'y a pas de solution c'est qu'il n'y a pas de probl&#232;me.

malalam · Accepted Answer

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.

malalam · Answer

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 ?

Steph115 · Answer

Exact je comprend,


a chaque debut et fin de rue sur une carte tu as dans une BDD les coordonn&#233;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&#232;me a sa solution. S'il n'y a pas de solution c'est qu'il n'y a pas de probl&#232;me.

Steph115 · Answer

Exact je comprend,


a chaque debut et fin de rue sur une carte tu as dans une BDD les coordonn&#233;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&#232;me a sa solution. S'il n'y a pas de solution c'est qu'il n'y a pas de probl&#232;me.

Steph115 · Answer

Exact je comprend,


a chaque debut et fin de rue sur une carte tu as dans une BDD les coordonn&#233;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&#232;me a sa solution. S'il n'y a pas de solution c'est qu'il n'y a pas de probl&#232;me.

Steph115 · Answer

Exact je comprend,


a chaque debut et fin de rue sur une carte tu as dans une BDD les coordonn&#233;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&#232;me a sa solution. S'il n'y a pas de solution c'est qu'il n'y a pas de probl&#232;me.

Steph115 · Answer

Exact je comprend,


a chaque debut et fin de rue sur une carte tu as dans une BDD les coordonn&#233;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&#232;me a sa solution. S'il n'y a pas de solution c'est qu'il n'y a pas de probl&#232;me.

Steph115 · Answer

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&#232;me a sa solution. S'il n'y a pas de solution c'est qu'il n'y a pas de probl&#232;me.

Steph115 · Answer

Ok je te remercie de tout ca je vais etudiez le tes reponses.

Merci. ++ Nexus

Chaque probl&#232;me a sa solution. S'il n'y a pas de solution c'est qu'il n'y a pas de probl&#232;me.

Trouver un chemin sur une carte

9 réponses

Votre réponse

Discussions similaires