• sncf et travelling salesman

    Économe des deniers publics en cette période de rigueur budgétaire, la SNCF donne aujourd'hui encore l'exemple par une politique volontariste et courageuse, concentrant son effort sur sa mission première.

    L'entreprise nationale, non contente d'avoir renoncé à son fameux slogan "Tout est possible" et aux investissements dans l'infrastructure, abandonne aujourd'hui la résolution des problèmes np-complets (vous pouvez les aider si vous ennuyez pendant un trajet un peu long).

    "Travelling salesman" est un problème classique d'informatique qui appartient à la catégorie "np complet", ce qui lui confère une propriété remarquable pour l'ingénieur (pas forcément pour le mathématicien) : on ne sait le résoudre qu'au moyen d'algorithmes dont le temps d'exécution augmente exponentiellement (dans le pire cas) avec le nombre de villes qu'on demande de joindre en faisant le moins de kilomètres possible. La résolution de  problèmes np-complets coûte très cher. Le tri alphabétique, en revanche, est extrêmement peu coûteux en ressources.

    sncf et travelling salesman

    Photo personnelle réalisée en gare de Paris Bercy le 11 décembre sur un quai à l'arrivée d'un train

    Pour vous aider, j'ai réalisé cette carte approximative, dans laquelle les numéros indiquent l'ordre de passage dans les gares :

    sncf et travelling salesman

    Source de la carte : L'église de France au moyen âge

    Moi, ça me transporte -objectif atteint, et en plus je commence à comprendre comment est conçue la politique tarifaire de la SNCF.

    PS: merci à marmoute pour le pinaillage d'avoir signalé l'inexactitude de mon explication des problèmes np-complets.

     

    « Une idée naïve pour sécuriser des échangesdécentraliser: supprimer le centre, ou la périphérie ? »

    Tags Tags : ,
  • Commentaires

    Aucun commentaire pour le moment

    Suivre le flux RSS des commentaires


    Ajouter un commentaire

    Nom / Pseudo :

    E-mail (facultatif) :

    Site Web (facultatif) :

    Commentaire :