Chapitre 1. Introduction

Commençons cet ouvrage par deux exemples.
Une machine est utilisée pour percer des trous dans des plaques de circuits imprimés. Comme de nombreux circuits sont produits, il est souhaitable que chaque circuit soit fabriqué aussi rapidement que possible. Nous ne pouvons agir sur le temps de perçage de chaque trou qui est fixé, mais nous pouvons chercher à minimiser le temps total de déplacement de la perceuse. Habituellement, les perceuses effectuent des déplacements dans deux directions : la table se déplace horizontalement tandis que le bras de la machine se déplace verticalement. Comme ces deux mouvements peuvent se faire simultanément, le temps nécessaire pour ajuster la machine entre deux positions est proportionnel au maximum des distances horizontales et verticales parcourues. Cette quantité est souvent appelée distance de la norme infini. (Les vieilles machines ne peuvent se déplacer que dans une direction à la fois ; le temps d’ajustement est alors proportionnel à la 1-distance, somme des distances horizontale et verticale.)
Un parcours optimal pour le perçage est donné par un ordre des positions des trous p1, …, pn qui rend minimum la quantité , d étant la distance de la norme infini : si p = (x, y) et p′ = (x′, y′) sont deux points du plan, alors d(p, p′) ≔ max{|x − x′|, |y − y′|}. Un ordre des trous peut être représenté par une permutation, c.-à-d. une bijection π : {1, …, n} → {1, …, n}. La meilleure permutation dépend bien entendu de la position des trous ; pour chaque ensemble de positions, nous aurons une instance spécifique (suivant l’usage, nous utiliserons le terme « instance » de préférence à « exemple »)…