Les scientifiques établissent le meilleur algorithme pour parcourir une carte
« C’est un excellent algorithme », a déclaré Érik Demaineinformaticien au Massachusetts Institute of Technology. « C’est très rapide, simple et facile à mettre en œuvre. »
Pour mettre cette procédure en pratique, vous devrez choisir un système d’organisation de vos notes – une structure de données, dans le jargon de l’informatique. Cela peut sembler un détail technique mineur, mais le temps passé à parcourir vos notes chaque fois que vous devez modifier ou supprimer une entrée peut avoir un effet important sur la durée d’exécution globale de l’algorithme.
L’article de Dijkstra utilisait une structure de données simple qui laissait place à des améliorations. Au cours des décennies suivantes, les chercheurs en ont développé de meilleurs, affectueusement surnommés « tas », dans lesquels certains objets sont plus faciles à trouver que d’autres. Ils profitent du fait que l’algorithme de Dijkstra n’a besoin que de supprimer l’entrée du sommet restant le plus proche. « Un tas est essentiellement une structure de données qui vous permet de faire cela très rapidement », a déclaré Václav Rozhoňchercheur à l’Institut d’informatique, d’intelligence artificielle et de technologie (INSAIT) de Sofia, en Bulgarie.
En 1984, deux informaticiens ont développé un conception intelligente du tas cela a permis à l’algorithme de Dijkstra d’atteindre une limite théorique, ou « limite inférieure », du temps requis pour résoudre le problème des chemins les plus courts à source unique. Dans un sens spécifique, cette version de l’algorithme de Dijkstra est la meilleure possible. Ce fut le dernier mot sur la version standard du problème pendant près de 40 ans. Les choses n’ont changé que lorsque quelques chercheurs ont examiné de plus près ce que signifie être « le meilleur ».
Meilleur comportement
Les chercheurs comparent généralement les algorithmes en étudiant leur comportement dans les pires scénarios. Imaginez le réseau routier le plus déroutant au monde, puis ajoutez des schémas de circulation particulièrement déroutants. Si l’on insiste pour trouver les itinéraires les plus rapides dans ces circonstances extrêmes, la version de 1984 de l’algorithme de Dijkstra s’avère imbattable.
Mais j’espère que votre ville ne possède pas le pire réseau routier au monde. Vous vous demandez peut-être : existe-t-il un algorithme imbattable sur chaque réseau routier ? La première étape pour répondre à cette question consiste à faire l’hypothèse prudente que chaque réseau présente les pires schémas de trafic. Ensuite, vous souhaitez que votre algorithme trouve les chemins les plus rapides à travers n’importe quelle disposition graphique possible, en supposant les pires pondérations possibles. Les chercheurs appellent cette condition « optimalité universelle ». Si vous disposiez d’un algorithme universellement optimal pour résoudre le problème plus simple consistant simplement à passer d’un point à un autre sur un graphique, il pourrait vous aider à éviter le trafic aux heures de pointe dans toutes les villes du monde.
