FORUM MP | Algorithmes : voyageur de commerce

COMMUNAUTE MP

Identifiez vous ...

DOMAINE MP

Bavardages

Langages Généraux

Langages Web

Langages DotNet

Autres langages

Dev. Jeux Video

Sécurité

Sys. Exploitation

Graphismes

Logiciels

Réseaux

Bases de données

Méthodologies

Emplois High-tech

Aide juridique

Articles juridiques

FORUM

CHAT MP IRC

Votre pseudo ...

Serv: irc.irc-land.org

Chan: #MoteurProg

PARTICIPER

Plus de 3500 emplois.

Visiteur MP

voyageur de commerce
	Forum : ALGORITHMES Sous Catégorie : Aucune Type du sujet : Sujet Normale FAQ : FAQ ALGORITHMES
		SUIVI PAR MAIL INACTIF
		SUJET NON RESOLU
		SUJET ACTIF
		N'APPARTIENT PAS A LA FAQ

PAGE : [1]

FORUM ALGORITHMES
	Page précedente	Page suivante

khabith2006
Nouveau membre

Inscrit : 02/07/2007
Messages : 1

#137451 Posté le 02/07/07 à 22:12

salut à tous
l'énoncé du problème du voyageur de commerce, tel qu'il a été annoncé et résolu dans pas mal de sites, n'a pas l'aspect réel du fait que toutes les villes sont reliées entre elles chose qui n'est pas réelle. alors je reformuler l'énoncé de façon à avoir des villes où l'accès direct est impossible donc pour y arriver il faut passer par d'autres villes voisines.
pour indiquer qu'entre une ville A et une Ville B il n y a pas de chemin direct en remplit la case correspondante, dans la matrice qui contient les distances entre les villes, par -1.
il y t il quelqu'un qui pourra m'aider à résoudre ce problèmes ? et merci d'avance

HAUT DE PAGE

Publicité

Inscrit : X
Messages : X

#Aucun

HAUT DE PAGE

Biboup
Membre du club

Inscrit : 07/06/2004
Messages : 1859

#137547 Posté le 03/07/07 à 15:33

Bonjour,
désolé d'être méchant : j'ai rien compris à ce que tu a dit!

Soit clair, précis.
Utilise la ponctuation et les retours à la ligne.
__________________________
Modérateurs VB et Merise à la retraite (la retraite à 20 ans... le rève! ^^ )
L'aide (F1 pour les intimes) permet de résoudre pas mal de problèmes. Consultez la!!
De même avec les Les FAQ!!
A vaincre sans effort, on triomphe sans gloire

RESOLU est très utile pour les modérateurs pressés, PENSEZ-Y!!

HAUT DE PAGE

lovejava
Membre du club
Chef de projet(s) :
- Hughobot

Inscrit : 13/07/2004
Messages : 640

#137555 Posté le 03/07/07 à 15:54

tiens biboup ;) ça faisait longtemps

Moi je ne connais pas la réponse mais je crois avoir compris : il essaie de répondre à une version un peu plus compliquée du classique : le voyageur de commerce.
En gros, dans l'énoncé habituel, toutes les villes sont reliées entre elles, on stocke les distances les séparant dans une matrice.

Dans son problème, certaines villes ne sont pas reliées : on ne peux pas par exemple aller de B vers C directement, il faut passer par d'autres villes qui elles sont jointes.

Le fait que deux villes ne soit pas reliées est indiqué par la présence d'un '-1' dans la matrice là où l'on devrait normalement mettre la distance qui les sépare.

[Translation...done.]

Enfin moi j'ai pas LA réponse ^^ mais si tu veux utiliser les algorithmes génétiques je pense que tu peux simplement revoir ta fonction d'évaluation pour qu'elle élimine dès le début les trajets impossible (ceux qui contiennent au moins un -1 dans leur matrice) et ensuite continuer le traitement comme pour le problème habituel.
Par contre on fait beaucoup confiance au hasard et ça risque d'être plus long mais bon c'est un peu le cas des algo génétiques en général...si quelqu'un a une autre solution...
__________________________
Lorsque touts les arbres auront été coupés, Lorsque touts les animaux auront été chassés, Lorsque touts les poissons auront été pêchés;
Alors l'homme découvrira que l'argent ne se mange pas.
------ |_o/e _|a/a---------

HAUT DE PAGE


	Page précédente	Page suivante
FORUM ALGORITHMES

PAGE : [1]

.: Site Web développé par Julien Pichot et l'équipe MPWG avec www.evolvia-web.com :.