Diskussion:Problem des Handlungsreisenden

Vorlage:Keine Auskunft

Ist der Artikel nicht komplett falsch benannt und müßte eigentlich den Namen des Handelsreisenden tragen? Es geht ja hier nicht um Handlung sondern um Handel (sales).

adi@TGI

Die Übersetzung von travelling salesman ist im deutschen Handlungsreisender (vgl. auch "Tod eines Handlungsreisenden" von Arthur Miller). --Avatar 00:35, 1. Jun 2005 (CEST)

Ich bin mir da nicht so sicher. Mir ist das Problem eigentlich ausschliesslich als Problem des Handelsreisenden bekannt. So ist es auch in entsprechender Fachliteratur benannt, die ich diesbezueglich kenne --193.205.206.25 12:00, 26. Jul 2005 (CEST)

Ich war ursprünglich auch verunsichert, aber "Handlungsreisender" ist wirklich die deutsche Bezeichnung für "travelling salesman" (schaut einfach in ein dickes englisch/deutsch-Wörterbuch).--JFKCom 23:31, 7. Okt 2005 (CEST)

Zustimmung. Stern 12:35, 29. Nov 2005 (CET)

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.

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)

 Pro Finde ich sehr anschaulich beschrieben. Stern 02:46, 10. Feb 2006 (CET)

 Pro Cottbus 07:29, 10. Feb 2006 (CET)

Erst contra, geändert in *neutral - Nach der Einleitung ergeht sich der Artikel nur noch in mathematischer Sprache und Formeln. Okay, wenn es wegen dem Thema nicht anders geht (bin kein Fachmann), nehme ich das contra zurück. Ich fände wenigstens eine anfängliche Abhandlung des Themas in "normaler Sprache" gut. Dann kann ja das mathematische folgen. Gruß Boris Fernbacher 09:17, 10. Feb 2006 (CET)

• Pro, gut beschrieben, allerdings würde ich mir noch etwas mehr über Heuristiken zur Lösung eines TSP und deren Qualität wünschen. @Boris: Das Kernproblem eines TSP ist schlicht "nur" das, was auch in der Einleitung steht. Der Rest, die Formulierung des Problems usw., ist Mathematik --Zakysant 09:45, 10. Feb 2006 (CET)

 Neutral: Da ist einiges fleißig zusammengetragen worden, aber ich hätte da noch einige offene Punkte:

• Mit der Einleitung bin ich nicht glücklich. Da der Handlungsreisende zu den klassischen NP-vollständigen Problemen gehört, sollte dies kurz erwähnt werden.

Steht im Artikel, nur an völlig unerwarteter Stelle (Siehe meine Kritik)! --Koethnig 14:04, 10. Feb 2006 (CET)

• Die Beschreibung des Problems als populär und alltäglich in der Einleitung gefällt mir ebenso nicht. Es ist einer der Klassiker, ja, aber was ist wirklich alltäglich? Dass das Problem praktische Relevanz hat, kann ggf. erwähnt werden und es könnte vielleicht im Dienste der allgemeinen Verständlichkeit (siehe oben) darauf eingegangen werden.

Ist schon alltäglich, allerdings ist der alltägliche Fall, einmal zur Arbeit und Zurück! :-) --Koethnig 14:04, 10. Feb 2006 (CET)

• Der Punkt In der Praxis gestattet man dabei häufig, Orte mehrmals zu besuchen in der Einleitung ist ziemlich überflüssig, da hier nur Entfernungen zählen (wir sind hier nicht beim Hamiltonkreisproblem), d.h. wenn der kürzeste Weg von A nach B über C führt, dann wird eben für die Distanz zwischen A und B die Summe der Distanzen zwischen A und C und zwischen C und B eingetragen.

Nein, dass klassische TSP verbietet das! In der Praxis kann man es dann erlauben, was äquivalent zum Verlangen einer metrischen Distanzfunktion ist (was das klassische aber nicht macht). :-) --Koethnig 14:04, 10. Feb 2006 (CET)

Der Punkt ist, dass diese Einschränkung nicht im mindestens stört. O.B.d.A... :-) --AFBorchert 09:04, 11. Feb 2006 (CET)

• Der Artikel geht wenig auf die Sicht der Informatiker ein. Insbesondere wird nicht das Branch-And-Bound-Verfahren erwähnt. Genauso fehlt die Betrachtung genetischer Algorithmen und Ameisen-basierter Verfahren.

Das stand doch auch schonmal drin bzw. es gibt einen Extra-Artikel dafür. --Koethnig 14:04, 10. Feb 2006 (CET)

Aus meiner Sicht genügt die Existenz weiterer Artikel dazu nicht. Es sollte dann immer noch überblicksmäßig darauf eingegangen werden, um dann auf den ausführlicheren Artikel zu verweisen. --AFBorchert 09:07, 11. Feb 2006 (CET)

• Es fehlt der geschichtliche Rückblick.

Was soll der enthalten? --Koethnig 14:04, 10. Feb 2006 (CET)

Wer das Problem zuerst formuliert hat und aus welcher Motivation heraus, wann welche Größenordnungen von TSP gelöst werden konnten, wann es qualitative Fortschritte in den Lösungsverfahren gegeben hat, wann die praktischen Anwendungen des Problems entdeckt wurden (erst, als es lösbar wurde, oder schon vorher?), usw. Siehe auch [1]. -- Sdo 23:01, 10. Feb 2006 (CET)

Meinst du das ernst? Das Problem gibt es sicher schon, seit Menschen denken können und die Motivation ist auch klar. Ich glaube nicht, dass man da eine Person findet, der man das ernsthaft zuschreiben kann (höchstens die erste mathematische Formulierung). Praktische Anwendungen für das Problem? Das ist doch sicher auch nicht ernst gemeint oder? "Größenordnungen lösen können" ist imho auch viel zu schwammig und irreführend, als das man dazu viel ernst zu nehmendes sagen könnte?! Und die Jahreszahlen für die Algorithmen gibt man einfach bei diesen an. Da braucht man so einen Geschichtsteil imho nicht. Interessant wäre höchtsens, wer sich wann wie intensiv mit dem Problem beschäftig hat, und was dabei rausgekommen ist. Aber so richtig viel hergeben wird das meiner Meinung nach nicht. Ich würde mich aber auch gerne eines besseren belehren lassen. --Koethnig 05:21, 11. Feb 2006 (CET)

Ja, das meinen wir ernsthaft. In der Mathematik gibt es eine lange Tradition, die Anfänge genau zu belegen. Es dürfte somit auch nicht zu schwierig sein, hier genaueres herauszufinden. Wohlgemerkt, ein Contra habe ich nicht gegegeben, sondern ein Neutral. --AFBorchert 09:02, 11. Feb 2006 (CET)

Ack AFBorchert. Ob die Motivation jedem klar ist, weiß ich nicht, zumal es mehrere Motivationen geben kann, sich mit dem Problem zu beschäftigen. Erstens ist es einfach zu beschreiben und leicht heuristisch, aber nur schwer optimal zu lösen, was es zur attraktiven Spielwiese gemacht hat. Zweitens hat es viele praktische Anwendungen. Konkrete Größenangaben und Meilensteine stehen z. B. unter dem oben angegebenen Link auf der TSP Homepage, wie auch einige Angaben zu den Ursprüngen des Problems. Ich kümmere mich mal darum, sobald ich mit meinen aktuellen Baustellen fertig bin... ;-) Gruß, -- Sdo 21:31, 11. Feb 2006 (CET)

Im Prinzip ist so ein Abschnitt ja auch richtig und wünschenswert, ich habe in diesem Fall nur einige Magenschmerzen bezüglich dessen, was da in bestimmte Aussagen reininterpretiert werden kann. Gerade bei den Größenordnungen muss man da schon sehr genau beschreiben, was damit gemeint ist. Soll heißen, was für Instanzen wurden da betrachtet? Auf welchen Rechenmachinen wurden sie geĺöst? Wie lange hat das gedauert? Welcher Alg. kam zu Einsatz? Und schon diese Fragen zeigen, wie fragwürdig solche Angaben sind. In derKomplexitätstheorie wurde nicht umsonst soetwas wie die O-Notation eingeführt. Ich kann dir leicht eine beliebige große Instanz basteln und dazu einen Algorithmus, der die Lösung sofort ausspuckt! --Koethnig 01:34, 12. Feb 2006 (CET)

Schon klar. Was mir im jetzigen Artikel einfach fehlt, ist ein Abschnitt zur praktischen Lösbarkeit und zu exakten Algorithmen. Der Text klingt so, als könne man mit der angegebenen Modellierung einfach ein IP aufstellen, es in einen General-Purpose-solver wie CPLEX füttern und schwupps, ist die Lösung da. Mit dem Ansatz kommt man natürlich nicht weit. Und dieses Bild würde ich gerne etwas geraderücken und klarmachen, dass hinter den Ergebnissen auf der TSP-Homepage echt viel mathematische und algorithmische Arbeit steckt und welche Art von Algorithmen da verwendet wurde. Ich werde mir Mühe geben, mich im Artikel präziser auszudrücken als hier... ;-) Gruß, -- Sdo 02:14, 12. Feb 2006 (CET)

• Der Abschnitt Algorithmische Komplexität hat gerade einen Absatz zur Komplexität und zählt danach nur noch Heuristiken auf.

Mehr kann man dazu nicht sagen! --Koethnig 14:04, 10. Feb 2006 (CET)

Wie sieht es mit exakten Verfahren aus? Die würde ich allerdings nicht hier einordnen, sondern zusammen mit den Heuristiken unter einem Abschnitt Lösungsverfahren. -- Sdo 23:01, 10. Feb 2006 (CET)

• Im Zuge der Allgemeinverständlichkeit würde ich empfehlen, den Artikel nach der Einleitung mit einem kleinen Beispiel zu eröffnen. Das Problem ist prinzipiell für jeden mit Papier und Bleistift nachvollziehbar. Die Mathematik kommt erst dann ins Spiel, wenn die Komplexität, die Lösungsansätze und die Heuristiken in Betracht gezogen werden.

--AFBorchert 11:01, 10. Feb 2006 (CET)

• Contra. Der Artikel ist gut lesbar und ordentlich strukturiert, aber er ist mir noch zu unvollständig. Ein vorheriger Review wäre sinnvoll gewesen (ist die Kandidatur eigentlich mit den Hauptautoren abgestimmt?). Exakte Lösungsverfahren fehlen völlig, die Geschichte ebenso. In diesem Zusammenhang wäre auch interessant, welche Größenordnungen von TSPs bisher exakt bzw. nahezu exakt lösbar sind. Das Problem ist zwar eine beliebte Spielwiese, hat aber reichlich praktische Anwendungen, die in der Einleitung genannt werden sollten. TSP mit Zeitfenstern und Online-TSP könnten noch erwähnt werden. (削除) Die Christofides-Heuristik setzt ein metrisches TSP voraus, wenn ich mich richtig erinnere – bitte nochmal nachprüfen und ggf. dazuschreiben. (削除ここまで)(erledigt -- Sdo). Dass der Artikel mathematiklastig ist, finde ich ok; es geht hier um ein mathematisches Problem. Allerdings kann man einiges anschaulicher formulieren. Insbesondere würde ich die graphentheoretische Modellierung vor die IP-Modellierung setzen und wahrscheinlich sogar als Definition nehmen, weil sie deutlich anschaulicher ist als ein IP oder die jetzige Definition über Permutationen. Das dürfte auch einigen der oben genannten Kritikpunkte entgegenkommen. Bei der IP-Modellierung sollte dabeistehen, dass hier die asymmetrische Variante modelliert wird. Üblicherweise wird das Problem auch auf einem vollständigen Graphen (mit big-M-Gewichten für fehlende Kanten) modelliert. Eine Kleinigkeit noch: die Abkürzung PdH ist meines Wissens völlig unüblich; TSP ist auch im deutschen Sprachgebrauch die übliche Abkürzung. Aber wie gesagt: der Artikel ist ein guter Anfang und auf dem besten Weg zu einem lesenswerten Artikel. Ich kann bei der Überarbeitung auch gerne mithelfen – der Artikel steht sowieso seit längerem auf meiner todo-Liste. Signaturnachtrag: -- Sdo 23:43, 10. Feb 2006 (CET)

•  Kontra: Der Artikel hat potential, aber zuviele Schwächen. Die mathematischen Formulierungen sind zu unsauber und teilweise werden Infos unnötiger Weise doppelt gegeben. Es fehlt der rote Faden. Der letzte Hauptautor hat aus meinem alten Artikel viele Dinge dankenswerter Weise übernommen, aber ohne sie an die richtgen Stellen zu sortieren, so das manche Überschrift überhaupt nicht mehr zum darauf folgenden Inhalt passt. Ich hätte den Artikel gerne erstmal im Review, da würde ich mich dann mit dran beteiligen aufzuräumen! Aber hier ist die Zeit dafür zu kurz, um aus dem contra noch ein pro zu machen --Koethnig 11:56, 10. Feb 2006 (CET)

 Kontra In dieser Form leider nur für Mathematiker verständlich. Da es sich jedoch um ein Problem handelt, mit dem sich auch Betriebswirte, Logistiker etc. beschäftigen sollte das Problem an Hand eines anschaulichen Rechenbeispiels erläutert werden. Vorbild könnte doch der Atrikel zum Ziegenproblem sein. --Rockhopper 20:49, 10. Feb 2006 (CET)

contra Heuristiken wie evolutionäre Algorithmen oder simulierte Abkühlung gehören unbedingt in den Artikel. --Phrood 23:12, 10. Feb 2006 (CET)

Contra Das einzige, was mir daran gefällt, ist der Link zun Spektrum-Artikel. Ob ich vor Jahrzehnten, als ich selbst Mathematische Optimierung als Diplomfach hatte, das Ganze lesenwert gefunden hätte - vielleicht. --84.158.7.10 13:21, 15. Feb 2006 (CET)

 Kontra Der Artikel sollte IMHO struktuierter sein und mehr erläuternden Text zwischen den Hard Facts haben ~ghw ^{.oO( )} 13:45, 15. Feb 2006 (CET)

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.

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)

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)

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)

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)

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 ${\displaystyle \epsilon }${\displaystyle \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)

Hier einige Notizen meinerseits, was noch zu tun ist, damit ich es nicht vergesse. Die Liste darf sowohl ergänzt als auch abgearbeitet werden. -- Sdo 11:47, 18. Aug 2006 (CEST)

• (削除) Die größte optimal gelöste Instanz hat mittlerweile 33810 Städte, siehe [2] und [3]. (削除ここまで) Erledigt. -- Sdo 22:20, 19. Aug 2006 (CEST)
• (削除) Schnittebenenbild durch ein passenderes ersetzen, etwa im Sinne der Bilder auf der Seite [4]. Das jetzige Bild bezieht sich auf ein Maximierungsproblem mit ganzzahligen Variablen und passt einfach so gar nicht zum Artikel. (削除ここまで) Erledigt. -- Sdo 02:28, 21. Aug 2006 (CEST)
• (削除) Das jetzige Schnittebenenbild ist immer noch doof, weil ganzzahlig und nicht 0/1. Das TSP-Polytop läßt sich nicht sinnvoll zeichnen: bei drei Städten besteht es aus dem Punkt (1,1,1), bei vier Städten ist es zwar höchstens dreidimensional, liegt aber irgendwie schief im ${\displaystyle R^{6}}${\displaystyle R^{6}} drin. Mir schwebt als Alternative gerade so etwas wie ein dreidimensionaler Würfel vor, von dem einige Ecken abgeschnitten sind, am besten mit Schnittebene dazu. So wie ein Stück Käse mit Käsemesserebene... Auf jeden Fall sollte das gezeigte Polytop so aussehen, als läge es im Einheitswürfel, und es sollte ein paar 0/1-Ecken haben. Hat noch jemand geniale Vorschläge dazu? -- Sdo 01:56, 23. Aug 2006 (CEST) (削除ここまで) Erledigt. Gefällt mir jetzt jedenfalls besser. -- Sdo 21:12, 27. Aug 2006 (CEST)
• (削除) Die asymmetrische IP-Formulierung mitsamt den zugehörigen Bildern durch eine symmetrische Version ersetzen (kann ich erledigen – ich habe die .fig-Quellen zu den Bildern). Das ist der üblicherweise betrachtete Fall, auf den sich auch die Rekordzahlen beziehen und für den die LKH-Heuristik und Concorde ausgelegt sind. (削除ここまで) Erledigt. -- Sdo 22:20, 19. Aug 2006 (CEST)
• (削除) Komplexitätsabschnitt überarbeiten, siehe Kommentare von P. Birken im Review. (削除ここまで) Erledigt. -- Sdo 01:56, 23. Aug 2006 (CEST)
• Anwendungen ausführlicher? Siehe Review.
• Bilder für die MST-Heuristik (auch im Artikel Minimum-Spanning-Tree-Heuristik einbauen).
• (削除) Einen kurzen Artikel Branch-and-Cut schreiben (z. B. auf Basis von Ganzzahlige lineare Optimierung, Schnittebenenverfahren und Branch-and-Bound), damit dieser Begriff endlich auf einheitliche Weise verlinkt werden kann. ;-) (削除ここまで) Erledigt: Branch-and-Cut. Ist sicherlich noch verbesserbar, aber schon mal ein Anfang. -- Sdo 22:45, 20. Aug 2006 (CEST)
• Übersichtstabelle zu den Lösungsverfahren? Siehe Vorschläge von Thomas M. im Review.

Das Problem ist, dass die verschiedenen Verfahren sehr unterschiedliche Zielsetzungen haben und teilweise miteinander kombiniert werden können. Eröffnungsheuristiken wollen eine erste Lösung berechnen, Verbesserungsheuristiken eine bestehende Lösung verbessern, duale Heuristiken eine untere Schranke berechnen. Bei Metaheuristiken und B&C kann alles miteinander kombiniert werden. Worst-case-Laufzeiten lassen sich nur bei einigen Eröffnungs- und dualen Heuristiken sinnvoll angeben – bei Metaheuristiken und Partitionsalgorithmen hängt sie von der Implementierung ab, und die Worst-case-Abschätzung von B&C ist genauso gut wie die von vollständiger Enumeration, was aber aus praktischer Sicht ein irreführender Vergleich ist. Eine tabellarische Zusammenfassung müsste sich also auf die Eröffnungsheuristiken beschränken, und dann ist die Frage, wie sinnvoll eine Tabelle noch ist. Was meint ihr dazu? -- Sdo 01:06, 27. Aug 2006 (CEST)

Du hast völlig recht, diese Probleme hatte ich - weitgehend unreflektiert - auch schon gesehen. Oft kann man nur einzelne Kriterien sinnvoll und nur paarweise zwischen Verfahren/Heuristiken vergleichen. Wenn man aber nie praktisch damit gearbeitet hat ist eine lückenhafte Tabelle zur Übersicht mMn hilfreicher als garkeine. Optimal wäre eine Tabelle für ein Beispiel, vielleicht 100 Städte, die Verfahren mit "sauberen" Zahlen, die Heuristiken und Kombinationen mit Mittelwerten für Berechnungsdauer und Fehlerabweichung. Eine solche Tabelle müßte man allerdings aus der Literatur nehmen, da es sonst womöglich "original research" ist. -- Thomas M. 18:36, 27. Aug 2006 (CEST)

Damit bewegen wir uns auf Glatteis. Solche Zahlen sind nur bedingt aussagekräftig, weil sie stark von der Implementierung und den verwendeten Instanzen abhängen. In der Literatur gibt es einen solchen umfassenden Vergleich vermutlich nicht, weil bisher keiner Zeit und Lust hatte, sämtliche Verfahren vernünftig zu implementieren. Das ist ja schließlich ein Heidenaufwand. Und Zahlen aus verschiedenen Veröffentlichungen kannst du erst recht nicht richtig vergleichen, weil zusätzlich meist auch noch unterschiedliche Instanzen und Hardware verwendet werden. Insofern kann so eine Tabelle sehr irreführend sein, weil sie Genauigkeit und Aussagekraft suggeriert, die nicht da sind. Ein qualitativer Vergleich sollte aus dem Fließtext hervorgehen. -- Sdo 18:53, 27. Aug 2006 (CEST)

Da sind wir auf einer Linie. Ein Vergleich mit Zahlen aus verschiedenen Quellen geht sicher nicht. Trotzdem wäre eine Übersichtstabelle hilfreich. Vielleicht auch nur mit ein paar qualitativen Werten, also exakt/nicht-exakt, Worst-case/best-case-Vergleich, Implementierbarkeit, Verbreitung. usw. Konkreteres kann ich jetzt aber auch nicht beitragen. -- Thomas M. 19:01, 27. Aug 2006 (CEST)

Ok, ich denke nochmal darüber nach. -- Sdo 21:12, 27. Aug 2006 (CEST)

• (削除) Eventuell eine kleine Ordung der Varianten durch Einteilung in Veränderungen der Randbedingungen, Zielfunktion(en) und Kombinationen derselben, oder nach Bedeutung oder durch historisches Erscheinen. (Fleißarbeit) (P.S. mit der Definition bin ich mittlerweile d'accord - wenn man sie im Zusammenhang mit der Einleitung sieht. P.P.S.: Großes Lob insgesamt für den Artikel!) -- Thomas M. 10:06, 24. Aug 2006 (CEST) (削除ここまで) Erledigt. -- Sdo 21:12, 27. Aug 2006 (CEST)

Ich habe die Varianten jetzt mal nach inhaltlichen Kriterien unterteilt. Praktisch relevant sind sie alle, und welche Variante wann zuerst in der Literatur vorkam, habe ich keine Ahnung. Da müsste ich erstmal ausführlich recherchieren. Aber so ist dieser Abschnitt auf jeden Fall strukturierter als vorher. (BTW: Danke für das Lob!) -- Sdo 01:06, 27. Aug 2006 (CEST)

So reicht es völlig. mMn -- Thomas M. 18:36, 27. Aug 2006 (CEST)

Abgerufen von „https://de.wikipedia.org/w/index.php?title=Diskussion:Problem_des_Handlungsreisenden&oldid=20744566"