Das Problem des "Handlungsreisenden" |
| 25.07.2005, 20:59 | digga | Auf diesen Beitrag antworten » | ||||||
| Das Problem des "Handlungsreisenden" Beim sog. Problem des Handlungsreisenden geht es um die Frage, welche Route durch eine vorgegebene Anzahl an Städten die kürzeste ist, die möglich ist. Dabei soll die Route so beschaffen sein, dass jede Stadt einmal besucht wird und anschließend wieder die Ausgangstadt erreicht wird. Wie könnte ein Lösungsansatz für einen Algorithmus aussehen, welcher immer die beste Lösung liefert? Bislang wurde in der Praxis der Schwerpunkt hauptsächlich auf Verfahren gelegt, welche eine Näherungslösung liefern. Allerdings erscheint mir dies aus mathematischer Sicht unbefriedigend zu sein. Intuitiv kann ich bestimmte Lösungen von vornherein ausschließen, da es beispielsweise abwegig wäre, wenn ich eine Weltreise plante, erst von Berlin nach Washington, dann zurück nach Paris, dann von Paris nach New York, von New York nach Madrid usw. zu reisen. Eine weitere Frage, die sich mir stellt: Angeblich ist es geschafft worden, für ca. 10.000 oder sogar noch mehr Städte die optimale Lösung zu errechnen. Da man aber im Gleichzug behauptet, dass kein Verfahren bekannt sei, außer alle möglichen Wege durchzuprobieren, so ist mir schleierhaft, wie diejenigen, die diese Lösung für die 10.000 Städte errechnet haben, auch beweisen wollen, dass es die beste ist. Sie können es m. E. gar nicht bewiesen haben, weil die Anzahl der möglichen Routen bei n = 10.000, 9999! beträgt, also eine gigantisch große Zahl. Kein aktueller und wohl zukünftigen Rechner ist in der Lage, diese vielen Wege miteinander zu vergleichen. Irgendwelche Vorschläge? |
||||||||
| 25.07.2005, 21:44 | AD | Auf diesen Beitrag antworten » | ||||||
In Fragen NP-vollständiger Probleme bist du vermutlich im Informatikerboard besser aufgehoben. |
||||||||
| 25.07.2005, 21:56 | digga | Auf diesen Beitrag antworten » | ||||||
| RE: Das Problem des "Handlungsreisenden" Mitnichten. Es geht mir um mathematische Beweisführung, nicht um "praxisorientierte" Näherungsversuche. |
||||||||
| 25.07.2005, 22:09 | sqrt(2) | Auf diesen Beitrag antworten » | ||||||
Nun, wie Arthur schon gesagt hat, ist das Travelling Salesman Problem NP-vollständig. Damit kannst du sämtliche einfacheren Lösungen dem Kommitee, das die Fields-Medaille verleiht, zusenden. |
||||||||
| 25.07.2005, 22:13 | AD | Auf diesen Beitrag antworten » | ||||||
Nun ja, zumindest muss man nicht alle n! Wege durchprobieren: Wenn man bereits einen Weg der Länge L für n Städte kennt, und eine Teilpermutation von sagen wir m Städten (mit m<n) bereits einen längeren Weg für diese m Städte benötigt, dann müssen wir den "Rest" dieser Permutation gar nicht mehr untersuchen! Das ist das, was mir erst mal spontan zu der Frage einfallen würde, ob man wirklich alle n! Permutationen durchprobieren muss. Ich denke mal, dass man damit schon eine ganze Menge Aufwand reduzieren kann! Aber "wenig" (also polynomial) wird es deswegen trotzdem nicht. |
||||||||
| 25.07.2005, 22:30 | sqrt(2) | Auf diesen Beitrag antworten » | ||||||
Das ist ja der Punkt. Wenn es jemand schafft, das TSP in Polynomialzeit berechenbar zu machen, kann man jedes NP-vollständige Problem in Polynomialzeit lösen, es folgt . Die Fields-Medaille wäre der entsprechenden Person dann wohl sicher. |
||||||||
| Anzeige | ||||||||
|
|
||||||||
| 26.07.2005, 13:50 | quarague | Auf diesen Beitrag antworten » | ||||||
man muss hier genau zwischen zwei Problemen unterscheiden: 1. was ist der optimale Weg 2. gibt es einen Weg der kürzer als eine vorgegebene Schranke ist das 1. ist da klassische TSP, das zweite ist mit deutlich geringerem Aufwand lösbar, wenn ich mich recht erinnere für bestimmte Schranken sogar mit polynomialen Aufwand. ausserdem ist es recht einfach bestimmte Konfigurationen von Städten zu konstruieren, für die das Problem nahezu trivial lösbar ist. zB könnte man alle Städte halbwegs gleichmäßig auf einem Kreis anordnen, dafür kann man das Problem dann mit beliebig vielen Städten schnell lösen. |
||||||||
| 26.07.2005, 13:59 | AD | Auf diesen Beitrag antworten » | ||||||
Das "halbwegs gleichmäßig" kannst du hier getrost streichen, das ist nicht nötig. |
||||||||
| 26.07.2005, 14:39 | PrototypeX29A | Auf diesen Beitrag antworten » | ||||||
RE: Das Problem des "Handlungsreisenden"
Was denkst du was wir Informatiker machen? Loesungen einfach auf gut Glueck annehmen? Das TSP ist ein klassisches Problem der theoretischen Informatik, die natuerlich sehr stark mit Mathe zusammenhaengt. Man kann sich darueber streiten (ja das macht man auch) ob man computergefuehrte Beweise anerkennt oder nicht. Nun ich bin deutlich dafuer, schliesslich ist es ja egal ob ein Computer die 100.000 Seiten ausdruckt oder ein Arbeitsloser Informatiker das in seiner Freizeit tut. Ein prominenter computergefuehrter Beweis ist auch das 4-Farben-Kartenproblem. Man hat mit einem Computer bewiesen, dass man jede Karte mit nur 4 Farben einfaerben kann. Manche Mathematiker weigern sich afaik bis heute noch den Beweis anzuerkennen ... Proto |
||||||||
| 26.07.2005, 15:04 | digga | Auf diesen Beitrag antworten » | ||||||
RE: Das Problem des "Handlungsreisenden"
Warum so kompliziert? Pack die Punkte doch gleich allesamt auf eine Gerade. Aber daran sieht man schon, dass es ein polynominales Verfahren - davon bin ich überzeugt - geben muss.
Ich gebe dir Recht. Wenn ich P=NP beweise, habe ich gute Chancen für die Fields-Medaille, allerdings glaube ich, dass derjenige, der vor kurzem -1 = 1 bewiesen hat, doch noch die besseren Aussichten auf die Fields-Medaille besitzt...
Nein, aber wenn ich eine Erkenntnis gewinnen möchte, die mir die Informatik mit ihren Methoden nicht liefern kann, ist sie für mich unbrauchbar. Das wirst du doch verstehen, oder? Frage an ALLE: Wie beweist man, dass ein Verfahren polynominal bzw. nicht-polynominal ist? |
||||||||
| 26.07.2005, 15:10 | PrototypeX29A | Auf diesen Beitrag antworten » | ||||||
RE: Das Problem des "Handlungsreisenden"
Und ich moechte nochmal behaupten, dass du nicht weisst was die theoretische Informatik macht.
1. Auch das ist wieder ein typisches Gebiet fuer Informatiker Das ein Verfahren in polynomieller Zeit (den worst-case) beweist man am besten an Modellen wie einer Turingmaschine. Das Gegenteil auch. 2. Bist du dirch sicher, dass du nicht "nicht-deterministisch polynomiell" meinst? |
||||||||
| 26.07.2005, 15:11 | Mathespezialschüler | Auf diesen Beitrag antworten » | ||||||
^^ Kannst du mir den Beweis bitte mal zeigen! 
Gruß MSS |
||||||||
| 26.07.2005, 15:13 | PrototypeX29A | Auf diesen Beitrag antworten » | ||||||
Am besten ohne die Wurzel-Operation falsch auf komplexe Zahlen anzuwenden? 
|
||||||||
| 26.07.2005, 15:26 | digga | Auf diesen Beitrag antworten » | ||||||
Das ist dein gutes Recht, das zu behaupten. Ich behaupte, dass du nicht weisst, was ein mathematischer Beweis ist. Einen solchen suche ich, und sonst nichts. Die theoretische Informatik ist mir dabei ähnlich wie die theoretische Physik relativ egal.
Nein, dafür sind andere hier im Forum besser geeignet. |
||||||||
| 26.07.2005, 15:28 | Mathespezialschüler | Auf diesen Beitrag antworten » | ||||||
Was meinst du denn damit? 
Wenn du sagst, jmd. hätte das bewiesen, dann musst du doch wissen, wer und wo vll der Beweis steht. Hier im Forum wird es sicher niemand beweisen können, weil es nicht bewiesen werden kann. *gg*Deswegen wollte ich den Beweis ja auch sehen, da ich denke, dass er wohl eher fehlerhaft sein wird.
Gruß MSS |
||||||||
| 26.07.2005, 15:29 | AD | Auf diesen Beitrag antworten » | ||||||
Sachte, sachte, Leute. @digga Du redest immer von "mathematischem Beweis". Aber was genau du beweisen willst (bzw. bewiesen haben willst) hast du uns noch nicht verraten. 
|
||||||||
| 26.07.2005, 15:41 | PrototypeX29A | Auf diesen Beitrag antworten » | ||||||
Troll woanders, so eine Kindergartenpolemik gehoert ins Heise-Forum, aber nicht hierher. Sorry an alle anderen, aber diesmal bin ich wirklich veraergert. Proto |
||||||||
| 26.07.2005, 16:10 | sqrt(2) | Auf diesen Beitrag antworten » | ||||||
Er ist beleidigt. Schau mal auf meine Signatur. |
||||||||
| 26.07.2005, 17:13 | digga | Auf diesen Beitrag antworten » | ||||||
Zum Beispiel wie ich beweisen kann, dass das von dir vorgeschlagene Verfahren, welches immerhin das Ausprobieren sämtlicher Möglichkeiten verbessert, dennoch das Problem des Handlungsreisenden nicht in polynominaler Zeit lösen kann. Oder allgemein: Wie kann ich beweisen, wie lange ein Algorithmus benötigt, im Hinblick auf p bzw. np?
In Ordnung, dann geh du doch bitte ins Heise-Forum oder Informatik-Forum und poste hier nicht mehr, zumindest nicht in meinen Threads, dann wäre die Sache erledigt. Danke! |
||||||||
| 26.07.2005, 17:20 | AD | Auf diesen Beitrag antworten » | ||||||
Nimm z.B. n Städte, bei denen sich die jeweilige Entfernung voneinander nur minimal voneinander unterscheidet, also sowas wie mit für alle i,j. Das ist der "worst case" für die von mir beschriebene Vorgehensweise - weil ich dann die Permutationen nicht so "abschneiden" kann, wie ich es oben beschrieben habe. Das ist natürlich kein Beweis, dass es kein besseres Verfahren gibt - aber es zeigt, dass mein Vorschlag von oben das nicht leisten kann. |
||||||||
| 26.07.2005, 17:42 | digga | Auf diesen Beitrag antworten » | ||||||
Muss ich dann also immer vom worst case ausgehen? Eine andere Frage: Wie finde ich den worst case und wie beweise ich, dass es auch wirklich der worst case ist? Denn wenn mein Verfahren selbst beim worst case noch die entsprechende Zeit dauernd würde (in p), dann hätte ich ja schon einen Beweis, den einen schlechteren Fall als den worst case kann es ja nicht geben. Ist so in etwa der Ansatz gemeint? |
||||||||
| 26.07.2005, 17:46 | AD | Auf diesen Beitrag antworten » | ||||||
Wenn's dafürfeste Regeln geben würde, wäre das Beweisen eine einfache Sache. Du musst dein Verfahren nach solchen Schwachpunkten "abklopfen".
Indem ich nachweise, dass es in allen Fällen höchstens so lange wie im worst case dauert! Oder was hast du gedacht? |
||||||||
| 28.05.2010, 10:20 | W_Ciossek | Auf diesen Beitrag antworten » | ||||||
| RE: Das Problem des "Handlungsreisenden" Ich glaube nicht, daß das Problem ein P = NP Problem ist. Wenn beispielsweise eine Miilliarde Orte aufgesucht werden sollen, die auf einer Geraden liegen, braucht man überhaupt keine Rechnerei und kann dieses Problem exakt lösen, indem man nur einen Weg wählt, nämlich diese Gerade. Man kann also schon von vornherein anhand der Geometrie unötige Wege auslassen. Ich habe einen Einbeulalgorithmus entwickelt, wo eine Haut um die Orte gespannt wird. Sie berührt die außenstehenden Orte. Dann wird eine zweite Haut gespannt, um die Orte herum, die nicht von der ersten Haut erfaßt wurden. Jetzt braucht man nur von der ersten Haut zur zweiten den kürzesten Zugang wählen. Man verfährt hierbei solange, bis alle Orte erfaßt sind. Leider kann ich noch nicht beweisen, ob dieser Weg der optimale ist, jedoch werden hier die Prinzipien der Variationsrechnung genutzt. |
||||||||
| 28.05.2010, 11:12 | wisili | Auf diesen Beitrag antworten » | ||||||
| RE: Das Problem des "Handlungsreisenden" Hier möchte ich die «Haut» sehen ... [attach]14864[/attach] |
||||||||
| 28.05.2010, 11:22 | papahuhn | Auf diesen Beitrag antworten » | ||||||
RE: Das Problem des "Handlungsreisenden"
Hi, du scheinst für die angegebene Probleminstanz eine bessere Lösung zu kennen? Wie sähe die aus? |
||||||||
| 28.05.2010, 11:30 | Mystic | Auf diesen Beitrag antworten » | ||||||
RE: Das Problem des "Handlungsreisenden"
Hm, ich sehe da nur die Knoten und nicht die Kanten und ihre Bewertungen... Oder meinst du den vollständigen Graphen mit den euklidischen Distanzen als Bewertung? Wie auch immer, ich möchte jetzt nicht in der Haut von W-Ciossek stecken... 
@W-Ciossek Es ist ein bißchen sehr naiv, aus der Tatsache, dass spezielle Einzelbeispiele von TSP leicht sind oder dass man für eine Klasse solcher Probleme einen guten Algorithmus kennt, gleich schließen zu wollen, dass dies dann für alle TSP-Probleme gilt... |
||||||||
| 28.05.2010, 11:36 | wisili | Auf diesen Beitrag antworten » | ||||||
| RE: Das Problem des "Handlungsreisenden" Ich weise nur auf die Unsinnigkeit hin, irgendein «Prinzip» zu nennen, ohne auch nur einen Hauch von Argument dafür zu haben, dass es besser sein könnte als andere, von Optimalität (und nur um das geht es hier) ganz zu schweigen. @mystic Ja, ich dachte an den vollständigen Graphen und implizit an die euklidische Distanz, obwohl ich zu wenig belesen bin, um sicher ausschliessen zu können, dass für diesen (hohen) Spezialfall eine polynomiale Lösung gefunden wurde. |
||||||||
| 28.05.2010, 11:44 | papahuhn | Auf diesen Beitrag antworten » | ||||||
RE: Das Problem des "Handlungsreisenden"
Deine Instanz ist aber auch kein Argument dafür, dass der Haut-Algorithmus offensichtlich suboptimal ist; deine Instanz ist schwierig, weil es sehr viele Knoten gibt, nicht weil es ein offensichtlich besseres Verfahren gibt. |
||||||||
| 28.05.2010, 12:56 | Mystic | Auf diesen Beitrag antworten » | ||||||
RE: Das Problem des "Handlungsreisenden"
Naja, was die Sache für euklidische TSP so speziell macht, ist in erster Linie das Erfülltsein der Dreiecksungleichung, die Vollständigkeit könnte man z.B. leicht durch die Hinzunahme der fehlenden Kanten mit genügend hohen Bewertungen erzwingen, ohne die Lösung zu verändern, wenn der ursprüngliche Graph schon hamiltonsch war... Meines Wissens gibt es aber auch da nur nur PTAS (Polynomial Time Approximation Schemes), welche in Polynomialzeitzeit "beliebig gute" Näherungen liefern... |
||||||||
|
|