Beim "Problem des Handlungsreisenden" geht es darum, die kürzeste Rundreise für eine gegebene Anzahl von Städten zu finden. Was einfach klingt, lässt sich nur für eine kleine Anzahl von Wegstationen exakt lösen, denn mit jeder weiteren Stadt steigt die Zahl der Kombinationsmöglichen enorm an: Bei zehn Städten gibt es rund 181 000 mögliche Routen, die berechnet und verglichen werden müssen. Bei elf Städten sind es bereits über 1,8 Millionen, und bei 20 Städten liegt ihre Zahl im Trillionenbereich.

Zwei Forscher vom Centre for Unconventional Computing der University of the West of England in Bristol haben nun ein Programm entwickelt, in der simulierter "Schleim" nach Lösungen für das Problem sucht. Wie Jeff Jones und Andrew Adamatzky berichten, findet ihr Algorithmus zwar nicht garantiert die beste, aber in den allermeisten Fällen eine sehr gute Lösung.

Die von ihnen "Blob" genannte intelligente Masse besteht aus Tausenden beweglicher Pünktchen, die von einer Art Lockstoff angezogen werden. Alle fraglichen Städte sondern diesen Lockstoff ebenso ab wie die beweglichen Pünktchen selbst. Dadurch ist sichergestellt, dass die Masse ihren inneren Zusammenhalt bewahrt und immer jede Stadt bedeckt. Wenn nun einzelne Pünktchen kontinuierlich eliminiert werden, schrumpft sie so in sich zusammen, dass nur noch Verbindungslinien zwischen den Städten zurückbleiben.

Das Resultat vergleichen die Forscher mit einer Insel, entlang deren Küstenlinie die Städte verbunden werden müssen, um die Tour zu ermitteln. Diesen letzten Interpretationsschritt, also das Nachfahren der Linie, erledigten die Forscher noch per Hand. Zum Test ließen sie das Programm jeweils sechs Lösungen für insgesamt 20 verschiedene 20-Städte-Aufgaben berechnen.

Jones und Adamatzky sind nicht die Ersten, die einen unkonventionellen Ansatz zur Lösung dieses Problems vorschlagen. Gute Resultate erhält man auch, wenn man Suchstrategien aus dem Tierreich entlehnt wie etwa die der Schwarmintelligenz von Ameisen. Das Problem auf physikalische Vorgänge in Materialien zu übertragen, kann ebenfalls praktikable Lösungen liefern. So kann man beispielsweise zwischen den Städten aufgespannte Gummihäute simulieren, die versuchen, ihre Oberfläche zu minimieren. Der Ansatz der beiden britischen Forscher liegt in der Mitte zwischen physikalischen und biologischen Vorbildern, denn äußerlich ähnelt er in seinem Verhalten sehr dem Schleimpilz Physarum polycephalum, der ebenfalls solche Aufgaben löst. Allen diesen Ansätzen ist gemein, dass sie heuristisch arbeiten, also oft, aber keinesfalls mit Garantie ein optimales Ergebnis erzielen.

Der Vergleich mit einer Software, die das Problem des Handlungsreisenden nach dem Zeit raubenden exakten Verfahren berechnet, verriet den Forschern dann, dass ihr Schleim im Mittel eine beste Tourlänge von 1,04 erreichte. Hätte das Programm immer die tatsächlich kürzeste Route gefunden, läge dieser Wert bei 1. Einen konkurrenzfähigen und vor allem praktikablen Ansatz zur Lösung dieses Problems, das im Alltag zum Beispiel bei verschiedensten Minimalisierungsaufgaben, aber auch ganz konkret bei der Planung von Wegrouten virulent wird, haben sie damit wohl nicht gefunden – wollten das aber auch gar nicht, wie sie freimütig einräumen: Ihr Verfahren sei interessant, weil es so einfach sei und vor allem ein Novum darstelle.