Discussion :

[Krispy]

voila. j'ai deja fait le probleme du voyageur de commerce. Mais meme si l'algo que j'ai utilisé est très lent, ca me donne quand meme le chemin le plus court. ( drijska )
mais maintenant, j'amerais le modifier.

Je voudrais rajouter :

-> existances de villes prioritaires ( obligation du voyageur de passer par la ville : 1 pour obligatoire, 0 pour facultative ).

-> le voyageur à une distance limite ( ben oui, faire autant de ville, ca use le carburant de la voiture )

-> Obstacles sur la route !

Et c'est deja pas mal

pour l'algo, j'utilise un tableau 100 * 100
j'ai les coordonnées de chaque ville
les obstacles et les villes sont des entiers. et pour savoir si un obstacle se trouve entre 2 villes, je calcule la droite passant par cesz 2 points, et je regarde si l'obstacle se trouve sur cette droite à 2 % près )

Voilà. Si vous avez des idées d'algo, n"hésitez surtout pas !

En vous remerciant

Nicolas

[Kangourou]

Salut,

plusieurs remarques :

Je crois que le probleme du voyageur de commerce et Djikistra sont 2 pbm differents :
voyageur= plus court chemin passant par tous les sommets d'un graphe
Djikistra=plus court chemin entre 2 points,sans passer par tous les points, avec valeur (=temps de trajet par exmple) pour chaque arete du graphe.

J'avoue que pour les villes prioritaires, je comprends pas trop :
Si une ville est facultative, tu la retire de la liste, et le chemin resultant sera forcement plus court, non ?

Pour les obstacles, il suffit de construire le graphe complet reliant toutes les villes entre elles, en omettant les liaisons qui contiennent un obstacle (critere geometrique dans ce cas). Ca doit etre facile, meme si ca l'est peut-etre moins de faire un algo rapide.

Voila A+

[lgirard]

ERREUR !!!!

Dijkstra donne le plus court chemin d'un sommet du graphe vers TOUS les autres sommets du graphe !!!!!

Le plus court chemin d'un sommet à un autre peut se faire par une variante de Dijkstra, mais pas avec l'original....

[Krispy]

euh.... en fait, j'utilisais une métode qui ressemble à Drijska.

je vais tenter d'étre clair car ca n'est pas facile.

Je calcule les distances entre toutes les villes prioritaires.
ensuite, par drijska, je cherche le chemin le plus court pour relier ces villes prioritaires )
Ensuite, une fois que j'ai le chemin le plus court, je le met dans une liste chainée.


Ensuite, je cherche un chemin voisin passant par une autre ville prioritaire qui n'était pas sur le chemin ( tout en respectant les obstacles ) et je le remplace. ( d'ou la liste chainee, car remplacer au milieu d'un tableau, c'est pas terrible )

Ensuite, vient l'algo compliqué en question.

je nomme le chemin chemin provisoire. je choisis un chemin voisin. Si il est plus court, je le remplace.
Si il est plus long : 2 possibilités : Si il est vraiment trop long, je le vire, si il est pas beaucoup plus long, je le remplace.

De cette facon, je peux controler le temps d'exécutiion du programme.
Ca s'appelle la méthode du recuit Simulé.


En fait, j'espère pouvoir passer par toutes les villes prioritaires et le maximum de villes facultatives, tout en ayant à l'esprit que j'ai une distance maximum à respercter.



Edit : J'aimerais bien que mon gars puisse revenir au point de départ. Voous avez une idée ? je galère un peu pour ca.

[lgirard]

voila. j'ai deja fait le probleme du voyageur de commerce. Mais meme si l'algo que j'ai utilisé est très lent, ca me donne quand meme le chemin le plus court. ( drijska )
mais maintenant, j'amerais le modifier.

Je voudrais rajouter :

-> existances de villes prioritaires ( obligation du voyageur de passer par la ville : 1 pour obligatoire, 0 pour facultative ).

si tu connais l'ordre de passage des villes pour le parcours, rien de plus facile.
Exemple : si tu dois faire la parcours suivant : A, B, C, D (dans l'ordre), alors recherche le plus court chemin de A à B, puis de B à C, puis de C à D, puis de D à A si tu dois revenir au point de départ.

-> le voyageur à une distance limite ( ben oui, faire autant de ville, ca use le carburant de la voiture )

lorsque la valuation de ton chemin dépasse cette limite, alors tu stoppes tout

-> Obstacles sur la route !

il suffit de supprimer dans ton graphe l'arc (cas de graphe orienté, arête sinon), et le pcc n'y passera pas.

Et c'est deja pas mal

pour l'algo, j'utilise un tableau 100 * 100
j'ai les coordonnées de chaque ville

tu travailles don cavec la distance euclidienne ? c'est pas très représentatif d'un réseau routier cela, tu ne crois pas ?

les obstacles et les villes sont des entiers. et pour savoir si un obstacle se trouve entre 2 villes, je calcule la droite passant par cesz 2 points, et je regarde si l'obstacle se trouve sur cette droite à 2 % près )

Voilà. Si vous avez des idées d'algo, n"hésitez surtout pas !

En vous remerciant

Nicolas

[/quote]

[Krispy]

Merci d'avoir répondu !

Alors pour la distance, je ne peux pas tout stopper car le pauvre gars doit revenir au point de départ.

Quant à la distance euclidienne, oui, je travaille avec elle
c'est le plus simple, non ?

J'ai la coordonée en X et en Y, la distance est facile à trouver. et les equations de droite, c'est plus simple en carthésien, non ? Mais je suis ouvert à toutes suggestions

[lgirard]

la distance euclidienne est la plus simple, mais elle correspond ni plus ni moins à la distance à vol d'oiseau. Bien évidemment, cette distance n'est qu'une borne inf de la vraie distance..

D'autre part, la notion de distance entre deux villes est somme toute pas suffisante, car n'est-il pas plus réaliste de prendre en compte le temps entre deux villes ? temps qui dépend de la distance en effet, mais aussi de la vitesse moyenne, elle même dépendant du type de route...

Concernant la distance max a effectuer, si votre graphe routier est symétrique, alors vous vous arrêter à votre limite divisée par deux.
Si votre graphe routier est non symétrique, c'est un peu plus compliqué, mais cela se fait aussi en calculant en parallèle la distance de retour.

[tomtom7]

Salut,

D'autre part, la notion de distance entre deux villes est somme toute pas suffisante, car n'est-il pas plus réaliste de prendre en compte le temps entre deux villes ? temps qui dépend de la distance en effet, mais aussi de la vitesse moyenne, elle même dépendant du type de route...

C'est tout à fait vrai. Il est toujours plus judicieux de travailler en temps plutôt qu'en distance... Même si les 2 sont corrélés.
Après, ça dépend de l'utilisation que tu dois faire de ton prog. Si tu veux vendre la résolution du PVC c'est clair qu'il te faut un vrai distancier routier et pas juste les coordonnées des villes.

Concernant la distance max a effectuer, si votre graphe routier est symétrique, alors vous vous arrêter à votre limite divisée par deux.
Si votre graphe routier est non symétrique, c'est un peu plus compliqué, mais cela se fait aussi en calculant en parallèle la distance de retour.

Désolé de te reprendre lgirard mais il est rare (surtout avec la distance euclidienne) qu'on repasse au retour par les villes de l'aller... Il faut que toutes les villes de la tournée soient alignées.

Ce ne serait pas plus simple de travailler sur une tournée qui boucle en permanence?
Depot-Depot
Depot-Ville1-Depot
Depot-Ville1-Ville2-Depot ...
Tu pourrais contrôler la distance totale.

Enfin, Krispy, c'est DIJKSTRA pas drijska. Erétique!

[Krispy]

Enfin, Krispy, c'est DIJKSTRA pas drijska. Erétique!

effectivement. merci de me reprendre.

Mais je n'ai pas l'intention de vendre mon Programme ni quoi que soit. c'est juste par *pur plaisir*. Et pour commencer, je opréfère travailler en distance. avec une distance limitée pour ce voyageur.


Est-ce que la solution qui consiste à dabord rechercher les chemins avec les villes prioritaires puis ensuite améliorer avec le plus grand nombre de villes facultatives vous parait convenable ( j'entends par là, ne pas prendre 34604 jours pour un algo de 4 villes ) ?

[tomtom7]

Oui pourquoi pas...
Rien ne t'empêche de commencer par insérer les villes prioritaires. Tu fais 2 listes, tant que tu peux insérer des villes de la 1ere tu le fais. Quand tu ne peux plus ou qu'elle est vide tu essaies avec les villes de la 2eme.
Mais plutôt que de réinventer l'eau chaude tu devrais jeter un oeil sur l'algo meilleure insertion... Au moins t'en inspirer. Il est simple et marchera bien pour ton problème.
Tant que tu n'as pas de contraintes horaires ça roule et c'est rapide.

[Krispy]

.Mais plutôt que de réinventer l'eau chaude tu devrais jeter un oeil sur l'algo meilleure insertion... Au moins t'en inspirer. Il est simple et marchera bien pour ton problème.

Ok. merci. c'est ce que ja vais faire.
je pensais , lorque 'on devait prendre une ville non prioritaire, définir un "cercle" autour des 2 villes et dans lequel je recherchais des villes facultatives.

.Tant que tu n'as pas de contraintes horaires ça roule et c'est rapide.

Qu'est ce que tu entends par contrainte horaire ? le temps d'exécution du programme ? bah ! si il ne faut pas 3 jours pour qu'il cherche la solution, ca me va

[tomtom7]

Hummm.
C'est pas super clair ton histoire de cercle...
Les contraintes horaires c'est pour le passage dans les villes.
Ex : villei entre 10:00 et 11:00.
A partir du moment où tu contraints ton problème comme ça c'est beaucoup moins agréable de bosser dessus parce que ça enlaidi le résultat. D'une belle tournée bien ronde tu passe à un espèce de tas de droites qui se croisent (j'exagère 1 peu...).
Mais pour un problème de la vraie vie t'es un peu obligé de tenir compte de trucs comme ça.

[Krispy]

Hummm.
C'est pas super clair ton histoire de cercle...

ah! peut-etre qu'il y a une méthode plus rapide, effectivement. mais je cherche encore ! je ne suis qu'à l'élaboration papier du prgm.
Une petite idée ? car pour pour rechercher les villes à rajouter, j'utilise une matrice 100*100 et je me déplace le long de la droite reliant ces deux villes. peut-etre que le déplacement dans cette dite-matrice va prendre trop de temps. j'espère un truc assez optimisé quand meme '( ou alors même juste un petit peu, ca serait déjà bien 8) )

Les contraintes horaires c'est pour le passage dans les villes.
Ex : villei entre 10:00 et 11:00.

Ok ! Non, heureusement que je n'ai pas ca. mais c'est vrai que ca pourrait être intéressant. ptet que si j'ai le temps et la motivation nécessaire, j'essayerais. C'est toujours bien de se lancer des défis ! 8

[Metal Tom]

Généralement quand on cherche un algo de ce genre on part du principe qu'on a déjà le graphe contenant les distances entre les différents sommets.
Je pense donc qu'il faut séparer la partie analyse de la situation ou tu vas évaluer la distance, temps etc entre les villes. Comme le disait quelqu'un si il y a un obstacle c'est que tout simplement le chemin est coupé donc on ne met pas d'arc (ou d'arète).
La deuxième partie est d'appliquer l'algo que tu cherches je pense au graphe que tu auras obtenu lors de la première phase.
Je crois qu'il est possible de se ramener à un voyage de commerce modulo quelques petites différences. Si ça reste NP-complet tu restes dans la merde :-) Par contre la méthode du recuit simulé n'est pas une méthode exacte mais une bonne heuristique qui est souvent utilisée pour ce genre de problèmes.
Je te conseilles donc de rechercher des approches du TSP (Travel Saleman Problem) sur internet : il y a des trucs intéressants. Les algos génétiques peuvent t'aider par exemple.

[bNoureddine]

voila. j'ai deja fait le probleme du voyageur de commerce. Mais meme si l'algo que j'ai utilisé est très lent, ca me donne quand meme le chemin le plus court. ( drijska )
mais maintenant, j'amerais le modifier.

Je voudrais rajouter :

-> existances de villes prioritaires ( obligation du voyageur de passer par la ville : 1 pour obligatoire, 0 pour facultative ).

-> le voyageur à une distance limite ( ben oui, faire autant de ville, ca use le carburant de la voiture )

-> Obstacles sur la route !

Et c'est deja pas mal

pour l'algo, j'utilise un tableau 100 * 100
j'ai les coordonnées de chaque ville
les obstacles et les villes sont des entiers. et pour savoir si un obstacle se trouve entre 2 villes, je calcule la droite passant par cesz 2 points, et je regarde si l'obstacle se trouve sur cette droite à 2 % près )

Voilà. Si vous avez des idées d'algo, n"hésitez surtout pas !

En vous remerciant

Nicolas

Bonjour !

Le probléme du voyageur de commerce est un probléme Hamiltonien , il y a le chemin le plus court et le circuit le plus court, le circuit Hamiltonien est un circuit qui passe une et une fois par tous les sommets du graphe et reviens au sommet de départ.

[ShootDX]

Je crois qu'il y a une solution possible avec le système de numérotation de Gros-Gray. Voila ce que j'ai trouvé:

[url]http://membres.lycos.fr/villemingerard/Numerati/CodeGray.htm[/code]

Mais attention:

Adleman a réussi à construire un ordinateur à ADN qui a résolu une version du problème du voyageur de commerce. L'ordinateur à ADN a mis une semaine, là où un ordinateur classique aurait mis des années.

Bonne chance

[Krispy]

Merci pour ces informations. Cependant, j'ai réussi à faire tout ce que je voulais. L'algo utilisé résoud 1500 villes en 3 minutes. donc je cris que ca peut aller. 8)

Probleme résolu !
Encore merci pour votre aide

[Metal Tom]

Ca change rien au problème : ça reste NP-complet.

[lgirard]

NP-Complet ou NP-Dur ???