 |
|
|
|
|
|
 |
 |
Neues aus der Welt der Wissenschaft |
|
|
|
|
|
|
Verwandtschaftsstress zum Feiertag |
|
| | | Ostern ist vorbei und der Besuchsmarathon bei der lieben Verwandtschaft auch - zumindest bis zum nächsten Feiertagswochenende. Doch Mathematiker knobeln noch immer an der ungelösten Frage: Wen besuche ich wann und in welcher Reihenfolge? |
|
|
|
|
|
|
Pfingsten naht |
|
| |
Ganz egal ob Ostern, Pfingsten oder Weihnachten: wenn die Feiertage vor der Türe stehen, wollen alle Großeltern, Tanten und Onkeln besucht sein.
Aber wie soll man es angehen, wie bringt man die lästigen Familienbesuche am schnellsten hinter sich? Zuerst zur Tante Gerda nach Eisenstadt und dann zu Onkel Joachim nach Graz, oder besser umgekehrt? Und wann zu Cousin Peter?
|
|
|
|
|
|
Das Problem vom Handlungsreisenden |
|
| |
Das mag ein sehr einfach klingendes Problem sein, nicht so für den Vollblut-Mathematiker. Er kennt diese spezielle Fragestellung auch als das "Problem vom Handlungsreisenden".
Das "Travelling Salesman Problem" (ein Handlungsreisender möchte einer Reihe verschiedener Städte in möglichst kurzer Zeit besuchen) ist zwar bei wenig Verwandtschaft einfach zu lösen. Problematisch wird es aber bei Großfamilien.
|
|
|
|
|
|
Die Qual der Wahl... |
|
| |
Denn gibt es bei 4 anvisierten Punkten nur 6 verschiedene Möglichkeiten, alle Punkte zu besuchen, sind es bei 20 verschiedenen schon 120 Billiarden.
Und hat man - theoretisch gesprochen - 100 Verwandte, die man besuchen muss, dann hat man die Qual der Wahl zwischen noch etwas mehr Reiserouten, nämlich ganz genau 933.262.154.439.441.526.
816.992.388.562.667.004.907.159.682.643.816.214.685.929. 638.952.175.999.932.299.156.089.414.639.761.565.182.862. 536.979.208.272.237.582.511.852.109.168.640.000.000.000. 000.000.000.000.
|
|
|
|
|
|
Grenzenloses Wachstum |
|
| |
Das Problem ist, unter so vielen Möglichkeiten "effizient" die wirklich beste Lösung zu finden. Effizient heißt in diesem Fall, dass der Aufwand der Berechnung nur relativ langsam mit der Anzahl der Ziele steigen soll. Das nennt man dann "polynomialen Aufwand".
|
|
Polynomialer Aufwand
Wenn "n" die Anzahl der Punkte ist, wäre dann die Anzahl der Rechenschritte zum Beispiel "n hoch 2" oder "n hoch 6", also vereinfacht gesagt ein Polynom. |
|
|
 Mehr Info bei britannica.com |
|
|
|
|
|
|
Der "exponentielle" Aufwand |
|
| |
Dummerweise hat der feiertäglich gestimmte Mathematiker aber bei seinem Problem einen so genannten "exponentiellen" Aufwand. Das heißt, dass er bei der Hinzunahme von nur 10 Punkten (oder Lieblings- bzw. Erbtanten), tausendmal mehr rechnen muss.
|
|
Berechnung des Rechenaufwandes
Will man den Rechenaufwand berechnen, steht hier die Anzahl der zu besuchenden Punkte im Exponenten, also zum Beispiel "2 hoch n", wobei es aber relativ egal ist was "unter" dem n steht, die Zahl wird sehr schnell sehr groß. |
|
|
|
|
|
|
Unlösbar trotz Super-Computer |
|
| |
Der entscheidende Unterschied zwischen den beiden Möglichkeiten ist, dass im zweiten Fall die Anzahl der erforderlichen Rechenschritte so schnell wächst, dass man das Problem bisher nicht lösen konnte - unabhängig davon, welchen Super-Computer man verwendet.
Für Mathematiker ist diese Fragestellung interessant, da es gleich eine ganze Klasse von Problemen beschreibt. Und: Wenn man eine dieser Aufgaben löst, hat man automatisch die Lösung für alle anderen.
Nachdem die Forscher nun schon seit über 20 Jahren versuchen, das Handlungsreisenden-Problem schneller als mit "exponentiellem" Aufwand zu lösen, und bis jetzt gescheitert sind, vermuten die Pessimisten, dass es überhaupt nicht möglich ist.
|
|
|
|
|
|
Was zu beweisen wäre... |
|
| |
Jetzt sucht man zumindest nach einem Beweis für diese "Negativaussage". Einfach damit man endlich zu suchen aufhören kann.
Demjenigen, dem es gelingt, winkt auf jeden Fall eine Million Dollar, ausgesetzt vom Clay Institut, das die sieben wichtigsten ungelösten Probleme der Mathematik zur Fahndung ausgeschrieben hat.
|
|
|
|
|
|
Praktischer Nutzen |
|
| |
Eine schnellere Lösung des Problems wäre zum Beispiel für große Firmen interessant, etwa beim Beliefern von Filialen oder beim Aufstellen und Warten von Automaten.
Und bis es keine genaue Lösung gibt, hilft man sich eben mit Näherungslösungen, also mit Ergebnissen, die vielleicht nicht optimal aber doch sehr gut sind.
|
|
Einen neuen Beitrag hat in jüngster Zeit Weixiong Zhang von der Universität Washington geliefert. |
|
|
Der Zhang-Algorithmus |
|
|
|
|
|
|
Minesweeper Math |
|
| |
Der Mathematiker Richard Kaye von der Universität Birmingham ist übrigens schon wieder beim Forschen, und ... spielt Minesweeper. Denn auch hier liegt ein Problem aus der gleichen Klasse verborgen - und die Million winkt.
|
|
|
|
|
|
Was macht der Nichtmathematiker? |
|
| |
Bis zur "Lösung" des Problems bleibt dem Normalbürger nur wohl nur eines übrig: Im Zweifelsfall in Urlaub fahren und die lästigen Verwandtenbesuche ganz streichen.
Niki Popper, Modern Times
|
|
|
01.01.2010 |
