|
Le problème de Steiner est un problème de minimisation :
comments relier des points donnés (ici les points en bleu) sur un quadrillage
pour que tous les points soient reliés et que la longueur totale soit minimale ?
Si on s'autorise à créer des points nommés "points de Steiner" (ici en rouge), la longueur totale peut en général être minimisée comme sur le schéma suivant
mais le problème de positionner ces points est un problème NP-complet. Même si on force les points à rester sur le quadrillage, l'ajout de points de Steiner peut minimiser la longueur totale ; ainsi le schéma de gauche représente le réseau de départ et celui de droite le réseau optimisé :
|
