This post is a French translation of this previous post. — Ce billet est une traduction française du billet original en anglais, réalisée avec Mc et Jill-Jênn.

En avril 2014, Google Paris a organisé un concours de programmation dans ses locaux à Paris : le Google Hash Code. Le problème à résoudre était plutôt amusant. Nous le présentons dans cet article, en précisant certaines stratégies adoptées par les équipes des Écoles normales supérieures. L'édition 2015 du concours est en cours, l'épreuve de qualification a eu lieu jeudi 12 mars (les inscriptions sont closes) ; c'est la nouvelle édition de l'épreuve qui nous a motivés pour rédiger notre solution pour l'épreuve de l'an dernier.

Les Écoles normales supérieures se sont particulièrement bien défendues lors de l'édition 2014, en décrochant les rangs 1, 2, 3, 4, 5, 7, 10 (les auteurs de cet article ont obtenu les rangs 5 et 7) et ont amélioré leurs résultats significativement dans les jours qui suivaient l'épreuve, l'échéance ayant été repoussée afin de pouvoir accueillir de nouvelles solutions.

Description du problème

L'énoncé complet est disponible sur le site officiel du concours.

On dispose d'une carte de Paris (à partir de données OpenStreetMap) qui décrit toutes les intersections et rues de la ville¹. Comme dans la vraie vie, certaines rues sont à sens unique. Les segments sont étiquetés par leur longueur (en mètres) et leur durée de parcours (en secondes). Le problème est le suivant : à partir de 8 voitures Street View qui partent des locaux de Google Paris (rue de Londres), combien de mètres de rues est-il possible de parcourir au maximum en un temps limité de 15 heures ? On peut choisir d'emprunter certaines rues plusieurs fois, mais leur longueur ne sera comptée qu'une seule fois dans le total des mètres parcourus.

Le but est donc de déterminer un itinéraire pour les 8 voitures afin de parcourir un maximum de mètres différents de rues de Paris dans le temps imparti.

La méthode exhaustive

Naturellement, on peut en principe résoudre le problème en énumérant toutes les routes possibles pour les 8 voitures et en choisissant la meilleure. Il y a un nombre fini de telles routes, donc cette approche identifiera nécessairement la solution optimale. Ceci peut suffire pour un mathématicien, mais pas pour un informaticien : les chemins sont trop nombreux, ainsi il serait impossible de tout les explorer en pratique. (Le concours lui aussi est en temps limité…)

À titre de comparaison, s'il s'agissait de n'énumérer que les routes possibles en 10 heures pour une voiture atteignant à chaque minute une nouvelle intersection d'où partent au moins deux routes, il y aurait déjà $2^{10\times 60}$ chemins possibles, soit environ ${10}^{180}$. Même si chaque atome du système solaire était un supercalculateur, on ne parviendrait pas à explorer toutes ces routes avant l'extinction du Soleil.

L'algorithme glouton

À l'inverse, une des approches les plus simples (outre les méthodes purement aléatoires) consiste utiliser un critère d'optimisation glouton : par exemple, choisir la rue la plus longue, la rue la plus rapide à parcourir, etc.). On planifie le parcours des voitures rue par rue, et on utilise le critère à chaque intersection pour choisir simplement la rue dans laquelle on se dirige ensuite.

Glouton basique

On considère pour commencer une unique voiture. Adoptons l'approche suivante : lorsque la voiture aboutit à une intersection qui lui permet de traverser des rues qu'elle n'a pas encore explorées, on choisit l'une d'entre elles : la plus longue, ou bien celle où l'on pourra visiter le plus de mètres par seconde. En revanche, si toutes les rues accessibles ont été visitées, on en choisit une au hasard. On réitère ce procédé tant qu'il reste du temps, et on fait de même pour les autres voitures.

Cette méthode gloutonne aura une performance correcte. Cela dit, de nombreux ajustements sont possibles, par exemple : planifier l'itinéraire de toutes les voitures simultanément plutôt que l'une après l'autre, ou bien commencer par envoyer les voitures à des intersections bien réparties dans Paris pour que chacune n'empiète pas sur le territoire des autres.

Cependant, l'inconvénient principal des solutions gloutonnes est qu'elles sont incapables d'anticiper. Par exemple, lorsqu'on choisit une rue au hasard parmi celles déjà visitées, on ne tente pas de se rapprocher d'un gisement de rues non visitées. Ainsi, une réflexion hâtive (c'est de là que vient le mot "glouton") à partir d'informations partielles risque d'entraîner les voitures dans un dédale de rues déjà visitées.

Méthode gloutonne avec anticipation

On peut combiner la méthode gloutonne avec une recherche exhaustive qui se limite aux quelques prochains choix à faire. En d'autres termes, pour choisir la prochaine rue à suivre à chaque intersection, on ne le fera pas uniquement sur la base des mètres que cela permet de visiter en une étape. À la place, on peut par exemple considérer tous les chemins possibles de longueur 10 et choisir de traverser la première rue de celui qui donne les meilleurs résultats en dix étapes. On peut ensuite planifier le trajet de toutes les voitures en parallèle suivant cette idée. La longueur des chemins à considérer (dans cet exemple, "10") est bien entendu paramétrable ; en général, plus elle est longue, meilleurs seront les résultats, mais plus il sera difficile de les calculer.

Cette idée simple est facile à implémenter et donne des résultats plutôt satisfaisants. Une de nos équipes l'a essayée avec des chemins de longueur 17, sauf erreur, et il semble que plusieurs des dix meilleures équipes l'ont également suivie.

La méthode intelligente

Bien sûr, l'objet de ce billet est de décrire la solution intelligente, celle que l'on a implémentée au terme de l'épreuve, pour le concours étendu.

Voir le problème comme une recherche de chemin eulérien

Pour avoir la bonne intuition, il faut remarquer le lien entre le problème étudié et celui de la recherche d'un chemin eulérien dans un graphe, c'est-à-dire un chemin qui passe par chaque arête une et une seule fois (ou, autrement dit, parcourt le graphe "sans lever le crayon"). En effet, si l'on voit le plan de Paris comme un graphe, où les intersections sont les sommets et les rues sont les arêtes, un chemin eulérien dans ce graphe serait la solution idéale, qui parcourt chaque rue une unique fois sans perdre de temps dans des rues déjà visitées.

Bien sûr, il faut un peu se forcer pour faire ce rapprochement. Déjà, il y a huit voitures ; mais pour l'instant on supposera qu'il n'y en a qu'une seule, et on partagera le parcours entre les huit voitures plus tard. Ensuite, il y a une limite de temps, et toutes les rues n'ont pas la même valeur en termes de nombre de mètres photographiés ; mais on négligera cela et on prétendra être capable de visiter toutes les arêtes dans le temps imparti (on verra que ce n'est pas une supposition si irréaliste ;)). Ainsi, on ignore complètement la valeur en mètres des rues, et on ne s'intéresse qu'au temps nécessaire pour les parcourir.

Enfin, et c'est là la principale difficulté, le graphe d'entrée est un peu inhabituel, car certaines arêtes ne sont pas orientées, mais d'autres le sont, à savoir les rues à sens unique. À cause des sens uniques, il va falloir s'intéresser au problème du graphe eulérien orienté, et il va donc falloir choisir une orientation pour les arêtes non-orientées.

Soyons précis : à proprement parler, il sera impossible de trouver un chemin eulérien. Il est facile de démontrer la célèbre caractérisation suivante des graphes qui ont un chemin eulérien (appelons-les les graphes eulériens) : le degré entrant de chaque nœud (le nombre d'arêtes qui pointent vers lui) doit être égal à son degré sortant². Bien sûr, le graphe d'entrée n'a aucune raison de remplir cette condition. Cependant, pour le problème du Hash Code, il n'est pas vraiment interdit de parcourir la même arête plusieurs fois ; c'est juste qu'on préfère éviter de le faire parce que ça fait perdre du temps.

Ainsi, on tente de rendre le graphe eulérien, en deux étapes. Premièrement, on choisira une direction pour orienter toutes les arêtes qui ne le sont pas, et ce d'une manière qui aide à rendre le graphe "plus eulérien". Ensuite, on ajoutera des arêtes pour le rendre réellement eulérien, afin de matérialiser la possibilité (dispendieuse) de parcourir une deuxième fois des arêtes visitées par ailleurs (c'est-à-dire des arêtes déjà visitées ou qui seront visitées de toute manière à un point ultérieur de la solution).

Orienter les arêtes non-orientées

Pour se ramener au problème du calcul d'un chemin eulérien orienté, il faut choisir une orientation pour toutes les arêtes non-orientées du graphe. Pour que ce problème de recherche de chemin eulérien soit plus facile à résoudre sur le graphe ainsi obtenu, on tentera d'orienter les arêtes d'une façon qui minimise la somme, sur tous les sommets, de la différence entre degré entrant et degré sortant. Intuitivement, plus cette valeur est petite, moins il faudra ajouter d'arêtes pour rendre le graphe eulérien.

Introduisons un peu de terminologie. Un sommet est dit surchargé (dans le graphe original, ou dans un graphe orienté obtenu à partir de ce dernier pour un certain choix d'orientation d'arêtes) si son degré entrant, en ne comptant que les arêtes orientées, est plus petit que son degré sortant. Il est dit sous-chargé dans le cas contraire, et équilibré si les deux degrés sont égaux. La charge d'un sommet est la différence entre son degré entrant et son degré sortant (elle est strictement positive pour un sommet surchargé, et strictement négative pour un sommet sous-chargé).

Comment choisir à présent la meilleure orientation pour les arêtes ? Le choix terminologique donnent déjà des indices : on voudrait orienter les arêtes de sorte à permettre aux sommets initialement surchargés de "transférer" une partie de leur charge aux sommets sous-chargés, suivant des chemins orientés, qui doivent être disjoint pour éviter de compter deux fois les arêtes intermédiaires. Il se trouve que l'on peut formuler cela proprement comme un problème de flot maximum.

Les sommets surchargés et sous-chargés sont respectivement représentés comme des sources et des puits dont la capacité est égale à leur charge. Chaque arête non-orientée est représentée comme une paire d'arêtes orientées allant dans chaque direction, leur capacité étant fixée à 1. Les arêtes déjà orientées sont ignorées.

Le problème de flot correspondant peut être résolu à l'aide de n'importe quel algorithme de flot. Par le théorème des flots entiers, le flot suivant chaque arête est de 0 ou de 1. Ainsi, le résultat du problème de flot décrit une façon d'orienter certaines des arêtes non-orientées (mais pas toutes), suivant la direction du flot qui passe par elles.

Il reste le problème que certaines arêtes du résultat n'ont pas d'orientation spécifiée, à savoir celles qui n'étaient pas utilisées du tout dans le flot optimal. Pour régler ce problème, il suffit d'orienter toutes les arêtes restantes au hasard. Bien sûr, ceci peut faire croître la somme que l'on cherche à minimiser, et pour remédier à cela on effectue ensuite l'amélioration suivante, que l'algorithme de flot avait déjà vérifiée avant la phase d'orientation aléatoire : pour tout chemin orienté qui utilise exclusivement les arêtes nouvellement orientées, si l'on peut diminuer la somme à optimiser en inversant la direction du chemin (c'est-à-dire que l'origine du chemin était sous-chargée et sa destination était surchargée), alors on inverse l'orientation de cette manière. Ceci incrémente la charge de l'origine, décrémente la charge de la destination, et ne change rien aux autres charges, donc c'est une amélioration. Pour effectuer cela de façon efficace, notez qu'il suffit de considérer toutes les paires de sommets. Dès que l'on trouve une paire d'un sommet sous-chargé et d'un sommet surchargé¸ on peut rechercher un chemin allant de l'un à l'autre, et l'inverser si on en trouve un.

Ainsi, à la fin de ce processus, on obtient un graphe orienté où l'on a tenté de minimiser la somme des différences entre le degré entrant et le degré sortant, sur tous les nœuds, pour rendre le graphe aussi eulérien que possible. Il reste à le rendre véritablement eulérien en ajoutant des arêtes pour que tous les sommets soient équilibrés.

Ajouter des arêtes

Intuitivement, les arêtes que l'on veut ajouter pour rendre le graphe eulérien correspondent à la possibilité d'ajouter au chemin des arêtes parcourues par ailleurs.

En d'autres termes, si on ajoute une arête du sommet $i$ au sommet $j$, cela signifie que l'on va aller du sommet $i$ au sommet $j$ suivant un chemin d'arêtes qui seront visitées par ailleurs. Tout le temps passé dans de tels chemins est perdu, et ne contribue en rien à l'objectif. Ainsi, le coût d'ajouter une arête de $i$ à $j$ devrait être la durée nécessaire pour aller de $i$ à $j$ suivant n'importe quel chemin dans le graphe. Pour être plus précis, on peut dans ce cadre suivre un chemin qui viole l'orientation que nous avions choisie pour les arêtes non-orientées, et cela ne pose pas problème ; donc on parle vraiment de la durée d'un plus court chemin dans le graphe original.

Ainsi, on commence par précalculer la durée du plus court chemin entre toutes les paires de sommets du graphe original, à l'aide de l'algorithme de Floyd-Warshall.

Ensuite, on représente le problème de choisir les arêtes à ajouter comme un problème de couplage de poids minimal dans un graphe biparti pondéré. D'un côté du graphe biparti, on place les sommets qui sont surchargés dans le graphe obtenu à l'issue de la phase précédente, copiés en un nombre d'exemplaires égal à leur charge. On crée de la même manière l'autre côté du graphe biparti avec les sommets sous-chargés³. Le graphe biparti dispose également d'une arête entre chaque paire de sommets de chaque partie, dont le poids est le temps du plus court chemin du premier au second.

À présent, un couplage parfait dans ce graphe biparti représente une façon d'ajouter le bon nombre d'arêtes d'une manière qui équilibre tous les sommets, et imposer que le poids d'un tel couplage soit minimal signifie que l'on veut minimiser le temps perdu à suivre des arêtes qui sont visitées par ailleurs. On utilise ainsi l'algorithme hongrois pour résoudre ce problème, et pour compléter le graphe orienté obtenu à l'issue de la phase précédente pour le rendre eulérien.

Construction du chemin eulérien

Le graphe obtenu est maintenant orienté, et chaque sommet est équilibré, donc on peut y construire un chemin eulérien. Pour le calculer, une simple approche gloutonne suffit. (Il y a peut-être des améliorations possibles pour optimiser par rapport aux étapes suivantes, mais nous n'en avons pas cherché.)

Depuis le chemin eulérien, en remplaçant les arêtes qui ont été ajoutées dans la phase précédente par les plus courts chemins auxquels elles correspondent, nous obtenons un itinéraire qui est une assez bonne solution pour le parcours de toutes les rues de Paris par une unique voiture en le moins de temps possible.

Partage du chemin entre voitures

On se rappelle à présent que l'on a huit voitures et non une seule, et qu'il faut donc découper la route obtenue entre les voitures.

Voici la méthode suivie. Prenons la première voiture, et faisons-lui suivre le début du chemin jusqu'à un quart du temps alloué. Ensuite, en considérant le reste du chemin qu'elle peut parcourir jusqu'à la fin de son temps, on cherche le sommet qu'elle traverse qui est le plus rapide à atteindre depuis le point de départ (dont on rappelle qu'il s'agit des bureaux de Google). La première voiture va jusqu'à ce point, et s'arrête. La voiture suivante prend le plus court chemin jusqu'à ce point, poursuit sa route suivant la suite de l'itinéraire pendant un quart du temps alloué, puis continue jusqu'au point le plus proche du point de départ obtenu de la même manière. On répète cela jusqu'à la dernière voiture, qui s'occupe de tout le reste de l'itinéraire.

Bien entendu, si l'on coupe le chemin à un point proche du point de départ, c'est pour minimiser le temps perdu par la voiture suivante pour reprendre l'itinéraire. Cette solution donnera toujours trop de travail à la dernière voiture, mais on verra plus tard comment équilibrer la durée des trajets des voitures. Si on force les voitures à parcourir l'itinéraire pendant au moins un quart du temps alloué, c'est pour rendre cet équilibrage plus facile, en garantissant que les parcours de toutes les voitures sont suffisamment longs pour se rencontrer de nombreuses fois.

Le trajet obtenu constitue la solution initiale pour huit voitures. Il reste à l'optimiser.

Optimisations

On itère maintenant un certain nombre d'optimisations destinées à modifier légèrement le chemin en l'améliorant, jusqu'à ce que l'on juge que la qualité du résultat est suffisante.

Bien entendu, toutes les optimisations ne sont pas aussi efficaces, et l'ordre dans lequel elles sont appliquées peut engendrer des différences significatives. Il est difficile de retrouver exactement l'ordre dans lequel elles ont été appliquées pendant le concours, ni le nombre d'itérations, mais il n'y avait de toute manière pas beaucoup de logique pour justifier ces choix.

Écrémage

Pour tout sous-chemin d'un chemin d'une voiture, qui consiste uniquement d'arêtes déjà visitées par ailleurs, on peut le remplacer par un plus court chemin entre les extrémités du sous-chemin, calculé à l'aide du Floyd-Warshall précédemment évoqué.

Échange de boucles

Supposons qu'une voiture se déplace d'un sommet $i$ à un sommet $j$, puis effectue un cycle $C$, puis se déplace à nouveau de $j$ à $i$, et l'arête entre $i$ et $j$ est déjà visitée par ailleurs. Si on peut trouver une voiture qui passe par n'importe lequel des sommets de $C$, alors cette voiture peut s'occuper de tout le cycle $C$ sur son chemin, et la première voiture peut économiser $C$ et l'aller-retour entre $i$ et $j$ (l'économie totale est donc de deux fois la longueur de l'arête $i$—$j$).

Bien entendu, ceci peut contribuer à déséquilibrer la longueur du trajet des voitures, mais on s'occupera de ces situations plus tard.

Raccourcissement

Si une voiture termine son chemin par un sous-chemin déjà visité par une autre voiture, on peut simplement le supprimer.

Exploration exhaustive

Pour tout sous-chemin de chaque chemin de chaque voiture, jusqu'à une certaine longueur, on vérifie si le sous-chemin peut être remplacé par un chemin plus court, qui visite tout de même toutes les rues du chemin qui ne sont pas visitées par ailleurs. Dans ce cas, on remplace le sous-chemin par le chemin trouvé. Ceci diffère de l'écrémage en ce sens que les sous-chemins peuvent inclure des arêtes qui ne sont pas visitées par ailleurs ; dans ce cas, le remplacement devra également passer par ces arêtes, possiblement dans un ordre différent.

Équilibrage

Jusqu'ici, on n'a pas tenu compte de la contrainte de temps maximal (15 heures). Celle-ci a besoin d'être satisfaite par toutes les voitures ; on ne peut donc pas se contenter d'une solution où une voiture a un trajet beaucoup plus long que les autres. Du reste, si on parvient à trouver une solution qui passe par toutes les arêtes (et ce fut le cas !), la qualité d'une solution est jugée selon son temps restant, c'est-à-dire $T-{max}_{c\in 1,\dots ,8}{t}_c$ où $T$ est la limite de temps, et $t_c$ le temps pris par la voiture $c$.

Idéalement, on voudrait donc que toutes les voitures effectuent des trajets qui prennent le même temps. Ceci signifie qu'il est souhaitable d'échanger des portions longues du trajet des voitures les plus occupées avec des portions plus courtes du trajet des voitures moins occupées.

En pratique, on recherche des paires de sommets $x$ et $y$ telles que deux voitures passent par $x$ puis par $y$. En général, les chemins des deux voitures entre $x$ et $y$ auront une longueur différente. Ainsi, si échanger les chemins permet de diminuer la différence de durée entre l'itinéraire des deux voitures, alors on procède à l'échange.

Cette méthode gloutonne peut être itérée aussi longtemps que nécessaire. En fait, comme les chemins des voitures ont tendance à se croiser très souvent, la méthode fonctionne très bien et converge rapidement vers un état où toutes les voitures suivent des itinéraires dont la durée est la même, à la seconde près, peu importe les itinéraires initiaux.

Résultats

La stratégie intelligente décrite ici parvient à parcourir toutes les rues de Paris dans le temps alloué (et même en 9 minutes de moins). Dommage de ne pas l'avoir réussi pendant le concours lui-même (plutôt que pendant l'extension), mais c'est déjà ça ! :)

État de l'art

Nous avons développé toutes ces méthodes par nous-mêmes, et n'avons pas regardé sérieusement l'état de l'art des méthodes utilisées par des gens qui ont déjà essayé de résoudre des problèmes similaires. En fait, notre problème est connu comme le problème du postier chinois, car il est également utile pour optimiser les distributions postales (et a été étudié par un mathématicien chinois).

Plus spécifiquement, notre version est le "$k$-mixed postman problem", car on a plusieurs voitures ($k$=8), et car le graphe est mixte : certaines des arêtes sont orientées, d'autres non. De manière assez surprenante, la solution optimale peut être calculée en temps polynomial pour les versions orientées et non-orientées⁴, mais la version mixte est NP-difficile⁵.

Il serait intéressant de comparer le résultat de notre méthode à l'état de l'art. Nous nous sommes rapidement comparés à des résultats de référence sur des jeux de données existants et nous n'avons pas de raison de penser que nos algorithmes sont meilleurs. Mais peu importe, nous nous sommes bien amusés. :)

Remerciements

Les idées de ce billet ne sont pas les miennes : à peu près tout a été fait par d'autres élèves de l'ENS. Les étapes de la solution intelligente, hormis les optimisations subséquentes, ont été conçues et implémentées par gnomnain (code). Et les optimisations par elarnon (code), and Mc and mehdi (code). (Tout le code est "en écriture seule" (write-only) et ne contient aucune documentation d'aucune sorte, je déconseille de tenter de l'utiliser.)

Ce billet a été écrit à partir d'une version préliminaire de Mc. Merci à Jill-Jênn, elarnon, Armavica et gprano pour leur relecture et remarques sur la version originale.