💾 Archived View for unbon.cafe › lejun › posts › 20240831_postierChinois.gmi captured on 2024-08-31 at 12:20:56. Gemini links have been rewritten to link to archived content
-=-=-=-=-=-=-
À l'image du problème du voyageur de commerce basé sur la visite de sommets, le problème du postier chinois est basé sur la visite des arcs d'un graphe.
Ce problème est utilisé comme modèle pour des applications telles que l'optimisation de trajets sur un réseau routier : pour son entretien courant, ou des relevés photographiques[1].
L'approche la plus simple pour résoudre le problème est d'utiliser le degré des nœuds, de manière à mettre en évidence un circuit eulérien aisément résoluble[2].
Un nœud peut être de dégré pair ou impair. Dans le premier cas il est possible de traverser le nœud autant de fois qu'il y a de paires d'arêtes le traversant, dans le second cas, il est indispensable de parcourir deux fois la même arête à l'exception du cas particulier où le graphe est ouvert.
Les nœuds d'un réseau peuvent ainsi se simplifier en degrés :
Dans le cas d'un graphe fermé, où le début et l'arrivée sont au même point, il est indispensable de n'avoir que des nœuds de degré pair. Si le graphe est ouvert, alors les marges de manœuvre sont amplement augmentées, il est possible d'avoir jusqu'à deux sommets de degré impair.
Plus que deux sommets impairs implique nécessairement des arêtes répétées, non réalisées, ou un second itinéraire (un second postier ?).
Faute de compétence, je suis incapable de développer la solution nécessaire ; Dans l'idéal, le problème étant NP-complet, une solution simple à développer serait un assistant de création de graphe capable de :
L'indépendance du fond de carte et du graphe est cruciale en terme de versatilité. Il existe déjà nombre de moteurs d'itinéraires en ligne, mais tous souffrent du même problème qu'est le graphe OpenStreetMap. La richesse des informations font qu'il est compliqué de générer un graphe automatiquement, et que les règles arbitraires usuelles sont difficilement paramétrables (ex : nombre de voies, restriction d'accès,…). Avoir un graphe indépendant c'est pouvoir relier manuellement les nœuds de degré impair, que ce soit en utilisant un tronçon en dehors du périmètre défini, en ajoutant un tronçon mineur qui n'aurait autrement pas été réalisé, ou simplement en déplaçant les extrémités de l'itinéraire.
La solution imaginée serait à la fois efficace et légère. En raison de ce dernier critère je ne pense pas pertinent de forker uMap ou bRouter qui sont des projets relativement lourds.