Discussion :

[ADSL[fx]]

bonjour, je cherche un algorithme rapide (sinon c'est pas la peine) pour résoudre le probleme suivant :

j'ai un graphe, dont le sommet de départ est fixé. il me faut un chemin qui passe par tous les sommets. cela ressemble donc au PVC sauf que le départ est donné et il n'y a pas besoin d'y revenir.

l'idéal serait de connaitre le temps minimal pour parcourir tous ses sommets, mais comme cela demanderais trop de temps je cherche un temps t, tel que t soit inférieur à ce temps minimal, et t le plus grand possible.

j'ia fait ca pour l'instant : pour chaque sommet je cherche le plus faible potentiel des arcs qui arrivent en lui et je fait la somme de tous des potentiels. ca marche mais je récupère un t trop faible a mon gout, il faudrait une autre idée pour se rapprocher un peu plus de la vérité.

quelqu'un a une idée ?

[ol9245]

un algo PVC ne résoud pas ta question ?

[ADSL[fx]]

il n'y a pas besoin de revenir au départ, ça fait donc un arc de moins a parcourir. alors je dirait que non

[ol9245]

il n'y a pas besoin de revenir au départ, ça fait donc un arc de moins a parcourir. alors je dirait que non

Tu veux chercher/développer un code spécial juste parceque tu veux pas supprimer le dernier arc d'un VC ? T'es courageux !

[ADSL[fx]]

tu pense que la solution est forcement la meme qu'avec le probleme du PVC ? t'en a la preuve formelle ?
et le probleme avec le PVC c'est que d'apres ce que j'ai pu voir, il n'y a pas d'algorithme de resolution exacte en dehors des usines a gaz

[ol9245]

tu pense que la solution est forcement la meme qu'avec le probleme du PVC ? t'en a la preuve formelle ?
et le probleme avec le PVC c'est que d'apres ce que j'ai pu voir, il n'y a pas d'algorithme de resolution exacte en dehors des usines a gaz

Je me suis basé sur le fait que tu as dit que tu n'as pas besoin de la solution la meilleure. Un VC avec le dernier sommet en moins fait donc éventuellement l'affaire. Quand au code uzinagaz ou pas, c'est pas des questions que je me pose quand je cherche des codes d'algo. La question que je me pose, c'est cobien de temps ça va me prendre pour l'implanter chez moi. Je te cite par exemple la bibliothèque FFTW (Fastest Fourrier Transform in the West). le code est énorme. le travail à faire, pas du tout : downloader, compiler, et appeler la fonction dont j'ai besoin. Ca m'a pris une heure chrono. Pareil pour un Dijkstra (chemin le plus court) : j'ai pas pris le meilleur algo en performance, mais le plus simple à implanter chez moi.

Ces parenthèses mises à part, on ne peut réfléchir que sur ce que tu nous dit de ton problème. Il est tout à fait possible que les solutions proposées sur cette base ne conviennent pas...
OL

[jobherzt]

tu pense que la solution est forcement la meme qu'avec le probleme du PVC ? t'en a la preuve formelle ?
et le probleme avec le PVC c'est que d'apres ce que j'ai pu voir, il n'y a pas d'algorithme de resolution exacte en dehors des usines a gaz

que ca soit la meme soultion, surement pas. mais le meme algorithme, ca ne fait pas de doute.

dans tous les algorithmes pour le PVC, qu'ils soient exacts ou des meta heuristiques, tu prend ou rejette des solutions suivant la longeur du chemin qui correspond. dans ton cas, c'est juste le calcul de la longueur qui change...

si on a 4 sommet, on a dans le PVC :

score (a,b,c,d) = d(a,b)+d(b,c)+d(c,d)+d(d,a)

dans ton cas :

score (a,b,c,d) = d(a,b)+d(b,c)+d(c,d)

mais a part ca, ya rien a changer a l'algorithme. donc je te conseille un algo genetique, amelioré avec une 2-opt par exemple. tu obtiendras des solutions plus que bonnes en un temps minime.