Quelle est la meilleure configuration pour relier entre eux 30 points ? C’est à cette question, vieille de 32 ans, que des chercheurs américains viennent enfin de répondre.
C’est un problème mathématique vieux de 32 ans : comment relier par le tracé le plus court 30 villes américaines ? D’apparence tout bête, ce casse-tête répondant au doux nom de Nug30 vient enfin d’être résolu par des chercheurs de l’université d’Iowa et du Laboratoire national d’Argonne aux ...tats-Unis. L’expérience a nécessité plus de 1 000 ordinateurs mis en parallèle tournant non-stop pendant une semaine.
Ce n’est pas tout. Pour terrasser la bête, les mathématiciens ont développé un logiciel d’optimisation des combinaisons qui s’appuie sur un algorithme éliminant progressivement les liens qui n’aboutiront jamais à une architecture optimale. Sans cette méthode, un ordinateur aurait beau tester mille milliards de combinaisons à la seconde, l’opération durerait un temps équivalent à 140 fois l’âge de l’univers !
L’intérêt d’un programme de recherche comme Nug30 est qu’il permet de concevoir des agencements où les déplacements sont minimisés. Cela concerne tout particulièrement la logistique : dans les hôpitaux, par exemple, où la distance parcourue par les malades est limitée, ou dans les transports, l’optimisation des trajets conduisant à une baisse des coûts.
http://www-unix.mcs.anl.gov/metaneos/nug30
http://www-unix.mcs.anl.gov/metaneo...