Diskussion:Problem des Handlungsreisenden/Archiv

Diese Seite ist ein Archiv abgeschlossener Diskussionen. Ihr Inhalt sollte daher nicht mehr verändert werden. Benutze bitte die aktuelle Diskussionsseite, auch um eine archivierte Diskussion weiterzuführen.

Um einen Abschnitt dieser Seite zu verlinken, klicke im Inhaltsverzeichnis auf den Abschnitt und kopiere dann Seitenname und Abschnittsüberschrift aus der Adresszeile deines Browsers, beispielsweise

[[Diskussion:Problem des Handlungsreisenden/Archiv#Thema 1]]

oder als Weblink zur Verlinkung außerhalb der Wikipedia

https://de.wikipedia.org/wiki/Diskussion:Problem_des_Handlungsreisenden/Archiv#Thema_1

Ameisenalgorithmen (erledigt)

Eine weitere Heuristik basiert auf so genannten Ameisenalgorithmen, bei denen das natürliche Verhalten von Ameisen bei der Wegsuche modelliert wird, um Optimierungsprobleme in der Informatik zu lösen. Ameisenalgorithmen zählen zu Multiagentensystemen, bei denen nach dem Modell von Ameisen gestaltete Agenten mit Hilfe von lokalen Heuristiken und Kommunikation über Duftstoffe (Pheromone) die kostengünstigste Lösung als Weg auf dem Problemgraphen suchen. Ameisenalgorithmen zählen zu den lokalen Suchverfahren, die durch iterative Optimierung einer zufällig gefundenen Lösung gekennzeichnet sind. Neben dieser iterativen Optimierung sind Ameisenalgorithmen durch Metaheuristiken gekennzeichnet, die in diesem Fall aus einem natürlichen Verhalten von Ameisen gewonnen werden. Die zugehörigen Optimierungsverfahren sind auch als Ant Colony Optimization (ACO) bekannt.

Steht jetzt drin. -- Sdo 20:48, 1. Okt 2006 (CEST)

Dieser Abschnitt kann archiviert werden. BSI 14:28, 3. Mär. 2011 (CET)

Deutsche Großstädte (erledigt)

Datei:TSP Deutschland 3.PNG Das Bild mit den deutschen Großstädten illustriert ein wirklich schönes Beispiel. Darf man sich dabei auch wünschen, dass die deutschen Städtenamen auch deutsch statt französisch dastehen?--JFKCom 22:59, 15. Okt 2005 (CEST)

Am besten sprichst du den Ersteller Kapitän Nemo einfach mal auf seiner Diskussionsseite darauf an. --Avatar 07:59, 17. Okt 2005 (CEST)

Mir ist das völlig wurscht in welcher Sprache die Städte und Länder bezeichnet sind. Es kommt doch ohnehin für das TSP nur auf die deutschen Städte an, die ja sogar mit deutschen Namen bezeichnet sind. 84.169.243.82 12:41, 17. Jun 2006 (CEST)

Mal eine weitere Frage. Wie kommst Du auf die in der Bildunterschrift angegebenen 43589145600 Möglichkeiten. Ich beschäftige mich zur Zeit im Rahmen einer Seminararbeit mit der Tourenplanungsproblematik. Dabei habe ich mir in dem Buch von Hans-Jörg Zingler (Computergestützte Transport- und Tourenplanung) die Formel zur Ermittelung der Kombinationen angeschaut und komme damit auf ein Ergebnis von 40564819207303300000000000000000 bei 15 Städten.LS8-18 22:20, 2. Nov. 2006 (CET)

0,5*14! --Scherben 22:30, 2. Nov. 2006 (CET)

Könntest Du mir das bitte (ruhig auch per Mail oder hier) erläutern, wieso das 0,5*14! ist? LS8-18 22:53, 2. Nov. 2006 (CET)

Hallo LS8-18, in Kurzfassung steht das im Artikel. Hier die Langfassung für n Städte: die erste Stadt kann beliebig festgelegt werden. Dann musst du eine von n-1 restlichen Städten auswählen. Im folgenden Schritt bleiben dir noch n-2 zur Auswahl, usw. Insgesamt musst du n-1 Städte auswählen (der letzte Schritt zurück zur Ausgangsstadt ist ja festgelegt). Das ergibt $(n-1)!=(n-1)\cdot (n-2)\cdot \ldots \cdot 1$ Möglichkeiten. Und weil bei einem symmetrischen TSP die Richtung egal ist, zählt es als dieselbe Tour, wenn du andersherum läufst. Also halbiert sich die Anzahl der verschiedenen Touren nochmal zu ${\frac {1}{2}}(n-1)!$. Bei 15 Städten sind das ${\frac {1}{2}}\cdot 14!=43589145600$. Gruß, -- Sdo 23:51, 2. Nov. 2006 (CET)

Dieser Abschnitt kann archiviert werden. BSI 14:28, 3. Mär. 2011 (CET)

Nur 14 Städte?

Wenn ich mir den Weg anschaue, finde ich nur 14 Städte darauf: 1. Berlin, 2. Dresdren, 3. Leipzig, 4. Nürnberg, 5. München, 6. Stuttgart, 7. Frankfurt, 8. Köln, 9. Düsseldorf, 10. Duisburg, 11. Essen, 12. Hannover, 13. Bremen, 14. Hamburg. Hab ich mich verguckt? --RokerHRO 13:25, 7. Nov. 2006 (CET)

Dortmund fehlt. Ist aber in der Route enthalten, zwischen Essen und Hannover. --Scherben 13:39, 7. Nov. 2006 (CET)

Ah, okay. Kann ich ja nicht wissen. Danke. --RokerHRO 14:19, 7. Nov. 2006 (CET)

Wo oder wie ist es belegt, das der dargestellte Weg wirklich den Optimalsten darstellt? --LS8-18 17:10, 7. Nov. 2006 (CET)

Das glaube ich Benutzer:Kapitän Nemo, dem Ersteller des Bildes, gerade einfach mal. Ich weiß zwar nicht, bezüglich welcher Kantengewichte er die Tour berechnet hat (z. B. Luftlinie oder Straßenentfernungen), aber die Tour sieht glaubhaft kurz aus. Frag im Zweifelsfall nochmal bei Kapitän Nemo nach. Nebenbei: optimal lässt sich nicht steigern. :-) -- Sdo 00:58, 8. Nov. 2006 (CET)

Mir fällt grad auf, dass wir auch hinschreiben könnten, dass es auch die Tour optimale Tour für die sechzehn größten Städte Deutschland ist. Da Bochum auf Platz 16 liegt und sowieso schon Teil der Route ist. ;) --Scherben 08:56, 8. Nov. 2006 (CET)

Das hängt jetzt von den Gewichten ab. Wenn es Luftlinienentfernungen sind, können wir Bochum aufnehmen. Andernfalls weiß ich nicht, ob die Aussage noch stimmt. -- Sdo 11:08, 8. Nov. 2006 (CET)

Ich komm' ja von da: Die A 40 als Verbindung der Essener und Dortmunder Innenstadt führt jedenfalls mitten durch Bochum. War aber sowieso nur Spaß. btw: Ich habe wohl vor ein paar Monaten auf die Diskussion zum Bild schon den Hinweis geschrieben, dass Dortmund fehlt. Wenn der Ersteller noch aktiv ist, hat er das Bild jedenfalls nicht auf seiner Beobachtung. --Scherben 11:15, 8. Nov. 2006 (CET)

Dieses Bild soll in erster Linie einen trockenen Artikel etwas anschaulicher gestalten. Die Reiseroute ist rein heuristisch berechnet, bis zum Beweis des Gegenteils gehe ich davon aus, dass sie die kürzeste Route ist. Dortmund fehlt leider auf der CIA-Karte und ich weiß leider auch nicht, wo man im eng besiedelten Ruhrgebiet noch eine zusätzliche Stadt einzeichnen könnte. --Kapitän Nemo 14:57, 8. Nov. 2006 (CET)

Kommentare zur überarbeiteten Version (erledigt)

Hallo Fishroot,

wie ich sehe, bist Du fleißig dabei, den Artikel zu überarbeiten – da hat sich ja schon einiges getan! Ich habe gerade auch bei der Charakterisierung (die ich gleich mal umbenannt habe) und den Lösungsmethoden ein paar Dinge geändert. Ein paar weitere Punkte, die mir beim Durchlesen aufgefallen sind, auch als Erinnerung für mich selbst:

1. Die neuere Geschichte fehlt noch: Applegate, Bixby, Chvatal, Cook, Padberg, Grötschel,....
2. Was haben das Königsberger Brückenproblem und das Icosian Game mit dem TSP zu tun, außer dass sie sich graphentheoretisch formulieren lassen?
3. Die allgemeine Definition finde ich komplett unverständlich und nutzlos. Wer vorher nicht wußte, was das Problem ist, weiß es hinterher auch nicht, und diese Definition bringt meines Erachtens keinen Vorteil. Ich würde schlichtweg die graphentheoretische Formulierung als Definition und als Basis für die späteren Erklärungen nehmen. Sie ist anschaulich und trotzdem exakt, und praktisch arbeitet jeder mit graphentheoretischen Begriffen und Argumenten, auch wenn zur Lösung vielleicht gerade ILPs verwendet werden. Ich kenne jedenfalls keinen, der die angegebene allgemeine Definition für irgendetwas nutzt, und wir sollten das Thema für Laien nicht unverständlicher machen als nötig. Wenn Du damit einverstanden bist, ändere ich das demnächst mal.
4. Die ILP-Formulierung würde ich auch zu den exakten Lösungsverfahren schieben. Nee, doofe Idee. Ist schon ganz gut so. -- Sdo 00:52, 19. Apr 2006 (CEST) Subtour-Eliminationsbedingungen ist zwar genauer, aber ich kenne die Dinger auf deutsch als Kurzzyklusungleichungen. Wahrscheinlich sollten wir beide Namen erwähnen.

So so, wohl zuviel in Grötschels Charakterisierung kombinatorischer Optimierungsprobleme herumgeblättert ;-). Ich halte den Begriff eigentlich für veraltet. (nicht signierter Beitrag von Tgel2 (Diskussion | Beiträge) )

Jein, eher Erinnerung aus seinen Vorlesungen... Ich habe keinen Überblick, wie oft welcher Begriff genutzt wird. Eine kurze Google-Abstimmung spricht für Subtour. Von mir aus können wir die Kurzzyklen im Artikel auch durch Subtouren ersetzen. -- Sdo 00:46, 28. Aug 2006 (CEST)

1. Um die Argumentation zu vereinfachen, sollte wir die übliche Formulierung auf einem vollständigen Graphen verwenden und kurz begründen, warum das sinnvoll ist. Sonst müssen wir ständig aufpassen wegen evtl. nicht existenter Kanten.
2. Anwendungen des klassischen Problems fehlen noch, am besten nach den Spezialfällen oder im Zusammenhang damit.
3. Evtl. können auch kurz Anwendungen für die verschiedenen Metriken erwähnt werden (z. B. Leiterplatten bohren für Maximums- und Manhattan-Metrik). Im Moment stehen sie etwas unmotiviert in der Gegend herum.
4. Die Einleitung sollte am Ende nochmal erweitert werden, um einen Überblick über den restlichen Artikel zu geben.

So, das war's erstmal. Gruß, -- Sdo 00:07, 28. Mär 2006 (CEST)

Die Punkte 1-7 habe ich gerade erledigt, die Einleitung muss noch gemacht werden. Ein paar Bilder könnten auch noch in den Artikel. -- Sdo 01:19, 15. Apr 2006 (CEST)

Einleitung und Bilder sind auch erledigt. Wenn keine wesentlichen Einwände kommen, stelle ich den Artikel demnächst in den Review, um dann mit dem überarbeiteten Artikel einen neuen Lesenswert-Anlauf zu starten. -- Sdo 00:52, 19. Apr 2006 (CEST)

Dieser Abschnitt kann archiviert werden. BSI 14:28, 3. Mär. 2011 (CET)

Archivierte Trollbeiträge (erledigt)

Da die Beiträge des mittlerweile gesperrten Benutzers Vfpp und seiner ebenfalls gesperrten Sockenpuppen Fsswsb4 und Fsswsb5 von begrenztem Nährwert sind, habe ich sie der Übersichtlichkeit halber archiviert. Die vollständige Version ist hier zu finden. -- Sdo 22:09, 20. Jun 2006 (CEST)

Dieser Abschnitt kann archiviert werden. BSI 14:28, 3. Mär. 2011 (CET)

Traveling vs. Travelling (erledigt)

Credner hat eben aufgrund des Beginns des englischen Artikels Traveling in Travelling geändert, allerdings nicht konsequent. Da die Frage nach der korrekten Schreibweise vermutlich noch öfter auftauchen wird, stelle ich sie hier mal zur Diskussion, bevor ich irgendwelche weiteren Änderungen in der Richtung durchführe. Meine Hoffnung ist, dass wir hier auf ein Ergebnis kommen, auf das wir später einfach verweisen können. Einige Fakten:

• Der englische Artikel handhabt die Sache uneinheitlich. Das Lemma beinhaltet Travelling, im Text taucht aber öfter die Variante Traveling auf. Laut der Fussnote scheint Traveling amerikanisches Englisch zu sein. Der Artikel wurde im Januar 2006 von Traveling nach Travelling verschoben, siehe Versionshistorie. Der Verschiebekommentar war „moved Traveling salesman problem to Travelling salesman problem: more neutral title; travelling is an acceptable spelling in BrE and AmE (and all other national varieties)“. Eine Diskussion dazu habe ich nicht gefunden.

• In der Literatur wird die Frage ebenfalls unterschiedlich gesehen, siehe die entsprechende Diskussion und die Literaturübersicht auf der TSP homepage (die selbst Traveling benutzt).

Welche Variante wir wählen, ist mir letztendlich egal, aber ich hätte gerne innerhalb des Artikels eine einheitliche Schreibweise (ggf. mit erklärender Fußnote wie im englischen Artikel). Gibt es in der deutschen WP irgendwelche Richtlinien zum Thema American/British English? In der englischen WP gilt: it depends... Gruß, -- Sdo 16:26, 27. Jun 2006 (CEST)

oups, sorry, ich dachte, ich hätte alles geändert. war nicht meine Absicht, da groß eine Diskussion anzustoßen, "Traveling" kam mir nur (da mir BE deutlich vertrauter ist als AE) merkwürdig vor, und in en-wp heißt das Lemma eben "Travelling Salesman Problem". Wie wir es nun letztlich schreiben, ist mir egal, aber ich geb Sdo völlig Recht, einheitlich sollte es sein (wie gesagt, da hab ich wohl einiges übersehen. keine Absicht.). -- Da der erste, der dem Problem den englischen Namen gegeben hat, von der Princeton University war, könnte man wohl für "Traveling" argumentieren... --Credner 16:55, 27. Jun 2006 (CEST)

Mir ist's völlig egal, im Zweifel würde ich wohl für die britische Variante votieren. Mit derselben Begründung, mit der das Lemma in der en:wp verschoben wurde. Grüße --Scherben 17:22, 27. Jun 2006 (CEST)

Ihr seid euch ja genauso einig wie der Rest der Welt...;-) Ich habe jetzt Credners Änderungen vervollständigt und überall (bis auf die Literaturliste) Traveling durch die britische Variante Travelling ersetzt. Damit scheinen ja zumindest wir alle glücklich zu sein. -- Sdo 01:08, 12. Aug 2006 (CEST)

Wenn hier dieser schöne Konsens erreicht wurde (der ja plausibel erscheint) -- wieso ist es dann im Artikel durchgängig anders gemacht (also en:us statt en:gb)? -- 84.191.150.110 21:40, 25. Mär. 2007 (CEST)

Weil es irgendwer (evtl. sogar ich selbst? Weiß ich nicht mehr.) im Laufe der Diskussion auf en:us umgestellt hat und es keinen genug gestört hat, das wieder zu ändern. Auf diese Art ist die Schreibweise zumindest konsistent mit der TSP-Homepage. So richtig Konsens war es ja auch nicht, sondern eher ein „ich würde es so und so schreiben, aber eigentlich ist es mir egal“ von allen Seiten. -- Sdo 00:48, 8. Apr. 2007 (CEST)

Dieser Abschnitt kann archiviert werden. BSI 14:28, 3. Mär. 2011 (CET)

Halbsperrung aufheben? (erledigt)

Ist der Vierfarbensatz- und TSP-Troll Vfpp eigentlich noch in einer seiner Reinkarnationen aktiv oder können wir die Halbsperrung des Artikels wieder aufheben? -- Sdo 01:12, 12. Aug 2006 (CEST)

Ich hab's mal aufgehoben, hab die Seite ja auf meiner Beobachtungsliste. --Scherben 10:59, 12. Aug 2006 (CEST)

Dieser Abschnitt kann archiviert werden. BSI 14:28, 3. Mär. 2011 (CET)

Einleitung / NP-Vollständigkeit (erledigt)

Der folgende Satz

Vereinfacht bedeutet dies, dass die Laufzeit jedes Algorithmus,
der für dieses Problem stets optimale Lösungen liefert,
exponentiell von der Anzahl der Städte abhängt

ist IMHO falsch: Erstens ist der Algortihmus auf NDTMs definitiv in Polynomialzeit berechenbar. Auch auf DTMs gibt es eine Polynomialzeitlösung wenn NP=P. Das Gegenteil ist ja noch nicht bewiesen. Die Darstellung in muss zwar vereinfacht, aber darf nicht falsch sein. Da NP/P für den Außenstehenden nicht trivial ist, sollte man ggf. wirklich einen neuen Abschnitt noch vor der Geschichte entwerfen, in dem das Problem detailliert erklärt wird. NP/P erst irgendwo im Laufe des Artikels zu erwähnen fände ich zu spät. Ggf. könnte man in diesem Abschnitt auch einen nichtdeterministen Algorithmus vorstellen. -- FelixReimann 22:02, 16. Aug 2006 (CEST)

Inhaltlich hast du Recht, ich kämpfe nur mit der Quadratur des Kreises. Wenn man das explizit machen will, kann man gleich auf den Artikel zum P/NP-Problem verweisen. Oder eben auf den zur NP-Vollständigkeit. Ich versuche mich nochmal daran. --Scherben 22:12, 16. Aug 2006 (CEST)

Wär mir schon ne bessere Formulierung eingefallen, hääte ich sie ergänzt :) -- FelixReimann 22:14, 16. Aug 2006 (CEST)

Ich habe hier mal was vorbereitet. Bitte um Kommentare. Und ab ins Bett. ;) --Scherben 22:36, 16. Aug 2006 (CEST)

Wenn ihr euch in der Komplexitätstheorie auskennt, könntet ihr ein gutes Werk tun und dem Artikel NP-Vollständigkeit eine Oma-verständliche Einleitung verpassen. In dem Artikel steht nicht mal drin, worin die Bedeutung des Begriffs liegt. Ich habe mich mit dem Thema bisher nicht mehr beschäftigt als unbedingt nötig, und könnte daher auch mit obiger Formulierung in der Einleitung leben – schließlich steht da „vereinfacht“...;-) An dieser Stelle würde ich das Thema auf zwei bis drei Sätze beschränken. Also etwa so wie jetzt, plus ein Satz zur Nichtapproximierbarkeit, ohne ins Detail zu gehen. Zu dem Zeitpunkt muss ein Leser nur verstehen, dass das Problem schwer ist. Für eine ausführlichere Erklärung schlage ich vor, zwischen Modellierung und Lösungsverfahren einen Absatz einzubauen, in dem die Tatsache der NP-Vollständigkeit und der Nichtapproximierbarkeit erklärt werden, zusammen mit den Konsequenzen für die Lösungsverfahren. Dort passt dieses Thema m.E. inhaltlich am besten hin.

Da es hier um das TSP geht und nicht um den Begriff der NP-Vollständigkeit, würde ich das Thema aber insgesamt nicht zu sehr auswalzen – da stimme ich Scherbens Beitrag im Review zu. In diesem Sinne ist mir Scherbens Entwurf ein wenig zu lang und zu technisch. Wer von der Problematik noch nichts gehört hat, ist mit dem zweiten Absatz wahrscheinlich überfordert. Ein Durchschnittsleser ohne Vorkenntnisse soll ja im wesentlichen verstehen (oder uns glauben), dass die Laufzeit exponentiell mit der Zahl der Städte wächst und dass das Problem außerdem schwer approximierbar ist, d. h., dass es keine beliebig gute Gütegarantie für polynomiale Heuristiken gibt. Letzteres sehe ich sogar eher schon als Teil für fortgeschrittene Leser. Die Approximierbarkeits-Aussage mit dem $\epsilon$ muss man als Laie auch erstmal verdauen. Gruß und gute Nacht, -- Sdo 01:43, 17. Aug 2006 (CEST)

Also ich stimme Sdo zu: es geht hier ums TSP, da sollte man nicht allzu ausführlich werden, was die NP-Vollständigkeit angeht. Vielleicht reicht es schon, das "Daher lässt sich bereits bei wenigen Städten nur sehr schwer die bestmögliche Rundreise finden." umzuändern in sowas wie "Dies bedeutet, dass sich mit solchen Algorithmen bereits bei wenigen Städten nur sehr schwer die bestmögliche Rundreise finden lässt. Daher wurden verschiedene Verfahren entwickelt, um trotzdem Ergebnisse zu erhalten, die in den meisten Fällen zufriedenstellend sind." Was meint ihr?

Und ja, NP-Vollständigkeit könnte eine Überarbeitung gebrauchen, bei der der Fokus mehr auf dem Begriff selbst und weniger auf dem Satz von Cook liegt. Ich hab aber keine Zeit, das selbst zu machen. Gruß, -- Schweerelos 12:12, 17. Aug 2006 (CEST)

Ich habe mir mal einen kleinen Trick erlaubt und hinter "Vereinfacht" einen Link auf die richtige Stelle in P/NP-Problem hinterlegt. So könnte man weiterhin diese "intuitive" Erklärung behalten, bräuchte hier kein großes komplexitätstheoretisches Brimborium und hätte somit die oben angesprochene Quadratur des Kreises geschafft. ;) --Scherben 17:27, 17. Aug 2006 (CEST)

Wunderbar. -- Sdo 00:04, 18. Aug 2006 (CEST)

Dieser Abschnitt kann archiviert werden. BSI 14:28, 3. Mär. 2011 (CET)

Denglisch (erledigt)

Also mich stört irgendwie das Wort Optimalitätsgap. Für mich heißt das entweder Optimalitätslücke oder englisch optimality gap oder einfach Lücke oder gap, Aber ist Optimalitätsgap ist mir noch nicht untergekommen und ich halte es auch für schlechtes Deutsch. Ansonsten kann mich ja hier einer eines besseren belehren und mir sagen wo es noch vorkommt.

Erledigt. -- Sdo 01:03, 28. Aug 2006 (CEST)

Dieser Abschnitt kann archiviert werden. BSI 14:28, 3. Mär. 2011 (CET)

TSP mit 526*10^6 Sternen (erledigt)

...Lösungen für ein TSP auf über 526 Millionen Sternen gefunden... Dieser Satz ist mir etwas unklar. 2004 hat man gerade so(offenbar wegen begrenzter Rechenkapazität) eine optimale Lösung für ein TSP mit 25.000 Städten berechnen können und ein wenig später konnte man gleich eins mit einer halben Milliarde lösen? --Stimpson 13:12, 1. Sep 2006 (CEST)

Du darfst den Relativsatz nicht vergessen. Es wurde eben nicht die optimale Lösung gefunden, sondern nur eine mit einer beweisbar sehr geringen Abweichung von der optimalen. --Scherben 13:19, 1. Sep 2006 (CEST)

Achso. Kann man es für meine Laienohren verständlich erklären, woher man die Abweichung von der optimalen Lösung berechnen kann, wenn diese gar nicht bekannt ist? --Stimpson 15:09, 1. Sep 2006 (CEST)

Letzter Absatz von "Exakte Lösungsverfahren". ;) --Scherben 15:12, 1. Sep 2006 (CEST)

Sauber, Oma-Test bestanden :) --Stimpson 15:16, 1. Sep 2006 (CEST)

Dieser Abschnitt kann archiviert werden. BSI 14:28, 3. Mär. 2011 (CET)

Review vom 11. August bis 8. September 2006 (erledigt)

Vorweg: Ich bin kein Hauptautor und habe bis auf kleinere Veränderungen überhaupt nichts an diesem Artikel editiert. Aber: Ich habe ihn gelesen und halte ihn für eine hervorragende Darstellung des traveling salesman problem, die m. E. wenig Wünsche offen lässt. Die mathematischen Methoden sind (aus der Sicht eines Mathematikers, zugegeben) in der gebotenen Detailliertheit angegeben, Geschichte, Modell und Bilder sind gut aufeinander abgestimmt. Meine Motivation war es zunächst, den Artikel zu verbessern und die Kritikpunkte aus der gescheiterten Lesenwert-Kandidatur auszumerzen. Nur: Die sind schon längst draußen, ich habe also kein Futter. Für mich ist der Artikel bereits jetzt lesenswert, nach dem Review sollte man m. E. direkt eine Exzellenz-Kandidatur angehen. --Scherben 16:01, 11. Aug 2006 (CEST) Zusatzfrage von mir als einem der Hauptautoren: ist der Artikel laienverständlich? Wenn nein, was ist unverständlich? -- Sdo 22:13, 11. Aug 2006 (CEST)

• Tja, die Frage nach der Laienverstädnlichkeit ist ein knifflige Sache. Denn ein Mathe-Laie wird auch die beste Darstellung eines mathematischen Sachverhaltes nicht kapieren. Ich denke, dass bei einem solchen Fachartikel der allgemeine Sachverhalt für Laien erklärt werden muss, zusätzlich noch die Geschichte... welche Persönlichkeiten haben sich damit beschäftigt, usw. Dies macht der Artikel. Vielleicht könnte man die Anwendungsgebiete etwas ausführlicher schildern? Zu den theoretischen Lösungsansätzen kann ich nix sagen, zähle mich eher zu den Laien, bzw. nicht zu den Mathe-Profis. Also ich wüsst nicht was man da noch besser machen kann. Die Grafiken und Bilder sind gut eingebaut. Ich habe keine Idee und halte den Artikel für absolut lesenswert (vielleicht sogar mehr, dazu fehlen mir aber Vergleiche im MatheBereich). Grüße! -- TP12 14:36, 13. Aug 2006 (CEST)

Hallo TP12, was genau würdest du dir bei den Anwendungen noch für Informationen wünschen? Ich weiß im Moment nicht so genau, was ich sinnvollerweise noch dazu schreiben kann. -- Sdo 22:18, 13. Aug 2006 (CEST)

• Die Erwähnung sowohl der englischen als auch der amerikanischen Schreibweise in der Einleitung finde ich unnötig. Zudem stört mich, dass das Problem im Artikel durchgängig mit STP abgekürzt wird. Und haben die ganzen Varianten wirklich keine deutschen Namen?
  Aber amsonsten sieht der Artikel für mich gut aus, wenngleich ich ihn zugegebermaßen nicht vollständig gelesen habe. --Ce 21:15, 13. Aug 2006 (CEST)

Das mit dem Traveling/Travelling sollte klarmachen, dass es unterschiedliche Schreibweisen gibt, und dass sich die Autoren darüber Gedanken gemacht haben, damit die Schreibweisen im Artikel nicht mehrfach hin- und hergändert werden. Deutsche Namen für diese Varianten sind mir zumindest nicht bekannt – die Fachliteratur ist fast vollständig auf Englisch verfasst. Und soweit ich weiß, ist selbst in der wenigen deutschsprachigen Fachliteratur TSP die übliche Abkürzung. -- Sdo 22:18, 13. Aug 2006 (CEST)

Wenn die Doppelnennung nur für Bearbeiter ist, dann bietet sich ein nur im Bearbeiten-Fenster sichtbarer HTML-Kommentar (<!-- (Kommentar) -->) an, wie z.B. hier:

Was die Abkürzung angeht, stört mich weniger, welche Abkürzung verwendet wird, sondern dass durchgängig abgekürzt wird. Wikipedia hat keine Platzprobleme, da kann man den Begriff schon ausschreiben (und in einigen Fällen wäre "das Problem" vermutlich eindeutig genug).

Ein Kompromiss wäre vielleicht die Verwendung des title-Attributs, z.B. so: TSP (mit dem Mauszeiger drauffahren, um den Effekt zu sehen). Nachdem die Abkürzung auf dem englischen Begriff beruht, sollte da der Tooltip m.E. ebenfalls englisch sein. --Ce 13:22, 15. Aug 2006 (CEST)

Die Variante mit dem Tooltip finde ich nur mäßig schön. Aber ich habe an einigen Stellen die Abkürzung TSP durch alternative Formulierungen ersetzt. Du hast schon recht, das macht das Lesen etwas angenehmer. Travelling ist inzwischen konsequent auf Traveling geändert worden, mit Kommentar für Bearbeiter im Quelltext. Das kann von mir aus so bleiben. -- Sdo 15:35, 15. Aug 2006 (CEST)

• Für Bild:Cutting plane algorithm.jpg sollte ein png/svg-Ersatz gefunden werden. --Phrood 21:27, 13. Aug 2006 (CEST)

Ja, das mit dem jpg war mein erster, uninformierter Versuch. Ich habe später mal versucht, stattdessen ein svg-Bild daraus zu machen, aber das wurde von der Media-Wiki-Software nicht korrekt umgesetzt. Daraufhin hatte ich die Sache erstmal vertagt, bis der Bug behoben ist. Aber ein png-Bild kann ich aus den Quellen noch erzeugen. -- Sdo 22:18, 13. Aug 2006 (CEST)

Erledigt. -- Sdo 01:42, 14. Aug 2006 (CEST)

• NP was ist das?--Sanandros 11:46, 16. Aug 2006 (CEST)

Ich bin verwirrt. Der Begriff taucht im Artikel nur über NP-Schwere, NP-Vollständigkeit und das P/NP-Problem auf und wird jeweils durch den Wikilink erklärt. Das sind ja letztlich auch nur Randnotizen. --Scherben 11:52, 16. Aug 2006 (CEST)

Nein, dass das TSP NP-vollständig ist, ist ganz essentiell, da dies der Grund ist, warum sich Horden von Mathematikern damit beschäftigen. Vielleicht sollte noch vor dem Abschnitt Geschichte ein extra Absatz, der das Problem etwas detaillierter für den mathematischen Laien beschreibt (v.a.: WO ist das Problem?->Exponentielles Wachstum der Möglichkeiten sowie NP-completeness). Außerdem beschreibt der Abschnitt Nichtapproximierbarkeit des TSP IMHO eine wichtige Eigenschaft des TSPs und ist im Kapitel Lösungsverfahren fehlplatziert. @Sanandros: siehe NP (Komplexitätsklasse) -- FelixReimann 12:21, 16. Aug 2006 (CEST)

Außerdem fehlen zu den Verfahren die Komplexitäten. Sind zwar nicht bei allen anzugeben (z.B. SimulatedAnnealing), aber bei den anderen sollte es dranstehen (z.B. NearestNeighbor: O(n²)) -- FelixReimann 12:39, 16. Aug 2006 (CEST)

Zur Vollständigkeit: Mit "Randnotiz" meinte ich, dass das im bisherigen Artikel nur Randnotizen sind, nicht dass das für die mathematische Untersuchung des TSP ohne größere Bedeutung wäre. Nur zur Erklärung. ;) Inhaltlich: Ich bin ein Freund von Artikeln, die sehr fokussiert das eigene Thema behandeln und nicht Dinge behandeln, die in anderen Artikeln bereits beschrieben worden sind. Heißt konkret: Einen eigener Abschnitt, der das Thema Vollständigkeit noch einmal aufgreift, würde ich hier fehl am Platze sehen. Bisher werden dieser Fakt und die daraus resultierenden Probleme im Artikel mehrfach aufgegriffen, das reicht m. E. Mal auf sdos Meinung warten. :) [Sehe ich genauso. -- Sdo 02:52, 18. Aug 2006 (CEST)]

Die Komplexitäten könnte man aber tatsächlich ergänzen, guter Vorschlag. --Scherben 14:06, 16. Aug 2006 (CEST)

Im Kasten vom Rearview-Artikel steht dieses Wort NP und daher habe ich gefragt--Sanandros 12:21, 16. Aug 2006 (CEST)

Schoener Artikel, ich habe aber noch einige Kritikpunkte. Zum Einen fasst die Einleitung meiner Meinung nach nicht das wichtigste zusammen. Eine Ein- bis Zweisatz-Erklaerung dessen, was NP-vollstaendigkeit ist und bedeutet, gehoert zum Artikel einfach dazu, sonst ist er fuer Laien nicht verstaendlich. Ebenso sollte direkt in der Einleitung angegeben werden, dass es leicht moeglich ist, gute Naeherungen zu berechnen. Schliesslich ist der Abschnitt zu den Loesungsverfahren zuwenig konkret. Er behandelt teilweise einfach Verfahren der ganzzahligen Optimierung, sehr deutlich im Abschnitt "Metaheuristische Verfahren", ohne aber konkret auf das TSP einzugehen. Ich denke das sollte man entweder kuerzen und auf Ganzzahlige lineare Optimierung verweisen oder aber konkret auf Resultate bzgl. dieser Verfahren eingehen. In etwa: "Alle Verfahren der ganzzahligen linearen Optimierung lassen sich auf das TSP anwenden, etwa <insert lange Liste>." Nur, wenn sich dann konkret etwas sagen laesst, erwaehnt man mehr, etwa bei der Minimum-Spanning-Tree-Heuristik. Ein Abschnitt wie "Metaheuristische Verfahren" ist in diesem Artikel aber IMHO entbehrlich. --P. Birken 14:35, 16. Aug 2006 (CEST)

Da ist etwas dran. Die Idee hinter dem Abschnitt war unter anderem, das Stichwort Ameisenalgorithmus an passender Stelle unterzubringen, weil der beim TSP besonders häufig als Allheilmittel angepriesen wird. Aber das lässt sich sicherlich auch in den Abschnitt über ganzzahlige Optimierung einbauen. Ich werde mir das mal genauer angucken. Schon mal danke für die Hinweise, -- Sdo 21:09, 16. Aug 2006 (CEST)

Die Metaheuristiken sind jetzt ein Unterabschnitt des Abschnitts Heuristiken, und die Beschreibung ist etwas mehr auf das konkrete Problem zugeschnitten. Rausnehmen will ich den Teil eigentlich nicht, einfach damit das Thema an passender Stelle vorkommt und inhaltlich eingeordnet ist. -- Sdo 22:56, 20. Aug 2006 (CEST)

• Wir haben hier einen ganz hervorragenden Überblicksartikel über das Problem nebst verschiedener Lösungsmöglichkeiten. Ich bin allerdings in der Thematik Halboma. Ich habe mir den Artikel mal durchgelesen. Es ist für mich eine Situation, wie wenn ich Zweitgutachter bei einer Diplomarbeit wäre, von deren Thematik ich nur am Rande was verstehe (kommt manchmal vor). Für meine folgenden Anmerkungen habe ich schätzungsweise ca. 2 Stunden verbraten, d.h. es ist nicht irgendwelches grantiges Gemeckere, sondern das, was mich (mit Gutachterhut) irritiert hat.

1. NP-Vollständigkeit kurz erklären, denn der weiterführende Link ist nicht auf die Schnelle hilfreich. Ev. auch alle folgenden NP-Varietäten.
2. Bei der Graphendarstellung sollte man G=(V,E) weglassen, da es eigentlich keinen Mehrwert bringt, außer die Einsicht, dass der Autor die erforderlichen Vorlesungen des Informatik-Grundstudiums besucht hat. Oder es muss angegeben werden, was V und E bedeuten.
3. Eine erklärender kurzer Halbsatz zu gerichteter Graph
4. Mehrere in der Praxis häufig auftretende Distanzfunktionen sind metrisch: klingt schief. Sollte der Autor gemeint haben: "Für praktische Probleme verwendet man häufig Distanz-Metriken, etwa:"? Die Distanzen wurden ja nicht als metrisch eingeführt, nur das TSP. Unter metrisch verstehe ich intuitiv metrisch skaliert.
5. Distanzen, die aus Entfernungstabellen in Straßenkarten entnommen werden, sind meist nicht metrisch, weil dort in der Regel die km-Länge eines zeitlich kürzesten Weges angegeben ist, der nicht unbedingt ein kürzester Weg bzgl. der Reisestrecke ist. Siehe oben. Statt meist nicht lieber "nicht zwingend"
6. Falls es im praktischen Planungsproblem zulässig ist, Orte mehrfach zu besuchen, kann man das Problem auf ein metrisches TSP im sogenannten Distanzgraphen reduzieren. Dort entspricht die Kantenlänge zwischen zwei Knoten $i$ und $j$ der Länge eines kürzesten $i-j-$Weges bzgl. der ursprünglichen Kantenlängen $c_{ij}$. Die so definierten neuen Kantenlängen erfüllen immer die Dreiecksungleichung. Wird nicht klar. Grafik wäre hilfreich, wie man da überhaupt ein bisschen großzügiger sein könnte.
7. Formel (2) könnte bestimmt mit etwas gutem Willen und weniger Eitelkeit verständlicher umformuliert werden. Ich habe jedenfalls keine Lust, das Zeug Symbol für Symbol mir zu erarbeiten.
8. Statt enumerieren: durchrechnen. Vor allem ist im Link Enumieren aufzählen.
9. deutlich größere Instanzen Was ist das denn bitte?
10. [1] Die Grafik ist völlig unklar, vor allem durch was sich die verschiedenenfarbigen Polygonzüge unterscheiden.
11. TSP Homepage: Ein Weblink im Artikel, bei einer Exzellenz-Kandidatur. Tztz...
12. Daraus ergibt sich eine algorithmische Komplexität von O(n²). Vermutlich gilt es als unfein, zu sagen, die Zahl der möglichen Lösungen steigt quadratisch oder so.
13. Einfüge-Heuristiken Klingt nach Cluster-Analyse.
14. minimal aufspannenden Baum Kurz erläutern
15. Minimum-Spanning-Tree-Heuristik. Hier wären zwei Grafiken illustrativ. Ausgangslösung und erstmalige Verdopplung der Kanten
16. k-Opt-Heuristiken Nach welchen Kriterien? Zufällig?
17. Verfahren in einem Framework zusammengefasst. Leider wird in dem Artikel Framework überhaupt nicht klar, was das sein soll. Könnte man da nicht einen kleinen Satz verlieren? Heißt in der Praxis, dass der Logistiker in seiner Arbeit so was macht oder dass man in der Forschung so vorgeht? Das war Forscherperspektive – hab's umformuliert. -- Sdo 02:52, 18. Aug 2006 (CEST)
18. Im Abschnitt Nichtapproximierbarkeit des TSP wird gezeigt, dass das Problem des Handlungsreisenden nicht in polynomialer Laufzeit beliebig gut approximierbar ist. Hier wird ein Beweis geführt, der einer gewissen Einarbeitung bedarf und außerdem aus dem Rahmen des gesamten Artikels fällt, weil ja sonst auch nichts bewiesen wird.
19. Vehicle Routing Problem heißt bei uns Transportproblem. Ich vermute auch stark, dass es für die anderen Anwendungsfälle deutsche Entsprechungen gibt

So weit meine 5 Euros. --Philipendula 15:44, 16. Aug 2006 (CEST)

Hallo Philipendula, schon mal vielen Dank für den detaillierten Review! Beim ersten Durchlesen klingen mir die meisten Vorschläge sinnvoll. Ich gucke mir das mal in Ruhe an und gehe dann später nochmal genauer auf einzelne Punkte ein. -- Sdo 21:09, 16. Aug 2006 (CEST)

Scherben hat wohl schon ein paar Punkte davon umgesetzt. --Philipendula 22:43, 16. Aug 2006 (CEST)

Hallo Philipendula, die meisten deiner Kritikpunkte sind inzwischen von verschiedenen Leuten eingearbeitet worden. Um die Bilder kümmern wir uns noch, und der Teil zur Komplexität und Approximierbarkeit ist auch noch in Arbeit. Das Transportproblem ist für mich aber ein klar definiertes Problem, das wenig bis gar nichts mit dem Problem des Handlungsreisenden zu tun hat, und die Einfüge-Heuristiken kenne ich wirklich unter diesem Namen. -- Sdo 02:52, 18. Aug 2006 (CEST)

Nachtrag: $V$ und $E$ wurden bei der Modellierung als ILP verwendet; ich habe sie jetzt auch dort definiert. -- Sdo 22:56, 20. Aug 2006 (CEST)

Mir gefällt der Artikel schon recht gut. Selbst geändert habe ich die Erwähnung der Distanzen in der Hoffnung eine Überleitung hinzubekommen. Als nicht Mathematiker ist mir die Wortwahl präzise genug, Philipendulas Kritik würde ich aber in 80% stützen. Zusätzlich würde ich die Beispiele aus der Real World (Handlungsreisender durch deutsche Städte) etwas deutlicher als solche behandelt wissen, da das Problem als solches abstrakt ist. Jetzt schon "lesenswert" von mir. Mehr ist wohl drin. --chrislb 问题 22:11, 16. Aug 2006 (CEST)

Hallo Chrislb, was genau meinst du mit den Beispielen? Tourenplanung ist zwar eine Anwendung des TSP, aber die meisten Anwendungen liegen wahrscheinlich in anderen Bereichen, wie auch im Artikel beschrieben. Zugegebenermaßen nicht sehr ausführlich, aber die Anwendungen sind auch nicht das Hauptthema des Artikels. Wo genau fehlt dir da etwas? -- Sdo 02:52, 18. Aug 2006 (CEST)

• Das "Problem des Handlungsreisenden" ist immernoch ein Problem der Unternehmensforschung (OR) und nur die Modellierungen und deren Lösungswege (i.w.S.) sind Probleme der angewandten Mathematik und theoretischen Informatik. (Manche behaupten sogar das eigentliche Problem besteht darin als Hanlungsreisender zwei Tage vor Weihnachten im verscheiten Minnesota eingeschlossen zu sein, während zuhause die Frau mit dem Postboten...)

Jein. Man kann das Problem auch einfach unabhängig von seinen Anwendungen als kombinatorisches Optimierungsproblem auffassen, das als Selbstzweck studiert wird. -- Sdo 18:57, 20. Aug 2006 (CEST)

Richtig: man kann es als math. Problem betrachten, um zu brauchbaren Lösungen zu kommen und dieser Mittel bedient sich auch das OR - das ist aber eine ganz andere Definition als im Artikel! Reine Mathematik könnte man ja in Kombinatorische Optimierung auslagern. --Thomas M. 19:29, 20. Aug 2006 (CEST)

Könnte man sich (von der jetzigen Einleitung ausgehend) auf "angewandte Mathematik" statt "Mathematik" einigen? --Scherben 19:43, 20. Aug 2006 (CEST)

"Het handelsreizigersprobleem (TSP, Traveling Salesman Problem) is één van de bekende problemen in de computerwetenschap en de Operations Research." - das ist die holländische Variante, die ich persönlich favourisiere. "Angewandte Mathematik" ist gut, OR noch im ersten Absatz zu erwähnen sollte eigentlich selbstverständlich sein. -- Thomas M. 20:00, 20. Aug 2006 (CEST)

Computerwissenschaft und angewandte Mathematik sind mir zu unpräzise. Es sollte schon diskrete Mathematik oder kombinatorische Optimierung sein. Ich habe jetzt den Kombinatorik-Link umgebogen und OR eingefügt. Besser so? Ich frage mich auch, was das TSP mit theoretischer Informatik zu tun hat, abgesehen davon, dass es eines der Standardbeispiele der Komplexitätstheorie ist. -- Sdo 20:34, 20. Aug 2006 (CEST)

• Anfang der neunziger Jahre gab es einige Lösungsansätze mit neuronalen Netzen und ähnlichen statistischen Verfahren (s. z.B. Self-Organizing Maps). Darüber würde ich gern kurz was lesen.

Habe ich bei den Metaheuristiken eingebaut. Gab es da irgendetwas wirklich Brauchbares? -- Sdo 18:57, 20. Aug 2006 (CEST)

Klar, bei der Lith. in KFM wird man sicher fündig. Habe jetzt aber keine Bücher greifbar. Die Ergänzungen sind fast schon ok. -- Thomas M. 19:29, 20. Aug 2006 (CEST)

• Der Übergang zur Modellierung ist nicht ganz laiengerecht. Ich denke die meisten haben bis zum Ende immernoch die anschauliche Deutschlandkarte im Kopf und beziehen das geschriebene darauf.

Ich bin gerade etwas ratlos, wie sich die Erklärung bei der Modellierung noch verbessern lässt. Eigentlich werden der Zusammenhang zwischen Knoten und Städten und die Bedeutung der Gewichte da ausführlich erklärt. Hast du konkrete Vorschläge? -- Sdo 18:57, 20. Aug 2006 (CEST)

Knifflig. Ich versuche mal einen Satz zu basteln... --Thomas M. 19:29, 20. Aug 2006 (CEST)

• Toll fände ich eine Übersichts-Tabelle für die Verfahren und Heuristiken, mit Aufwände, Vor- und Nachteile, usw.

Lesenswert isser schon, aber für exzellent fehlt mir gegen Ende noch ein wenig der Überblick. -- Thomas M. 14:44, 20. Aug 2006 (CEST)

Ok, über so eine Tabelle können wir nochmal nachdenken, das ist gar keine schlechte Idee. Fehlt dir der Überblick über den letzten Teil (Problemvarianten) oder über den gesamten Artikel? Hast du Vorschläge, wie sich das am besten ändern lässt? -- Sdo 18:57, 20. Aug 2006 (CEST)

Die Problemvar. sind halt zusammenhangslos aneinandergehängt. Ich erkenne weder eine problemspezifische, noch eine inhaltlich-anwendungsorientierte oder eine mathematisch-lösungsorientierte Struktur. -- Thomas M. 19:29, 20. Aug 2006 (CEST)

Das stimmt, aber die vorgestellten Problemerweiterungen haben auch nichts miteinander zu tun (außer dass sie alle vom TSP abstammen) und sind nahezu beliebig kombinierbar. Insofern habe ich da gerade Schwierigkeiten, eine Struktur reinzubringen. -- Sdo 20:34, 20. Aug 2006 (CEST)

Ich dachte an meine alten Lehrbücher, die die verschiedene Varianten eben durch unterschiedliche, formalisierte Randbedingungen und/oder Zielfunktionen ausgedrückt haben. Durch solche Gegenüberstellungen ließe sich dann leicht eine Ordnung und die Begrenztheit der möglichen Variationen und Kombinationen zeigen - das führt hier aber vielleicht zu weit.

Die Einleitung/Definition ist noch nicht optimal. Ich bin aber überfragt, ob das TSP geschichtlich zuerst in einem rein mathematischen oder wirtschaftlichen (OR) Zusammenhang definiert und bearbeitet wurde. Auf jeden Fall gibt es zwei "Ebenen" oder Bedeutungen. Zum einen als anwendungsorientierte Problemstellungen und dann als Problemklasse in der Mathematik. Vermutlich sollte man das in der Def. und Einleitung trennen, aber da bin ich kein Experte. -- Thomas M. 21:13, 20. Aug 2006 (CEST)

Ich denke mal, erst als Anwendung und dann als mathematisches Problem, wie es jetzt unter Geschichte steht. In der Einleitung ist das ja im wesentlichen getrennt; es gibt sowohl zur Anwendung als auch zum mathematischen Problem je einen Absatz. Nur im ersten Satz kommt beides vor, was IMHO auch in Ordnung ist. -- Sdo 22:56, 20. Aug 2006 (CEST)

---

Vielen Dank an alle Reviewer! Ich bin die nächsten drei Wochen erstmal weg und baue danach noch die letzten Anregungen ein. Anschließend kann der Artikel von mir aus kandidieren (wobei ich erstmal KLA vorschlagen würde, um noch Rückmeldungen zur Oma-Tauglichkeit zu bekommen). -- Sdo 11:58, 8. Sep 2006 (CEST)

Ich habe den Artikel aus Zeitmangel leider (erstmal) nur überfliegen können. Mir persönlich kommt dabei die Einleitung recht lang vor. Insgesamt soll die Artikeleinleitung doch die Sache kurz und knapp (soweit das beim jeweiligen Thema möglich ist) auf den Punkt bringen. - Oder sehe ich das Falsch? Mir würde der erste Absatz als Einleitung reichen. Der 2. und 3. Absatz wären vielleicht als Untereinleitung für die Teilüberschrift „Mathematische Beschreibung“ geeignet. Der 4. Absatz scheint mir als Untereinleitung für den Gliederungspunkt „Lösungsverfahren“ geeignet.

Insgesamt scheint sich die Arbeit, die hier investiert wurde aber sehr gelohnt zu haben. Viel Glück bei der laufenden Nominierung - ich werde mich bis auf weiteres enthalten, da ich den Artikel für eine Stimmabgabe erst noch in Ruhe, gründlich lesen muss.--Beck's 23:42, 1. Okt 2006 (CEST)

Dieser Abschnitt kann archiviert werden. BSI 14:28, 3. Mär. 2011 (CET)

Fehlendes, Fehler und Ungenauigkeiten (erledigt)

Als ganz ganz unrsprünglicher Autor möchte ich dann jetzt auch mal meinen Senf abgegen, da ich ausnahmsweise mal etwas Zeit dazu habe und die Autoren glauben jetzt relativ weit zu sein.

1. Zunächst fehlt (mir) die Unterscheidung in die drei Varianten Entscheidungsproblem, Optimierungsproblem und Suchproblem.
2. Nicht verwunderlich ist, dass mangels dieser Untersccheidung die falsche Behauptung aufgestellt wird, das TSP (so wie im Artikel definiert) wäre NP-vollständig. Richtig wäre, dass das zugehörige Entscheidungsproblem NP-vollständig ist (nur für solche ist der Begriff der NP-Vollständigkeit überhaupt definiert). Für Optimierungs- und Suchprobleme könnte man noch den Begriff NP-Äquivalenz verwenden, aber der ist derzeit grottig/falsch in WP erklärt.
3. Wo kommen diese ominösen Instanzen mit 32.000 Städten her? Ich kann leicht eine Instanz mit 2^32.000 Städten und eine optimale Lösung dazu angeben. Diese Aussagen sind in dieser vereinfachten Form also total nutzlos. Ich vermute mal, dass da real existierene Städte und ihre Distanzen genommen wurden. Diese Aussage gehört dann unbedingt in den Artikel rein. Noch besser wäre, wenn noch erklärt wird, nach welchen Kriterien die Städte ausgewählt wurden.

--Koethnig 11:38, 2. Okt 2006 (CEST)

Kurz von mir:

Ad 1. Hier geht es eigentlich nur um das Optimierungsproblem. Die Unterscheidung will ich hier eigentlich nicht erklären. Wäre NP-schwer passender als NP-vollständig? Der Artikel ist leider komplett unverständlich, aber soweit ich mich erinnere, ist ein Optimierungsproblem im wesentlichen dann NP-schwer, wenn das zugehörige Entscheidungsproblem NP-vollständig ist, oder? Ich bin da allerdings kein Experte.

Ad 3. Das sind alles TSPlib-Instanzen mit realem Hintergrund, siehe weiter unten im Artikel. Dass diese Instanzen nicht trivial sind, kann sich der Leser eigentlich denken, wenn sie hier extra erwähnt werden, oder?

-- Sdo 12:51, 2. Okt 2006 (CEST)

zu 1.) Streng genommen handelt der Artikel nur das Suchproblem ab (häufig wird aber nicht zwischen Such- und Optimierungproblem unterschieden, wobei dann mit Optimierungsproblem eigentlich dass Suchproblem gemeint ist)! Auf die Unterscheidung würde ich schon aufmerksam machen wollen, schon weil erst daraus die Beweisbarkeit der NP-vollständigkeit rührt. Das kann man dann gerne auch in einem Extra-Abschnitt machen der auch den Laien nicht überfordern dürfte. Und man kann dann auch erläutern, warum das Such- und Optimierungsproblem ähnlich schwer sind (polynomieller Alg für Entscheidungsproblem -> pol. Alg. für Opt. -> pol. Alg. für Suchproblem und (trivial) -> pol. Alg. für Entscheidungsproblem). NP-vollständigkeit ist deshalb nur auf Entscheidungsprobleme beschränkt, weil es schon die NP-schwere ist! Insofern reicht es nicht und wäre auch unsinn, dies dahingehend abzuschwächen. Also entweder man sagt, dass zugehörige Entscheidungsproblem ist NP-Vollständig, oder man sagt das Optimierungsproblem ist NP-Äquivalent oder (das fände ich am besten) man lässt diese Begriffe zumindest in der Einleitung ganz weg und widmet dem ganzen einen eigenen Abschnitt, wo man dann auch gerne das Entscheidungsproblem einführen kann.

Führen die Unterscheidung dieser Begriffe und ein eigener Abschnitt hier nicht zu weit? Diese ganzen Erklärungen haben nichts speziell mit dem TSP zu tun, und es handelt sich hier nicht um einen Artikel zur Komplexitätstheorie. Der Zusammenhang zwischen diesen Begriffen und die von dir genannten Implikationen sollten genau einmal beim Suchproblem bzw. beim Optimierungsproblem abgehandelt werden (die wiederum gemeinsam in einem Artikel mit dem Entscheidungsproblem erklärt werden sollten) und nicht in jedem Artikel, der ein spezielles Problem beschreibt. Der Artikel sollte sich meiner Meinung nach auf die Erklärung des TSP beschränken und nicht zu sehr in die Komplexitätstheorie abschweifen – er ist lang genug, und den meisten Lesern dieses Artikels ist diese Unterscheidung wahrscheinlich herzlich egal. Selbst die meisten Optimierer ignorieren diese Feinheiten. Es geht mir hier darum, dass die Leser des Artikels die Kernaussage begreifen, nämlich dass das Problem schwer ist und eine exakte Lösung „im wesentlichen“ die Enumeration aller möglichen Lösungen erfordert. Wer Details wissen will, kann sich die Erklärung der NP-Vollständigkeit und ähnliche Artikel durchlesen.

Nichtdestoweniger habe ich den Teil mit der NP-Vollständigkeit in der Einleitung und im Geschichtsteil mal präzisiert. Sagt der Begriff der NP-Äquivalenz eigentlich irgendetwas wesentlich anderes aus als der Begriff der NP-Vollständigkeit, außer dass der eine für Such- und der andere für Entscheidungsprobleme definiert ist? Laut NP-Vollständigkeit#NP-Äquivalenz sieht es so aus, als wären die beiden Begriffe aus praktischer Sicht äquivalent. ;-) -- Sdo 02:26, 3. Okt 2006 (CEST)

Im Prinzip ist dieses Verfahren mit dem zugehörigen Entscheidungsproblem recht kanonisch und insofern hast du recht. Ich bau es mal in Entscheidungsprobleme ein und bieg den Link noch auf die dann passende Zwischenüberschrift um. --Koethnig 11:37, 3. Okt 2006 (CEST)

Wunderbar. -- Sdo 17:21, 3. Okt 2006 (CEST)

zu 3.) Sehe ich nicht so, weil ohne den Hinweis der Wert der Aussage völlig unklar bleibt. Reale Inst. neigen z.B. dazu metrisch zu sein und weitere schöne Eigenschaften zu haben. Man kann dann also davon ausgehen, das entsprechende Algorithmen ähnliche Instanzen ähnlich effizient lösen, aber das kann bei komplett anderen Instanzen wieder anders aussehen. Mglw. wird dem Leser also zuviel Leistung der entsprechenden Alg. suggeriert. Nicht umsonst betrachtet die Komplexitätstheorie Probleme meist bzgl. ihrer Eingabelänge und nicht anhant von ein paar Beispielen ...

--Koethnig 13:41, 2. Okt 2006 (CEST)

Der praktische Hintergrund der Beispiele steht ja hier, zusammen mit dem Hinweis, dass die konkreten Eingabedaten eine wesentliche Rolle spielen. Im Geschichtsteil habe ich die Angaben nochmal etwas präzisiert. -- Sdo 02:26, 3. Okt 2006 (CEST)

Dieser Abschnitt kann archiviert werden. BSI 14:28, 3. Mär. 2011 (CET)

Belege für Karps Beweis (erledigt)

Gibts für die Behauptung, das Karp 1972 das Entscheidungsproblem als NP-vollständig charakterisieren konnte Belege? Die Reduktion von Hamiltonkreis auf TSP ist zwar recht einfach, aber zu den 21 klassichen gehört es scheinbar nicht... --Koethnig 11:52, 3. Okt 2006 (CEST)

Nachtrag: das angegebene Postscipt von David Applegate, Robert Bixby, Vašek Chvátal, William Cook schreibt es Karp zu, verweißt aber auch nur auf die Liste?! --Koethnig 11:58, 3. Okt 2006 (CEST)

Kann es so gewesen sein, dass Karp nur gezeigt hat, dass das Hamiltonkreisproblem NP-vollständig ist? Und dass schon vorher bekannt war, dass sich das Hamiltonkreisproblem auf Entscheidungsproblem zum TSP zurückführen lässt? --Scherben 15:50, 3. Okt 2006 (CEST)

Kann gut sein. Die Reduktion ist ja nicht schwierig. Ich gucke morgen mal im Garey und Johnson nach, ob dort Genaueres dazu steht. -- Sdo 17:17, 3. Okt 2006 (CEST)

Also, dort steht nur ein lapidarer Hinweis „Reduktion auf das Hamiltonkreisproblem“ ohne Referenz. Wahrscheinlich hat Karp die NP-Äquivalenz des TSP nicht direkt bewiesen, bekommt es aber meist zugesprochen, weil die Reduktion auf das Hamiltonkreisproblem so einfach ist. Ich habe die Formulierung entsprechend überarbeitet. -- 23:29, 4. Okt 2006 (CEST)

Dieser Abschnitt kann archiviert werden. BSI 14:28, 3. Mär. 2011 (CET)