Tour Bitonic - Bitonic tour
En géométrie computationnelle , une visite bitonique d'un ensemble de sites ponctuels dans le plan euclidien est une chaîne polygonale fermée qui a chaque site comme l'un de ses sommets, de sorte que toute ligne verticale traverse la chaîne au plus deux fois.
Tours bitoniques optimaux
Le tour bitonique optimal est un tour bitonique de longueur totale minimale. C'est un exercice standard de programmation dynamique pour concevoir un algorithme de temps polynomial qui construit le tour bitonique optimal. Bien que la méthode habituelle pour le résoudre de cette manière prenne du temps , un algorithme plus rapide avec le temps est connu.
Le problème de la construction de circuits bitoniques optimaux est souvent attribué à Jon L. Bentley, qui a publié en 1990 une comparaison expérimentale de nombreuses heuristiques pour le problème du voyageur de commerce ; cependant, les expériences de Bentley n'incluent pas de circuits bitoniques. La première publication qui décrit le problème de la tournée bitonique semble être une publication différente de 1990, la première édition du manuel Introduction to Algorithms de Thomas H.Cormen , Charles E. Leiserson et Ron Rivest , qui énumère Bentley comme à l'origine du problème .
Propriétés
Le tour bitonique optimal n'a pas d'auto-croisement, car deux arêtes qui se croisent peuvent être remplacées par une paire d'arêtes non croisées avec une longueur totale plus courte en raison de l'inégalité du triangle.
Comparé à d'autres circuits qui pourraient ne pas être bitoniques, le circuit bitonique optimal est celui qui minimise la quantité totale de mouvement horizontal, avec des liens rompus par la distance euclidienne.
Pour les points dans le plan avec des coordonnées entières distinctes et avec des coordonnées en nombre réel qui se trouvent dans un intervalle de longueur ou moins, le tour bitonique optimal est un tour de vendeur itinérant optimal.
Autres critères d'optimisation
Le même algorithme de programmation dynamique qui trouve le tour bitonique optimal peut être utilisé pour résoudre d'autres variantes du problème du voyageur de commerce qui minimisent les combinaisons lexicographiques de mouvement dans un nombre fixe de directions de coordonnées.
Lors de la 5e Olympiade internationale d'informatique , à Mendoza, Argentine en 1993, l'un des problèmes du concours concernait les tournées bitoniques: les candidats devaient concevoir un algorithme qui prenait en entrée un ensemble de sites et une collection d'arêtes autorisées entre les sites et construisait un visite bitonique en utilisant ces bords qui comprenaient autant de sites que possible. Comme pour le tour bitonique optimal, ce problème peut être résolu par une programmation dynamique.
