Problem des Handlungsreisenden?

High · 09.02.2001

Hi!

Ich habe in der c´t einen Bericht über biologische Computer gelesen. In diesem Bericht wird von einem "Problem des Handlungsreisenden" gesprochen. Kann mir jemand erklären, was das für einen Hintergrund hat und worum es bei diesem Problem geht? In dem Artikel wurde nämlich beschrieben, daß ein biologischer Computer der erste Computer war, der dieses Problem mit einer Rechenzeit von einer Woche lösen konnte.

FatherFrost · 09.02.2001

man hat eine art karte(netz) mit städten(knoten) und strassen(kanten), die die städte verbinden.

gesucht wird der kürzeste weg, der durch alle diese städte führt

High · 09.02.2001

Das Problem an sich ist ja recht einfach.
Bei Routenplanern hat man doch auch das selbe Problem. Aber dafür brauche ich ja auch keinen biologischen Computer.
Warum ist die Lösung dieses Problems dann so schwer? Man bräuchte doch nur alle Möglichkeiten durchzuspielen?

FatherFrost · 09.02.2001

bei routenplannung suchst du den kürzesten weg zwischen 2 punkten. wenn du die richtung weiss ist es sehr leicht den pfad zu finden, etwa log(n)

beim traveling salesman problem:
wenn du n punkte hast und jeder von denen mit allen anderen verbunden ist, dann hast du 2^n mögliche pfade

[ 09 Februar 2001: Nachricht editiert von: FatherFrost ]

High · 09.02.2001

Das war mir schon klar, aber dafür muß doch n definiert gewesen sein, um einen Vergleich zwischen der Rechenleistung der Computer zu haben.
Oder will man versuchen eine generelle Lösung für alle n zu finden?

COGE · 09.02.2001

Natürlich könnte man alle Möglichkeiten durchspielen.
Bei sagen wir 5 Punkten vielleicht noch möglich, aber mach mal was bei - sagen wir - 100 Punkten.

Es gibt ein math. Gebiet namens Operation Research. Da beschäftigt man sich mit solchen Problemen und den Algorithmen, sie zu lösen.

...COGE...

Turok · 10.02.2001

das mag schon Stimemn was Father Frost meinte mit dem Pfad finden wenn man die Richtung weis von 2 punken oder soirgendwie,aber wenn man sich diese ganzen Routenplaner auf cdroms durschaut und sich ein und dieselbe Route berechnen läst ist das Ergebnis von der Enfernung geshen immer abweichend je nach Programm,also ist es für unsere Hightech industrie samt Super Computern auch nicht einfach nicht richtigen Pfad zu finden!

Turok · 10.02.2001

verflucht warum ist meine ct noch nicht da

am Montag kommt sie

nic_power · 10.02.2001

Hallo,

Das Traveling salesman ist eines der klassischen Computer-Probleme, mit dem Informatikstudenten immer wieder gerne gequaelt werden

. Ziel ist es, die kuerzeste Route zu finden, bei der N Staedte durch eine Rundreise verbunden werden, ohne dass eine Stadt mehr als einmal besucht wird. Das Traveling Salesman Problem gehoert zu den NP-vollstaendigen Problemen, und fuer groessere N nicht loesbar (zumindest nicht in akzeptabler Zeit). Das verschiedene Routenplaner unterschiedliche Ergebnisse berechnet, liegt daran, dass unterschiedliches Kartenmaterial verwendet wird und die Algorithmen zur Berechnung nicht identisch sind.

Nic

High · 10.02.2001

Also ist davon auszugehen, daß der Bio-Computer einen Algoithmus gefunden hat um das Problem vollständig zu lösen?

@Turok:
Der Artikel in der c´t war in der letzten Ausgabe und nicht in der neuen. Nur für den Fall, das Du deswegen auf die c´t wartest.

FatherFrost · 10.02.2001

es gibt schon einen algorithmus.... eben alle möglichkeiten durchprobieren. es gibt auch schnellere verfahren, wie zb die nachbarschaftslösung, aber sie bringen nicht das optimale ergebnis

Quisquam · 10.02.2001

Möchte nur mal darauf hinweisen, daß für dieses Rätsel noch keine Lösung gepostet wurde: http://www.power.msing.de/cgi-bin/ultimatebb.cgi?ubb=get_topic&f=26&t=000528

High · 10.02.2001

@Quisquam:
Dann würde ich mal sagen, Du besorgst Dir nen Bio-PC und fütterst den dann mit den Daten. Länger als eine Woche wird er nicht beschäftigt sein.

Problem des Handlungsreisenden?

High

FatherFrost

High

FatherFrost

High

COGE

Turok

Turok

nic_power

High

FatherFrost

Quisquam

High

Problem des Handlungsreisenden?

ANGEBOTE & SPONSOREN

Neueste Beiträge

Statistik des Forums