Das Problem des Handlungsreisenden

Die ZEIT berichtet über “Das Problem des Handlungsreisenden” – im Englischen “Traveling Salesman Problem” oder kurz TSP genannt.

Nach der Einleitung, die das Problem am Beispiel der Müllabfuhr, die alle Tonnen auf dem kürzesten Weg leeren muss, bleibt der Bericht leider sehr theoretisch.

Und verschweigt, dass es durchaus Algorithmen gibt, die eine näherungsweise Lösung des Problems ermöglichen – nicht im mathematischen Sinne – für die praktische Anwendung aber sicher hinreichend.

Die pgRouting-Bibliothek enthält beispielsweise entsprechende Routinen.

Hinterlasse eine Antwort