Journal runderground 1 : 9h53m02s

Posté par  (site web personnel) .
Étiquettes : aucune
0
6
mai
2005
Héhé ! Certains ont douté [1], d'autres ont rigolé [1], mais on l'a fait [2]!

Il nous a fallu 9 heures 53 minutes et 02 secondes pour passer dans toutes les stations de métro de Paris !

Je vous rappelle que j'organise un petit concours de logiciel libre pour aider à encore améliorer ce "record".

Allez tous à vos claviers ou à vos cartes oranges !

[1] https://linuxfr.org/~rangzen/17874.html(...)
[2] http://l-homme.net/runderground/(...)

  • # Félicitation !

    Posté par  (site web personnel) . Évalué à 2.

    \o/ Champagne ! \o/

    Bon, reste plus qu'à se laver et à se reposer...

    À quand le prochain record ? :-D

    • [^] # Re: Félicitation !

      Posté par  (site web personnel) . Évalué à 6.

      Le prochain ...
      Sais pas, on est crevé, on a couru à tous les changements plus certains raccourcis genre Porte d'Orléans-Porte de Vanves plutôt que de reppasser par Monparnasse
      On a quand même amélioré le record de 2h30 ...

    • [^] # Re: Félicitation !

      Posté par  . Évalué à 4.

      C'est bien plus beau lorsque c'est inutile !

      • [^] # Re: Félicitation !

        Posté par  . Évalué à 3.

        Un "return" intempestif => deux commentaires ...

        Le logiciel, c'est un problème bien connu de recherche operationnelle, dit "du voyageur de commerce". Malheureusement, à ma connaissance, il n'y a pas de solution mathématique générale. Une solution c'est de calculer tous les itinéraires possibles. Mais, amha, inaplicable vu le nombre de stations (si n est le nombre de station, il y a n ! itinéraires). Mais, peut-être, avec un grand (très grand nombre) d'ordi en cluster sous Linux ...

        • [^] # Re: Félicitation !

          Posté par  (site web personnel) . Évalué à 4.

          Le coup de calcul pour avoir la meilleur solution est effectivement prohibitif.

          Mais il existe des algorithmes pour avoir des solution approchée en un temps raisonnable.
          (par exemple un algorithme génétique http://fr.wikipedia.org/wiki/Algorithme_g(...)énétique#Applications_dans_la_recherche )

          • [^] # Re: Félicitation !

            Posté par  . Évalué à 2.

            Je crois que c'est le genre de problème que l'on résoud aussi avec des Algorithme par colonies de fourmis.

            • [^] # Re: Félicitation !

              Posté par  . Évalué à 3.

              Oui, il y a beaucoup d'algorithmes qui permettent de trouver une solution dite optimale. J'avais lu un document comparant tous ces algorithmes, selone la rapidité, et aussi le choix de la solution (je rappelle qu'une solution optimale n'est pas forcément une meilleure solution).

              De ce que j'ai retenu, en terme de qualité de solution, l'algorithme génétique était un peu moins bon que l'algorithme des fourmis. Cependant, il me semble que l'algorithme génétique était bien plus rapide que son collègue.

              Mais bon, je n'ai plus le lien, et c'étaient des comparaisons sur des implantations particulières.

        • [^] # Re: Félicitation !

          Posté par  (site web personnel) . Évalué à 7.

          Le problème n'est à mon avis pas tant lié au temps de calcul (il y a plein de méthodes approchées pour le problème du voyageur de commerce qui donnent quasiment la solution optimale en très très peu de temps). Le problème, c'est plutôt de connaître précisement les hypothèses du problème.

          Est-ce que tu sais précisement combien un métro met pour aller d'une station à une autre ? Combien tu vas attendre dans une station pour chaque correspondance, à chaque instant de la journée ? Combien de temps tu vas mettre pour marcher/courrir dans la station de métro X ou Y pour prendre ta correspondance ? Combien de temps tu vas marcher/courrir pour relier la station de métro X à la station de métro Y (ça peut parfois être intéressant d'y aller à pattes), etc, etc.

        • [^] # Re: Félicitation !

          Posté par  (site web personnel) . Évalué à 2.

          Le chemin utilisé aujourd'hui a été trouvé par un quadri xeon avec le programme de l'ENS ...

  • # Space Station ?

    Posté par  (site web personnel) . Évalué à 2.

    C'est quelle station ?

    http://rangzen75.free.fr/runderground-1-20050506/dscn2230.jpg(...)

  • # Station Olympiades

    Posté par  . Évalué à 5.

    Fin 2006 ou début 2007, la ligne 14 sera étendue avec une station à côté des tours des Olympiade. (à coté de Tolbiac, mais sans connexion avec cette station)

    Il ne reste donc qu'un an et demi pour battre le record actuel. Après les données du problème auront changées.

  • # C'est interessant

    Posté par  (site web personnel) . Évalué à 1.

    C'est typiquement le genre de truc que j'adore faire.
    :p

    Faudrait que je teste un jour ....

  • # Impresionnant

    Posté par  . Évalué à 3.

    C'est assez impressionnant !

    Mais à quand le parcours de toutes les rues de Paris ? Vous avez le droit au vélo bien sûr. Par contre, il vaut mieux une caméra sans fil avec une voiture qui suit et qui enregistre en permanence, parce que s'arrêter à chaque rue pour la prendre en photo, ça risque d'être très pénible

    :o))

  • # Juste pour savoir...

    Posté par  (site web personnel) . Évalué à 10.

    Tu serais pas un mainteneur Debian? Parce que comme ca je comprendrais mieux pourquoi ca avance pas :p

    Ho, une porte... ==> []

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.