Pour se déplacer d'un point à un autre sur une carte, il est souvent utile de connaître le plus court chemin. Un premier problème consiste en la construction d'un réseau optimal de chemins entre plusieurs points de la carte, étant données certaines contraintes. Puis, le réseau étant fixé, vient le problème de détermination de chemins optimaux dans le réseau. Ce dernier problème, que nous étudierons ici, fait intervenir la théorie des graphes, dans laquelle un point, un chemin d'un point à un autre, et un réseau de points et de chemins sont appelés respectivement graphe, sommet et arc. Le problème de plus courts chemins d'un sommet à un autre par exemple, se révèle très utile dans la planification de trajectoire dans un réseau routier, ou dans les outils de guidage par satellite. La complexité de tels réseaux nécessite alors l'intervention de l'informatique pour résoudre le problème, et donc la recherche d'algorithmes efficaces. Ainsi naissent les algorithmes de Bellman-Ford que je présenterai ici, et de Dijkstra. L'orientation du problème vers l'informatique fait ensuite naître de nouvelles applications, comme par exemple dans les jeux video, lorsqu'il s'agit de trouver un plus court chemin d'un point à un autre d'une carte divisée en cases appelées noeuds. Tandis que l'algorithme de Bellman-Ford résout le problème formellement, l'algorithme A* (prononcé A étoile ou A star) en est une résolution plus efficace adaptée aux jeux vidéo. Enfin, on peut aussi rechercher le plus court chemin passant par tous les arcs d'un graphe : c'est le problème du postier chinois, ou passant par tous les sommets : c'est le problème du voyageur de commerce. Ce dernier problème est résolu par l'algorithme 2-opt et par l'algorithme de Lin-Kernighan que je présenterai.
Algorithme de Bellmann-Ford
Contrairement à l'algortihme de Dijkstra qui ne peut être utilisé que lorsque tous les arcs ont des poids poitifs ou nuls, celui de Bellman-Ford autorise la présence de certains arcs de poids négatif et permet de détecter l'existence d'un circuit absorbant accessible depuis le sommet de départ. Je vous propose de lire l'algorithme en l'appliquant en même temps à cet exemple pour comprendre son fonctionnement. Voici la version texte complète de l'algorithme. L'algorithme de Bellman-Ford est le plus théorique, le plus général pour la résolution du problème de plus courts chemins. Celui de Dijkstra est moins général mais plus efficace donc en pratique beaucoup plus utilisé. Il trouve des applications dans les services de GPS ou de calculs d'itinéraires en ligne.
Algorithme A*
Pour une meilleure efficacité, il est possible d'orienter la recherche dans la direction de la destination à atteindre, si on connaît cette direction. C'est ce que fait l'algorithme A*, en particulier très utilisé dans les jeux vidéo. C'est un heuristique, c'est à dire qu'il est assez efficace mais qu'on n'est pas sûr de trouver exactement la meilleure solution. Voici une très bonne présentation de l'algorithme, et très accessible. Je vous propose aussi de tester mon programme que j'ai écrit en ActionScript (Flash) ou encore celui-ci trouvé quelque part sur Internet.
Algorithmes de résolution du problème du voyageur de commerce
Si on est un « voyageur de commerce » et qu'on doit faire notre livraison dans plusieurs villes, et rentrer à la maison à la fin de la tournée, on peut avoir besoin de connaître le plus court chemin passant par toutes ces villes. L'algorithme 2-opt résout ce problème :on commence par considérer un chemin arbitraire passant par tous les sommets, et pour tout couple d'arcs de ce chemin on croise les arcs pour voir si on obtient un chemin plus court. L'algorithme de Lin-Kernighan part de la même base, mais au lieu de choisir deux arcs, on construit simultanément pièce par pièce, une liste d'arcs du chemin initial et une liste d'arcs qui devront remplacer les précédents. À chaque étape, on fait des tests pour savoir si le chemin construit sera meilleur, et la détermination des listes d'arcs repose sur le principe de backtracking. Pour trouver effectivement une solution au problème, il est souvent nécessaire de répéter ces algorithmes plusieurs fois. On s'arrête lorsque l'algorithme n'apporte plus de modification au chemin qu'on lui soumet. Mon algorithme 2-opt comprend cette répétition grâce à une boucle while. Par contre il faudra répéter manuellement l'exécution de Lin-Kernighan pour obtenir une solution définitive. Attention, même avec ces répétitions, ces algorihtmes peuvent ne pas aboutir à la meilleure solution possible :ce sont des heuristiques. Voici donc l'algorithme 2-opt que j'ai programmé avec un ami, et mon algorithme de Lin-Kernighan, et les deux transparents que j'en ai faits :ici et là. Voici également l'algorithme original sur lequel je me suis basé pour programmer le Lin-Kernighan, avec des commentaires que j'ai ajoutés, et le document d'où il est tiré. Je vous suggère de comparer l'efficacité des deux algorithmes en comptant le nombre d'exécutions nécessaire à chacun pour trouver une solution définitive d'un même exemple. Ces algorithmes sont certes utiles pour déterminer la meilleure trajectoire pour la tournée d'un livreur, mais ils sont en pratique beaucoup plus utilisés pour déterminer l'ordre d'exécution des tâches à effectuer par une machine connaissant la durée s'écoulant entre chaque couple de tâches. On les utilise également pour déterminer l'ordre de perçage de trous dans circuit imprimé ; j'ai pensé qu'ils pouvaient aussi être utilisés pour déterminer l'ordre dans lequel relier des ampoules d'une enseigne commerciale en un circuit électrique en série.
Lors de l'étude de différents algorihmes de plus courts chemins, j'ai souhaité faire moi-même des tests sur ordinateur pour les expérimenter. J'ai donc réussi à programmer l'algorithme de Bellman-Ford en langage Caml, puis je me suis essayé à programmer l'algorithme A*, en ActionScript cette fois (le langage de programmation des animations Flash), pour avoir une interface graphique. J'ai finalement réussi à débugger totalement ce dernier programme, dont l'implémentation des listes était un peu complexe, à cause peut-être du langage de programmation utilisé mal adapté au problème. Pour la suite, il se trouvait qu'un ami s'intéressait au même domaine que moi pour les TIPE. Nous nous sommes donc associés et nos recherches se sont orientées vers le problème du voyageur de commerce. L'algorithme le plus simple de résolution de ce problème s'appelait le 2-opt, dont nous avons trouvé l'algorithme écrit en pseudo-code. Nous avons donc essayé de l'interpréter en Caml, mais ce n'est qu'après plusieurs essais, mettant en oeuvre différentes implémentations des chemins, et en suivant pas à pas l'exécution de notre programme à l'aide d'un schéma que nous modifiions manuellement à chaque étape, que nous somme parvenus à obtenir un programme opérationnel satisfaisant. Nous ne voulions pourtant pas nous arrêter là. Il existe un autre algorithme, dit de Lin-Kernighan, plus efficace mais plus subtil à comprendre et plus compliqué à implémenté, permettant de résoudre ce problème. Ayant trouvé une documentation complète de cet algorithme (en anglais), nous nous sommes demandé s'il nous était possible de le programmer lui aussi, malgré les difficultés supplémentaires qui s'annonçaient par rapport au 2-opt. Le document présentait là encore l'algorithme en pseudo-code, mais il était cette fois destiné à un langage impératif, tandis que nous ne connaissions que des langages fonctionnels. J'ai alors eu l'idée que la structure impérative d'un algorithme pouvait être reproduite dans Caml à travers le principe de récursivité croisée. Cette méthode, appliquée dans un exemple simple, s'est révélée correcte. Ceci m'a donc permis d'interpréter le code en Caml. La phase de résolution des bugs n'est pas une mince affaire pour un algorithme un peu sophistiqué comme celui-ci. J'ai dû faire afficher des messages à plusieurs endroits du code, pour être au courant de ce qui se passait à chaque instant, puis lire en détail le gros texte obtenu pour trouver à quels endroits apparaissaient les erreurs. Enfin, il a fini par marché.