Le problème du voyageur de commerce appliqué aux images (via @zachlieberman)

Penguins

Le problème du voyageur de commerce est un vieux problème “insoluble” en informatique qui consiste, à partir d’un ensemble de villes séparées par des distances données, à calculer le plus court chemin qui les relies toutes.

Pour donner un ordre de grandeur, le nombre de chemins possibles passant par 69 villes est un nombre d’une longueur de 100 chiffres.

Dans le cas présent et de son adaptation aux images, les “villes” (du voyageur de commerce) sont remplacées par des points, le contraste de l’image est traduit par une plus grande densité de points dans les zones sombres et inversement.

L’image produite au final est donc construite à partir d’une seule ligne (un seul trajet), passant une seule fois par tous les points et revenant à son point de départ.

La version pdf sur le site original est bien plus intéressante. Et d’autres exemples y sont également visibles.

http://www.cgl.uwaterloo.ca/


Posted

in

by

Tags: