[Jeu sympa ET gratuit] Popomundo (#9)

Lwevin Myan · 03/03/2009, 17h47

Citation :

Publié par Acaedan

Y a pas quelqu'un qui saurait faire un petit programme pour calculer la tournée parfaite ?
Genre le parcours idéal entre toutes les villes, le plus court, le plus rapide, avec le moins possible de passages doubles dans une ville.

P.S. : Popmundo Tour Designer, je connais, et c'est pas ca

C'est très très difficile.
C'est le problème du voyageur de commerce, avec une grosse limitation (tous les trajets ne sont pas possibles), mais avec une énorme extension (on peut et on doit probablement passer deux fois par la même ville pour avoir un trajet optimum).
Sans heuristiques et avec 41 villes, le calcul de la chose prendrait quelques centaines d'années (sans exagérer).

Il faut "juste" implémenter des heuristiques, quoi.

03/03/2009, 17h53

Message supprimé par son auteur.

Lwevin Myan · 03/03/2009, 18h45

C'est réalisable, mais d'une la réalisation ne sera pas forcément optimale et de deux, la programmation de ce genre de choses n'est pas triviale. On parle d'un problème que ne sait pas vraiment résoudre la communauté scientifique (techniquement, pas du tout, même, puisqu'on ne fait qu'approximer la meilleure solution, sans avoir la garantie qu'on a la solution optimale). Il ne faut pas que être "un peu" bon en maths.
Par ailleurs, trouver un truc déjà existant sur Internet, j'ai des doutes, car les contraintes spécifiques à ce problèmes sont trop spécifiques, justement. Donc, il faut éventuellement s'inspirer de ce qu'on peut trouver sur le net, et l'adapter. Bon courage, quoi.

cricri · 03/03/2009, 22h45

d un autre cote le pb est plus simple pour nous suffit de faire un tour complet en minimisant le temps de parcourt entre chaque ville (on a 1 jour pour chaque ville)

on a pas besoin de calculer un tour complet sans arret

Rhaitz · 04/03/2009, 04h00

Wes Toland
Wes est une fille de 27 ans qui fait partie de Zebra Incognito. Wes devient The Zebra en concert. Wes se trouve en ce moment à Los Angeles, ici : LA Rock.

Je suppose que c'est le dernier tresor national que personne avais utiliser (que Jonas avait dis)

Aiina · 04/03/2009, 09h46

Ohhh mon ex bandm8 est devenu une nana, god damn c'est quoi ce bordel. :O Il a rajeunit de 10 ans aussi...

Par contre, il a gardé son prénom, ça fait un peu trans du coup. Je me vois mal m'appeler ross avec un perso féminin... :x

04/03/2009, 10h08

Citation :

Publié par Acaedan

Donc c'est pas réalisable comme ca par un jolien un peu bon en maths ?

J'en ai fait un mais chui mauvais en maths

C'est plus un problème de conception que d'analyse en fait, les techniques sont assez connues mais la plupart des programmes gèrent des coordonnées au lieu de distances... Rien d'insurmontable mais ça ne se code pas tout seul sinon ça se saurait

J'avais filé le lien de ce que j'avais fait quelque part dans ce fil ou celui d'avant, pas le temps de m'en occuper en ce moment, désolé.

Aiina · 04/03/2009, 10h12

Citation :

Publié par Olblach

J'en ai fait un mais chui mauvais en maths

C'est plus un problème de conception que d'analyse en fait, les techniques sont assez connues mais la plupart des programmes gèrent des coordonnées au lieu de distances... Rien d'insurmontable mais ça ne se code pas tout seul sinon ça se saurait

J'avais filé le lien de ce que j'avais fait quelque part dans ce fil ou celui d'avant, pas le temps de m'en occuper en ce moment, désolé.

https://forums.jeuxonline.info/showt...5#post17000715

A force d'être ici, je commence à bien connaitre les arcanes de ce forum.

Lwevin Myan · 04/03/2009, 10h26

Le truc, c'est que c'est pour 12 villes (dixit ton post), donc à ce niveau, effectivement, on peut explorer toutes les possibilités, ce n'est pas énorme.
Comme c'est une factorielle, 12! est calculable, 500 millions de possibilités, ce n'est rien.
41! l'est beaucoup moins.

Donc, non, les techniques ne sont pas "connues".
(D'ailleurs, plutôt que le programme, le source aurait été mieux)

04/03/2009, 11h04

Bah euh il y a des concours qui tournent sur 1 million de villes, sinon t'as celui là sur 250 villes qui marche très bien : http://labo.algo.free.fr/defi250/def...50_villes.html

Les différentes techniques sont présentées ici : http://labo.algo.free.fr/pvc/algorithme_genetique.html

Comme je disais le problème c'est que ce sont des points pas des distances entre deux villes sinon tu aurais déjà ton tour du monde bouclé.

Quant à mes sources c'est du niveau débutant, j'ai juste fait un truc rapide, si je l'améliore on en reparlera. C'est du C# t'as mon autorisation pour le décompiler si ça te démange

Pour faire ton tour du monde tu fais des paquets de 12-15 villes, par exemple en les regroupant par continents, après il faut ruser un peu pour connecter les continents entre eux, ça te fera pas forcément un tour parfait mais ça devrait faire un truc correct, surtout si t'es pas à la journée près.

Lwevin Myan · 04/03/2009, 11h19

Mais encore une fois, le truc avec les 250 villes :
1) Il y a des méthodes heuristiques derrière qui ne te garantissent pas que le résultat sera optimal (même si 99% de chances, on est d'accord)
2) prennent comme hypothèse que tous les chemins sont possibles (pas "trop" grave), et qu'on passe une unique fois dans chaque vile. Ce dernier point simplifie énormément le problème (tant du point de vue perf que du point de vue algo : sur tes 250 villes, ben ton parcours fait 250 villes, point. Popmundo, tu ne connais pas la longueur du chemin idéale, ce qui rend par exemple les algos génétiques ou 2-opt qu'on trouve sur le net inadaptés).

Je n'ai jamais dit qu'un tel programme était impossible, juste qu'il faut un peu plus qu'un coin de table et cinq minutes pour le faire, c'est très loin d'être trivial.

04/03/2009, 11h34

Oui ce sont des heuristiques on est bien d'accord. Par contre il paraît qu'avec les ordinateurs ADN on arriverait à le résoudre.

Et non ce n'est pas trivial j'ai jamais dit ça

Maintenant pour boucler ton tour avec un bon algo ça devrait te filer un truc très correct.

En tous cas si la daube que j'ai programmé est utile à quelqu'un je prendrai deux minutes pour la mettre à jour avec les nouvelles routes (et éventuellement vous filer le source

).

Le point 2 que tu soulèves est intéressant, perso j'ai résolu ça en commençant par calculer la meilleure route entre les villes deux à deux. Effectivement, on peut considérer que cette route peut ne pas être la meilleure dans le cadre d'une tournée. C'est là où en entre dans le problème de conception que j'ai mentionné pudiquement plus haut

En fait j'étais parti sur un modèle objet assez bizarroïde et intéressant mais j'ai jamais eu le temps de le finir.

Dhu · 04/03/2009, 13h02

Citation :

Publié par Fartha

Pas encore...

Bon, je suis satisfait de ces élections. Statistiquement, j'ai réuni entre 55 et 65% des votes francophones.

Comment arrives tu à ce chiffre ?

Tu termines avec 87 voix (soit moins que ce que Cédric Doreau avait lorsqu'il a annulé sa candidature au dernier moment et s'était présenté après toi), Chanteau à 320 voix et Audrey Gate à 38 voix.

Donc selon toi, Audrey représente 30% des francophones et Chanteau 15 ou 20 % ?

C'est fort tout de même

Fartha · 04/03/2009, 14h20

Citation :

Publié par Dhu

C'est fort tout de même

Et oui, merci

Rhaitz · 04/03/2009, 17h42

Un de vous connais quelqun qui enseigne spin doctor mastery ? et quelqun qui serais pret a me suivre pour les 2 jr de teach ?

Et a quel prix ?

Fartha · 04/03/2009, 17h54

Je l'enseigne en ce moment. Mais peu de chance que je puisse me déplacer (vis à vis des autres élèves). Ou alors, il faudra beaucoup payer !

*mode capitaliste ON*

Rhaitz · 04/03/2009, 18h02

C'est pas pour moi c'est pour mon bandmate (mais il lui manque encore 1 ou 2 etoile dans un des skills) c'est quoi beaucoup que je puisse lui dire ?

04/03/2009, 18h35

Message supprimé par son auteur.

Dr. Gregory House · 04/03/2009, 23h21

Citation :

Publié par Rhaitz

Wes Toland
Wes est une fille de 27 ans qui fait partie de Zebra Incognito. Wes devient The Zebra en concert. Wes se trouve en ce moment à Los Angeles, ici : LA Rock.

Je suppose que c'est le dernier tresor national que personne avais utiliser (que Jonas avait dis)

-_-'

Perdre dix ans ouais, mais devenir une nana, non merci ça ira. Ca doit etre le trésor national du Brésil ça.

Fartha · 05/03/2009, 09h55

J'enseigne à Johannesburg le temps de toucher mon million...

Je devrais en partir le 11 mars.

05/03/2009, 13h08

Message supprimé par son auteur.

Fartha · 05/03/2009, 14h22

Citation :

Publié par Acaedan

J'ai fait une demande pour être ton apprenti Je veux bien maîtrise de la communication !

Au fait, pour voler un objet, il faut la compétence de crime ? ou de vol à la tire ?

Je t'accepte. Mais je pourrais enseigner qu'à partir de 22h ce soir au plus tôt. J'attends un autre élève pour cette comp.

Sinon, je pense que Crime suffit vu que je crois pouvoir le faire. Vol à la tire doit pouvoir monter les chances de réussite.

Rhaitz · 06/03/2009, 08h08

Bon un de mes bandmate est dans "the lake" donc je vais devoir le kick soon

Ca me saoule :>

Va falloir que je trouve 1 ou 2 personne pour remplacer :x

Selty · 06/03/2009, 10h35

T'es dans quel style de musique ?
(Je suis en rock, j'ai un bandm8, pour l'instant c'était lui qui gérait les tournées mais là il ne peut plus trop. Résultat : On stagne dans le classement, alors qu'on tourne quand même à la centaine d'étoiles chacun et santé/humeur haute. Donc je me dis que, pourquoi pas, si ça intéresse un groupe, on pourrait peut-être fusionner.)

Dr. Gregory House · 06/03/2009, 14h44

Citation :

Publié par Rhaitz

Bon un de mes bandmate est dans "the lake"

C'est quoi the lake ?

#40659 Invité	Message supprimé par son auteur.
03/03/2009, 17h53

cricri Alpha & Oméga	d un autre cote le pb est plus simple pour nous suffit de faire un tour complet en minimisant le temps de parcourt entre chaque ville (on a 1 jour pour chaque ville) on a pas besoin de calculer un tour complet sans arret
03/03/2009, 22h45

Rhaitz Alpha & Oméga	Wes Toland Wes est une fille de 27 ans qui fait partie de Zebra Incognito. Wes devient The Zebra en concert. Wes se trouve en ce moment à Los Angeles, ici : LA Rock. Je suppose que c'est le dernier tresor national que personne avais utiliser (que Jonas avait dis)
04/03/2009, 04h00

Aiina Alpha & Oméga	Ohhh mon ex bandm8 est devenu une nana, god damn c'est quoi ce bordel. :O Il a rajeunit de 10 ans aussi... Par contre, il a gardé son prénom, ça fait un peu trans du coup. Je me vois mal m'appeler ross avec un perso féminin... :x
04/03/2009, 09h46

Lwevin Myan Alpha & Oméga	Le truc, c'est que c'est pour 12 villes (dixit ton post), donc à ce niveau, effectivement, on peut explorer toutes les possibilités, ce n'est pas énorme. Comme c'est une factorielle, 12! est calculable, 500 millions de possibilités, ce n'est rien. 41! l'est beaucoup moins. Donc, non, les techniques ne sont pas "connues". (D'ailleurs, plutôt que le programme, le source aurait été mieux)
04/03/2009, 10h26

Fartha Alpha & Oméga	Citation : Publié par Dhu C'est fort tout de même Et oui, merci
04/03/2009, 14h20

Rhaitz Alpha & Oméga	Un de vous connais quelqun qui enseigne spin doctor mastery ? et quelqun qui serais pret a me suivre pour les 2 jr de teach ? Et a quel prix ?
04/03/2009, 17h42

Fartha Alpha & Oméga	Je l'enseigne en ce moment. Mais peu de chance que je puisse me déplacer (vis à vis des autres élèves). Ou alors, il faudra beaucoup payer ! mode capitaliste ON
04/03/2009, 17h54

Rhaitz Alpha & Oméga	C'est pas pour moi c'est pour mon bandmate (mais il lui manque encore 1 ou 2 etoile dans un des skills) c'est quoi beaucoup que je puisse lui dire ?
04/03/2009, 18h02

#40659 Invité	Message supprimé par son auteur.
04/03/2009, 18h35

Fartha Alpha & Oméga	J'enseigne à Johannesburg le temps de toucher mon million... Je devrais en partir le 11 mars.
05/03/2009, 09h55

#40659 Invité	Message supprimé par son auteur.
05/03/2009, 13h08

Rhaitz Alpha & Oméga	Bon un de mes bandmate est dans "the lake" donc je vais devoir le kick soon Ca me saoule :> Va falloir que je trouve 1 ou 2 personne pour remplacer :x
06/03/2009, 08h08

Selty [XIII] Alpha & Oméga	T'es dans quel style de musique ? (Je suis en rock, j'ai un bandm8, pour l'instant c'était lui qui gérait les tournées mais là il ne peut plus trop. Résultat : On stagne dans le classement, alors qu'on tourne quand même à la centaine d'étoiles chacun et santé/humeur haute. Donc je me dis que, pourquoi pas, si ça intéresse un groupe, on pourrait peut-être fusionner.)
06/03/2009, 10h35

Dr. Gregory House Alpha & Oméga	Citation : Publié par Rhaitz Bon un de mes bandmate est dans "the lake" C'est quoi the lake ?
06/03/2009, 14h44

[Jeu sympa ET gratuit] Popomundo (#9)

Connectés sur ce fil