Diskussion:Problem des Handlungsreisenden

Dieser Artikel war am 10. Januar 2007 der Artikel des Tages.

Automatische Archivierung

Auf dieser Seite werden Abschnitte automatisch archiviert, wenn sie mit {{Erledigt|1=--~~~~}} markiert sind. Die Archivübersicht befindet sich unter Archiv.

Name des Handlungsreisenden

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)

Kommt mir trotzdem noch seltsam vor: PONSline (PONS ist ja immerhin ein recht renommierter Wörterbuchverlag) sagt auch "Handelsreisender". Welche Wörterbücher übersetzen das denn tatsächlich mit "Handlungsreisender"?

Es kann durchaus sein, dass Wörterbücher den Begriff mit „Handelsreisender“ übersetzen (was den Kern der Sache meiner Meinung nach auch besser trifft), aber in der deutschsprachigen Fachliteratur zu dem Thema hat sich nun mal der „Handlungsreisende“ ganz klar durchgesetzt. Damit müssen wir einfach leben. -- Sdo 00:42, 22. Jul. 2007 (CEST)

...Mal wieder eine klassische Fehlübersetzung, die sich (leider) durchgesetzt hat - vielleicht kann man im Artikel darauf verweisen? -- 85.181.78.85 13:08, 22. Jul. 2007 (CEST)

...und daran wird sich nix ändern, wenn man nicht irgendwo mal anfängt, die (logisch) richtige Bezeichnung zu verwenden! Ich finde, auch wenn sich "Handlungsreisender" in der Fahliteratur durchgesetzt hat, könnte man den Artikel in "Handelsreisender" umbenennen, und von Ersterem darauf verlinken. Natürlich sollte man dabei irgendwo anmerken, dass dieses "Dilemma" existiert.--Lizziemcguire 13:10, 4. Mär. 2008 (CET)

Nein. Wir sollten die Bezeichnung wählen, unter der das Problem allgemein bekannt ist, und das ist der Handlungsreisende. Auch wenn die Bezeichnung ursprünglich aus einer falschen Übersetzung hervorgegangen ist, hat sie sich inzwischen zum Eigennamen entwickelt. Das sollten wir respektieren. Ändern werden wir den Namen des Problems in der allgemeinen Wahrnehmung nicht, weil für die Namensgebung nunmal die Fachliteratur und nicht die WP ausschlaggebend ist. Hier vom Handelsreisenden zu sprechen, würde höchstens zur Verwirrung beitragen. -- Sdo 01:17, 5. Mär. 2008 (CET)

Die Begründung von Sdo tönt stark nach: Ist so, weil ist so. Und dass Sdo normativ festlegt, unter welcher Bezeichnung das Problem allgemein bekannt sei nehme ich noch nicht als schlagendes Argument und dass sich aus einer ursprünglich (falschen?) Übersetzung inzwischen ein Eigenname entwickelt haben soll, bezweifle ich mal. Ich kenne das Problem ebenfalls nur unter der Bezeichnung: "Problem des Handelsreisenden" und meine Wörterbücher übersetzen salesman mit "der Handelsreisende" und nicht mit "der Handlungsreisende". Der liebe Duden allerdings kennt beide Formen. Nach einigem googlen habe ich den Eindruck, dass es regionale Unterschiede in der Verwendung der beiden Begriffe gibt.

Google meint (eingeschränkt auf Seiten aus der Schweiz) der Suchbegriff "Handlungsreisende" komme ca. 271 mal vor, während "Handelsreisende" ca. 2110 mal vorkommt. Google meint (eingeschränkt auf Seiten aus Deutschland): "Handlungsreisende": ca. 9000 mal, "Handelsreisende": ca. 17200 mal. Daraus lässt sich schliessen, dass die Verwendung des Begriffs "Handlungsreisender" beispielsweise in der Schweiz kaum gebräuchlich ist, während in Deutschland derselbe Begriff tatsächlich in Gebrauch ist. Und sofort stellt sich doch nun die Frage, ob denn der Titel tatsächlich so falsch ist (wenngleich ich zugebe, dass ich mich massiv am Begriff Handlungsreisender störe). -- 02:33, 11. Mär. 2008

Dass der Handelsreisende in der Schweiz verbreiteter ist als der Handlungsreisende, wusste ich tatsächlich nicht. Na gut, ich kann mit beidem leben. Es sollte beides mindestens als Redirect geben. -- Sdo 01:45, 12. Mär. 2008 (CET)

Tatsächlich geht es in diesem Artikel jedoch nicht im Geringsten um den Begriff des "Handelsreisenden" (Lemma), sondern um das "Problem des Handlungsreisenden", welches wie viele andere Begrifflichkeiten der Mathematik darauf verzichtet sich sprachlichen Konventionen zu unterwerfen. Eine gesonderte Betrachtung des Handelsreisenden macht keinen Sinn und Recherchen des Optimierungsproblems bezüglich (also insbesondere bei Suchmaschinen oder Wörterbüchern) nur dann, wenn der gesamte Begriff des "Problem des Hundlungsreisenden" (bei google etc. in Anführungszeichen) gesucht wird. Darüber hinaus besteht der Sinn einer Enzyklopädie keineswegs darin die Sprache zu formen. --91.17.202.60 11:25, 14. Apr. 2008 (CEST)

In der deutschen Literatur ist das Problem eigentlich als "Rundreiseproblem" geläufig. (vgl. das zitierte Buch von Domschke oder den zitierten Artikel von Grötschel und Padberg.). Das ist nicht wörtlich übersetzt, aber es ist griffig und bequem auszusprechen, (und man vermeidet die Frage, wie der Handelsvertreter eigentlich heißt. ;-) Dadurch, dass viele Leute das Problem aus der englischen Literatur kennen, hat sich die wörtliche Übersetzung aus dem englischen leider verbreitet. Ich wäre dafür, den Artikel auf Rundreiseproblem umzubenennen. (mit einem Verweise von der alten Bezeichnung.) -- Günter Rote, 25.6.2007

Meines Wissens ist „Rundreiseproblem“ deutlich weniger geläufig als die anderen beiden Namen. Als Indikator (wenn auch nicht als Beweis) mag dienen, dass Google eingeschränkt auf deutsche Seiten 56.400 Treffer für „Problem des Handelsreisenden“, 30.500 Treffer für „Problem des Handelsreisenden“ und 1.190 Treffer für „Rundreiseproblem liefert.“ -- Sdo 14:13, 26. Jun. 2008 (CEST)

Vom "Rudreiseproblem" habe ich noch nie gehört. Und dass sich eine der beiden Möglichkeiten (Handelsreisender oder Handlungsreisender) durchgesetzt hat, kann man wohl kaum sagen: Wer Deutsch kann, benutzt den "Handelsreisenden" (den es auch gibt und was die korrekte Übersetzung für den "travelling salesman" ist), wer nur nachplappert oder nicht nachdenkt, benutzt den "Handlungsreisenden". Was soll das sein? Der Begriff wird im Duden nicht einmal genannt. In der Mathematik (bzw. in der Fahliteratur) findet man jedenfalls beide Begriffe. Und warum sollte man hier nicht den richtigen verwenden.

Wie ich sehe wird das Namensproblem schon behandelt. Ich habe mich, als ich das Thema gesucht habe erst einmal gewundert bei so einer Wortverdrehung gelandet zu sein. Man muß doch einfach nur mal sprachlich-logisch über das Problem nachdenken. Es geht doch um eine umherfahrenden Händler. Und dieser ist doch somit nichts anderes als ein Handelsreisender..... --79.199.115.185 00:25, 25. Okt. 2009 (CEST)

Um einmal etwas Klarheit in diese schier endlose Diskussion zu bringen, sei auf folgenden Eintrag im Synonymwörterbuch verwiesen: Unter "Vertreter, Vertreterin" steht unter anderem folgendes: c) [...],Handelsreisender, [...], (Kaufmannsspr.): Handlungsreisender [...] (Quelle: Duden - Das Synonymwörterbuch, 4. Aufl. Mannheim 2007 [CD-ROM]). Das dürfte eigentlich die Frage, ob nun Handels- oder Handlungsreisender, beantworten. --Mahriser 10:24, 24. Aug. 2010 (CEST)

Ja: Wir reden hier über Informatik und Mathematik, nicht über Kaufmannschaft. Es geht z.B. darum, eine optimale Reihenfolge für das automatische Setzen von Bohrungen zu bestimmen o.a. Graf Alge (Diskussion) 11:26, 17. Nov. 2016 (CET)

Üblich - und auch in vielen Lehrbüchern verwendet - ist auch im Deutschen die Bezeichnung "Travel(l)ing-Salesman-Problem (TSP)". In der deutschen Übersetzung des Standardlehrbuchs zu Algorithmen (von Cormen, Leiserson, Rivest und Stein) wird "Problem des Handelsreisenden" benutzt. Die merkwürdige Übersetzung "Problem des Handlungsreisenden" habe ich hier in Wikipedia zum ersten Mal gesehen. Graf Alge (Diskussion) 16:24, 27. Okt. 2015 (CET)

Ich möchte nochmal nachdrücklich eine Umbenennung des Lemmas in "Problem des Handelsreisenden" anregen. Auch im deutschen Standardlehrbuch "Graphentheorie" von R. Diestel wird diese Übersetzung verwendet. Diestels Buch enthält einen ausführlichen Index englisch-deutscher Fachbegriffe - eine Referenz, an die sich Wikipedia halten könnte... Graf Alge (Diskussion) 11:26, 17. Nov. 2016 (CET)

(auch (...) Handelsreisenden, (...)) in die Einleitung eingefügt. Handlungsreisender veraltet ja zunehmend. Helium4 (Diskussion) 19:34, 19. Feb. 2023 (CET)

Abgeschlossene Lesenswert-Diskussion (abgelehnt)

 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)

Zu erledigen

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 $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. Bleibt so. -- Sdo 20:43, 1. Okt 2006 (CEST)
• Bilder für die MST-Heuristik, auch (vielleicht sogar auschließlich?) im Artikel Minimum-Spanning-Tree-Heuristik einbauen. Das betrifft vor allem den Artikel Minimum-Spanning-Tree-Heuristik und weniger diesen hier. -- Sdo 20:43, 1. Okt 2006 (CEST)
• 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. Erledigt. Sdo 00:50, 31. Aug 2006 (CEST)

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)

Ich habe mal für die Eröffnungs-, Konstruktions- und Verbesserungsheuristiken eine Tabelle gebastelt. Metaheuristiken, Partitionsheuristiken und exakte Verfahren habe ich rausgelassen, weil sich dazu unter den angegebenen Gesichtspunkten wenig sagen lässt. Vorschläge zur Verbesserung der Tabelle nehme ich gerne an. Ich wäre auch ganz dankbar, wenn nochmal jemand die angegebenen Laufzeiten auf Plausibilität prüfen könnte. Zum Teil habe ich diese in den jeweiligen Artikeln gefunden, zum Teil habe ich sie mir aber auch gerade selbst überlegt, so dass eine Überprüfung nicht schlecht wäre. Eine sehr kurze Zusammenfassung der Laufzeitbegründung habe ich jeweils in einem Quelltext-Kommentar dazugeschrieben. Gruß, -- Sdo 00:50, 31. Aug 2006 (CEST)

Ohne meine Literatur bin ich im Detail keine große Hilfe - lediglich die "Summe der kürzesten Kanten" hätte ich spontan auf O(n²) geschätzt. Wenn sich die Werte bestätigen ist die Tabelle mMn wirklich toll, da man gut sehen kann, dass es die Methode nicht gibt und alle ihre Vor- aber besonders Nachteile haben. Bei mehr Kriterien würde das noch deutlicher, aber so reicht es dicke. Danke :-) -- Thomas M. 13:17, 31. Aug 2006 (CEST) ...und viel Erfolg - auch bei Exzellenz

O(n²) war auch meine erste Schätzung, aber bei genauerem Überlegen sind mir nur folgende Varianten eingefallen: (1) man sortiert die Kanten (das braucht O(m log m) = O(n² log n)) und geht sie dann durch, oder (2) man geht n-mal alle Kanten durch und sucht sich die kürzeste raus – das braucht O(nm) = O(n³), ist also teurer. -- Sdo 00:32, 1. Sep 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)

• Ein paar von den roten Personenlinks mit Inhalt füllen. -- Sdo 02:52, 2. Sep 2006 (CEST)

Es wäre schön, wenn auf der Landkarte auch 15 Städte namentlich aufgeführt wären - es fehlt (nur der Name) Dortmund. -- [[Benutzer:Dottore E.] 12:04, 7. Sep 2018 (CEST)

Metriken

Ich hatte die Metriken nicht ganz grundlos umsortiert. Es sind handelt sich bei diesen nämlich um die Standardbeispiel der durch die L1-, L2- und L-Unendlich Norm induzierten Metriken. Die L1-Norm induziert die Manhatten, die L2-Norm die Euklidische und die L-Unendlich-Norm die Maximum Metrik. für beliebige x mit x>=1 lassen sich entsprechende Normen definierien, die dann eine entsprechende Metrik induzieren. Insofern hat die Umstellung lediglich die in diesem Sinne "natürliche" Reihenfolge wiedergegeben! Das ist übrigens entwas, was man sowieso noch schöner herausarbeiten könnte. Allerdings gehört das größtenteils in den Artikel zu den Metriken aufgeräumt. --Koethnig 13:23, 6. Okt 2006 (CEST)

Hallo Koethnig, ich habe deinen Kommentar erst jetzt gesehen. Der Hintergrund hinter deiner Normen-Reihenfolge war mir zwar klar, aber erst nach einigem Nachdenken. Ich habe die Metriken deshalb wieder umsortiert, weil diese Reihenfolge nur von Mathematikern verstanden wird. Für alle anderen ist die euklidische Metrik nun mal die intuitivste, und wer die p-Normen nicht kennt, für den ist auch nicht einsichtig, warum Maximums- und Summennorm nicht zusammenstehen, wenn sie hinterher zusammen besprochen werden. -- Sdo 23:02, 15. Okt. 2006 (CEST)

Lesenswert-Kandidatur, 1. Oktober 2006 (erfolgreich)

Der Artikel wurde seit der letzten Kandidatur gründlich überarbeitet und im Review nochmal verbessert. Als einer der Hauptautoren ohne eigenes Votum. -- Sdo 21:09, 1. Okt 2006 (CEST)

•  Pro Klar! --Tamás 12:42, 3. Okt 2006 (CEST)
• Nach den jüngsten Kritiken auf der Diskussionsseite des Artikels bleibt mir nur ein (Laien-) Kontra.--84.137.231.26 13:49, 3. Okt 2006 (CEST)

Kannst du das auch näher begründen? Im Augenblick geht es in der Diskussion ausschließlich darum, wieviel Raum man dem komplexitätstheoretischen Hintergrund zum TSP einräumt und wie exakt man dabei sein möchte. Von Fehlern spricht niemand, es geht nur um Präzisierungen. --Scherben 15:19, 3. Okt 2006 (CEST)

Die Präzisierungen sind auch mittlerweile durchgeführt. -- Sdo 23:37, 4. Okt 2006 (CEST)

Ich bezog mich eigentlich auf den Teil „Fehlendes, Fehler[...]“, wo darauf hingewiesen wird, dass der Artikel strenggenommen nur das Suchproblem behandelt, eigentlich aber noch das Optimierungs- und das Entscheidungsproblem behandeln müsste. Da 1. dieser Teil mitlerweile als „erledigt“ markiert ist und ich mich 2. nach 2 Vorlesungen die das Thema nicht sooo detalliert behandelten, auf dem Gebiet lieber als Laie bezeichne, soll es an mir nicht scheitern. Ich streiche also gerne mein contra (wie oben bereits geschehen) und gehe über zu  Neutral.--84.137.213.48 14:19, 5. Okt 2006 (CEST)

• Pro. Hab nix zu meckern. —mnh·∇· 17:54, 3. Okt 2006 (CEST)
• pro super Artikel, steckt viel Arbeit drin. Schön wärs, wenn noch jemand die genaue Definition unter NP-Äquivalenz/NP-leicht nachtragen könnte, das ist mir nämlich nicht klar. --Kurt seebauer 22:55, 4. Okt 2006 (CEST)

Ich habe mal Koethnig darauf angesprochen, der kennt sich damit genauer aus. NP-Äquivalenz ist im wesentlichen dasselbe wie NP-Vollständigkeit, nur für Suchprobleme statt für Entscheidungsprobleme. -- Sdo 23:37, 4. Okt 2006 (CEST)

• pro Der Artikel ist auch IMHO nahe an der Exzellenz, da wuerde ich mir aber wuenschen, dass meine Kritik aus dem Review umgesetzt wird: Statt alle Verfahren der ganzzahligen linearen Optimierung kurz zu beschreiben und Aussagen darueber aufzulisten sollten im wesentlichen nur die speziellen Aussagen bzgl. dieser Verfahren zum TSP genannt werden. Deutlich sieht man das eben beim Abschnitt "Metaheuristische Verfahren", der nichts mit dem konkreten Problem zu tun hat. --P. Birken 12:50, 5. Okt 2006 (CEST)

Ich hatte den Teil auf deine Anregung hin erstmal etwas problemspezifischer formuliert, werde ihn aber gelegentlich in Metaheuristik einarbeiten und hier kürzen. Ist vorgemerkt. -- Sdo 15:18, 5. Okt 2006 (CEST)

Übertragene Bedeutung von Entfernung

Für mathematikferne Leser sollte schon in der Einleitung bzw. überhaupt eine kleine Bemerkung eingebaut werden, dass Entfernung symbolisch gesehen werden kann. Genauso gut können auch die Kosten, die Zeit, der Energieverbrauch, ... optimiert werden. Im Geschichtsabschnitt steht ohne weitere Erklärung ' ... Anwendungen u. a. in der Informatik, den Wirtschaftswissenschaften, der Chemie und der Biologie'. Welches Entfernungsmaß bei der Genomsequenzierung benutzt wird, versteh ich zB nicht so ohne Weiteres. Und wenn ich den Artikel richtig gelesen habe, taucht Zeit als Begriff nur so nebenbei bei den Metriken im Bohrerbeispiel auf. Der Abschnitt 'Varianten und Anwendungen' sollte zur Zeit noch wohl besser 'Varianten und Anwendungen heißen. -- Erlanger 20:40, 18. Okt. 2006 (CEST)

Gute Hinweise, danke. Die Abschnittsüberschrift hat schon jemand geändert, und ich habe in die Einleitung noch einen Satz eingebaut, der den Zusammenhang des Bildes zu den Anwendungen hoffentlich etwas klarer macht. Besser so? -- Sdo 00:24, 19. Okt. 2006 (CEST)

Rekorde für optimale Lösungen

Bedeutet im Geschichtsabschnitt "konnten optimal lösen", dass für eine ganz bestimmte Instanz eine Lösung gefunden wurde? Oder heißt es, dass für TSPs der genannten Größe ein optimaler Algorithmus gefunden wurde? Oder heißt es, dass die Lösung in annehmbarer Zeit gefunden wurde und man einfach nicht länger warten wollte, um größere zu lösen und die Optimalität zu beweisen? Prinzipiell braucht man ja nur alle Lösungen durchprobieren. Ich frag nur, weil ich Chancen sehe, dass Nichtmathematiker wenigstens noch diesen Abschnitt lesen und eine Bemerkung dazu verstehen könnten.-) -- Erlanger 20:40, 18. Okt. 2006 (CEST)

Wie es da stand: einzelne Instanzen beweisbar optimal gelöst. Ich habe versucht, es noch etwas deutlicher zu formulieren. Ist es so auch für Nichtmathematiker klar? -- Sdo 00:24, 19. Okt. 2006 (CEST)

Selbstwiderspruch: Im Geschichtsteil steht gegenwärtig eine anderer Rekord als weiter unten im Abschnitt über praktische Grenzen der Berechenbarkeit. (nicht signierter Beitrag von 134.2.81.235 (Diskussion) 13:21, 17. Jun. 2011 (CEST))

Ist jetzt (nur 13 Jahre später) behoben. --BumbleMath (Diskussion) 07:37, 16. Jan. 2024 (CET)

Exzellenz-Kandidatur (erfolgreich)

Während der Lesenswert-Kandidatur vor zwei Wochen und beim Mathematik-Portal kam der Wunsch nach einer Exzellenzkandidatur auf. Nachdem ich gerade noch einige Anregungen eingearbeitet habe, stelle ich ihn daher hier zur Wahl. Als einer der Hauptautoren ohne Votum. -- Sdo 00:12, 16. Okt. 2006 (CEST)

• Gibt es einen Grund, warum genetische Algorithmen oder simulierte Abkühlung keine Erwähnung finden? --Phrood 00:39, 16. Okt. 2006 (CEST)

Ja, zu gründliches Kürzen bei meiner Auslagerungsaktion vorhin. ;-) Sie stehen jetzt wieder drin. Ausführlich erklären will ich sie hier nicht, weil sie nichts mit dem speziellen Problem zu tun haben und sich außerdem beim TSP im Vergleich zu problemspezifischen Heuristiken nie richtig durchgesetzt haben. -- Sdo 01:14, 16. Okt. 2006 (CEST)

Hm, soweit ich weiß, erwähnt zumindest Sedgewick in seinen "Algorithms in C" die simulierte Abkühlung für TSP. Ich glaube auch, dass genetische Algorithmen ziemlich effizient, allgemein und oft nahezu optimal sind. Da bin ich skeptisch gegenüber dem etwas negativen Unterton, mit dem sie im Text erwähnt werden. Trotzdem jetzt ein vorsichtiges  Pro --Phrood 01:41, 16. Okt. 2006 (CEST)

Ich glaube nicht, dass deine Meinung mit dem entscheidenden Satz Prinzipiell können all diese Verfahren gute Lösungen berechnen, aber auch beliebig schlecht im Vergleich zu einer Optimallösung sein. in Widerspruch steht. Oder habe ich was übersehen? --Scherben 11:06, 16. Okt. 2006 (CEST)

Ack Scherben. Sie werden im Artikel relativ neutral erwähnt. -- Sdo 12:37, 16. Okt. 2006 (CEST)

•  Pro Ich war auf den Artikel schon im Review aufmerksam geworden. Es ist eine gelungene und umfassende Betrachtung dieses Optimierungsproblems.--Philipendula 09:51, 16. Okt. 2006 (CEST)
•  Pro Wurde in Teamarbeit von fleißigen Fachleuten zweifellos auf Exzellenzniveau gebracht. Der Artikel sollte hier nur nochmal von kritischen Nicht-Mathematikern auf Allgemeinverständlichkeit geprüft werden. --Tamás 12:38, 16. Okt. 2006 (CEST)

Wurde zum Teil schon von mir diesbezüglich durchforstet. --Philipendula 12:16, 18. Okt. 2006 (CEST)

• Pro: Einfach ein schoener Artikel. --P. Birken 12:08, 18. Okt. 2006 (CEST)
•  Pro Als Nicht-Mathematiker (Ingenieur)... finde ich den Artikel verständlich, und ich finde ihn zurecht VorgeschlagenDüsentrieb 12:56, 18. Okt. 2006 (CEST)
•  Kontra Der Abschnitt zur Formulierung als ganzzahliges Problem erscheint mir irgendwie zu lang. Die Länge verliert ihre Berechtigung for allem dadurch, dass sie nicht weiterführt. Es wird zwar immer wieder behauptet, dass man das Problem praktisch in dieser Formulierung löst, aber die Verfahren werden kaum dargestellt und es wird auch nicht alles verlinkt, bzw. verlinktes ist zu ungenau. Zudem scheint der Abschnitt im Vergleich zum Rest zu genau formuliert. Auf wesentliche Teile der Formulierung komme ich selbst, ohne jedes Detail in diesem Abschnitt lesen zu müssen. An sich hab ich nichts gegen genaue Darstellungen, aber ich frage mich, warum bei den "handfesteren" Teiles des Artikels dann auf diese Genauigkeit verzichtet wird. Dadurch wirkt dieser Abschnitt irgendwie wie ein Fremdkörper im Artikel. --Koethnig 13:58, 19. Okt. 2006 (CEST)

Auch wenn Sdo das sicher besser erklären kann, mein Kommentar dazu in Kurzform: Die typische Formulierung des TSP als Optimierungsproblem ist die als ganzzahliges lineares Programm, sie zu verstehen ist eine unabdingbare Voraussetzung, um die Optimierungsverfahren zu verstehen. Deshalb hat sie m. E. zurecht eine prominente Stellung im Artikel - und sie ist auch so detailliert formuliert, weil das eine Kritik im Review war. Dass Mathematiker und Informatiker recht schnell verstehen, welche Einschränkungen an die Variablenbelegung gestellt werden müssen, ist "einkalkuliert". Naja, und alle Verfahren zur exakten Lösung (Branch and Cut, Branch and Bound, Schnittebenen, ... ) bauen auf genau dieser Formulierung auf. Diese Verfahren werden angedeutet, aber die exakte Erklärung ihrer Funktionsweise wird in die Einzelartikel verlegt. Was wäre denn dein Vorschlag? Dass man diese Verfahren detailliert erklärt? Dass man sie etwas detaillierter erklärt? Und welche Links fehlen dir? Grüße --Scherben 14:10, 19. Okt. 2006 (CEST)

@Koethnig: Wo fehlt dir Genauigkeit? Der Artikel behauptet übrigens nicht, „dass man das Problem praktisch in dieser Formulierung löst“, sondern stellt den ILP-Ansatz als eins von mehreren möglichen Lösungsverfahren dar. Weiter unten steht auch ein Kommentar dazu, dass dieser Ansatz hauptsächlich im Forschungsumfeld verwendet wird. Dass die ILP-Modellierung relativ ausführlich erklärt wird, hat mehrere Gründe. Erstens ist der ILP-Ansatz das einzige bekannte Verfahren, um bewiesenermaßen Optimallösungen zu berechnen (von Enumeration mal abgesehen), und damit aus mathematischer Sicht interessant. Zweitens ist der Zusammenhang zwischen 0/1-Vektoren und Touren für Laien alles andere als trivial, aber m.E. mit einer ausführlichen Erklärung und etwas Nachdenken noch zu verstehen. Für dich mögen da Trivialitäten drinstehen, aber die Modellierung soll auch für Nichtmathematiker verständlich sein. Dagegen werden die zugehörigen Verfahren (wie Branch-and-Cut) nur verlinkt und nicht genauer erklärt, weil sie erstens unabhängig von dem spezifischen Problem sind (siehe auch Kommentar zu Metaheuristiken in der Lesenswert-Diskussion), zweitens in den verlinkten Artikeln ausführlich beschrieben und drittens sowieso nur für Leute mit Vorkenntnissen in Linearer Optimierung zu verstehen sind. Das führt im Rahmen dieses Artikels einfach zu weit. Gruß, -- Sdo 00:46, 20. Okt. 2006 (CEST)

Soweit ich es aus dem Artikel nachvollziehen kann, tut das ILP-Verfahren nichts anderes als zu Enumerieren. Nur wird die Enumeration hier in der Modellierung "versteckt". Genau da ist dann auch das nächste Problem. Es wird, wie der Artikel ja auch sagt, garnicht wirklich komplett modelliert, sondern nur sinnvolle Teile. Das ist dann nichts anderes, wie bei der Enumeration überflüssige Pfade nicht weiter zu verfolgen. Wenn das ganze nicht vollständig modelliert wird, kann man sich berechtig die Frage stellen, warum und wie die ILP-Verfahren dafür dann noch funktionieren. Ich schätze mal, dass die verlinkten Artikel dazu von vollständig ausformulierten ILPs ausgehen (ich habs jetzt aber nicht nachgeprüft). In diesem Fall müsste/könnte man dazu noch was sagen, was dann nat. Fachwissen voraussetzt. Dann würde der Abschnitt wenigstens nicht mehr so sehr als Fremdkörper auf mich wirken. Ungenau ist der Artikel vor allem da, wo es um die Komplexitätstheorie geht. Momentan ist es wenigstens richtig, aber ich schätze mal, es wird nicht lange dauern, bis da jemand wieder Fehler einbaut, weil er vermeintlich glaubt Ahnung zu haben. der teil zu den aproximativen heuristiken könnte auch ausführlicher sein. jedenfalls steht das imho nicht so richtig in relation zu der ausführlichkeit im oben genannten Abschnitt. --Koethnig 13:54, 20. Okt. 2006 (CEST)

Die Modellierung ist vollständig. Jeder 0/1-Vektor, der (1) und (2) erfüllt, definiert eine Tour, wie es auch im Artikel steht. Auch die Enumeration durch Branch-and-Cut ist vollständig in dem Sinne, dass alle Optimallösungen während der Enumeration betrachtet werden. Lag das Missverständnis an dem Satz über die unbekannten Facetten? Ich habe ihn mal etwas klarer formuliert. Damit ist dein erster Einwand hoffentlich behoben. Branch-and-Cut macht übrigens mehr als Enumeration, weil durch zusätzliche Schnittebenen Teile des Branch-and-Bound-Baums früher abgeschnitten werden können. Warum und wie das genau funktioniert, steht in den Spezialartikeln. Den Komplexitätsteil würde ich hier höchstens um spezielle TSP-Resultate erweitern wollen. Allgemeinere komplexitätstheoretische Ausführungen sollten in den verlinkten Spezialartikeln stehen. Die Korrektheit der Aussagen müssen wir im Auge behalten, aber das trifft auch auf den Rest des Artikels zu. Die vielen einzelnen Primalheuristiken sind jeweils knapper erklärt als der ILP-Ansatz, weil sie mathematisch nicht so spannend und einfacher zu verstehen sind, und weil es zu den meisten dieser Heuristiken brauchbare und nicht zu lange Spezialartikel gibt. Insgesamt nimmt der heuristische Teil aber mindestens genausoviel Platz ein wie der exakte, weil Heuristiken in der praktischen Anwendung deutlich verbreiteter sind. -- Sdo 14:54, 20. Okt. 2006 (CEST)

•  Pro Besser als alles, was ich im Informatikstudium zu diesem Thema angetroffen habe. PumpingRudi 20:47, 22. Okt. 2006 (CEST)
• Pro Schafft den schwierigen Spagat, mathematisch exakt und dennoch verständlich (zumindest ab Abiturniveau) zu sein. Die Grafiken helfen ungemein für das Verständnis.--Uwe G. ¿⇔? 10:29, 24. Okt. 2006 (CEST)
• Dafür: Mir gefällt der Artikel. Verständlich, aber geht dennoch in die Tiefe. Exzellent. -- Dishayloo + 10:49, 25. Okt. 2006 (CEST)

Erwähnung, dass Optimalität 'nur' aus sportlichen Gründen interessant ist

Das bezieht sich auf meine (Erlanger) Einfügung vom 14.11.1006 und Scherbens Revert: Da das TSP nun einmal eine Aufgabenstellung ist, die und deren Nutzanwendung auch Nicht-Mathematiker verstehen können, bin ich der Meinung, dass erwähnt werden sollte, dass hinter dem Streben, das Optimum zu finden und zu beweisen, nur der mathematische Erkenntnistrieb steckt. Nicht-Mathematiker interessiert die Beweisbarkeit doch nur bis zum Äh, ja, interessant. Die beiden Plätze für diesen nicht-mathematischen Punkt sah ich in der Einleitung und bei der Praxis. Und die Einleitung ist eh schon vollgestopft genug.

Btw: Ceterum censeo, dass bis auf das ADAC-Beispiel und den immer wieder gern bemühten Routenplanungen, in den Varianten nur wenig konkrete Anwendung aus dem täglichen Leben und Erleben des Lesers vorkommen. Oder Beispiele, in denen deutlich wird, dass TSP wirklich nicht nur was für Verkehrsplanung ist. Wo taucht zB ein TSSP oder ein BTSP auf? Alternativ kann man auch und Anwendungen in der Überschrift weglassen. Aber das hatten wir ja schon.-) -- Erlanger 20:13, 14. Nov. 2006 (CET)

Ich dachte, dass eine Passage dieser Art schon irgendwo im Artikel steht. Muss wohl bei irgendeiner Überarbeitung rausgeflogen sein. --Scherben 20:27, 14. Nov. 2006 (CET)

Im ersten Satz des Abschnitts Varianten und Anwendungen und unter dem dort angegebenen Link sind einige konkrete Anwendungen von Concorde angegeben, die nichts mit Verkehrsplanung zu tun haben. Tourenplanung, ggf. mit weiteren Nebenbedingungen, ist meines Wissens tatsächlich eine wichtige Anwendung. Jeder Betrieb, dessen Außendienstmitarbeiter mehrere Kunden abklappern müssen (z. B. ein technischer Kundendienst), hat TSPs zu lösen. Dass die wenigsten Betriebe dieses Problem als TSP verstehen oder am Ende gar mit exakten Methoden lösen, ist eine ganz andere Sache. Wo jetzt genau Prize Collecting TSP und so etwas auftreten, weiß ich auch nicht, aber ich vermute mal, irgendwelche Anwendungen dafür wird es geben, sonst hätte sich keiner diese Varianten ausgedacht. -- Sdo 23:28, 14. Nov. 2006 (CET)

Name des Problems

Müsste es korrekterweise nicht Handelsreisenden und nicht Handlungsreisenden heissen ?

Dieser Name des Problems hat sich in der Literatur eingebürgert, also heißt es hier auch so. --Scherben 10:16, 10. Jan. 2007 (CET)

Siehe auch erstes Kapitel auf dieser Diskussionsseite, da wurde das schon mal diskutiert. -- Sdo 11:26, 10. Jan. 2007 (CET)

Auf den Diskussionsseiten ist es im Gegensatz zu den Artikelseiten erlaubt, Richtiges auch zu etablieren versuchen; wir dürfen hier also ruhig "Handelsreisender" oder "Rundreiseproblem" sagen und hoffen, dass es irgendwann eine neue Abstimmung gibt. Die Forschungselite richtet sich bei ihren Benennungen sowieso nicht nach Wikipedia. --Heinrich Puschmann (Diskussion) 14:51, 25. Jan. 2013 (CET)

Ja, zum Glück! Graf Alge (Diskussion) 16:38, 27. Okt. 2015 (CET)

Anwendung des Problems

Die Aussage ein Problem finde verschiedene Anwendungen halte ich für widersinnig. Ein Problem, wie etwa das TSP, kann bei verschiedenen Fragestellungen aus den unterschiedlichsten Bereichen auftreten. Daher kann ein Lösungsansatz, wie bestimmte Heuristigen, in verschiedenen Bereichen genutzt werden. Das Problem selbst ist aber keine Problemlösung. (nicht signierter Beitrag von 84.169.245.75 (Diskussion) )

Was genau willst Du mir sagen? Bei der Gelegenheit zwei Bitten: 1. unterschreibe mit vier Tilden (~~~~) und 2. schreibe keine Diskussionsbeiträge in Artikel. Danke. -- Sdo 22:16, 7. Jan. 2007 (CET)

Hat er/sie doch geschrieben! Ein Problem findet keine Anwendung. Ein Problem tritt vielmehr (in verschiedenen Bereichen) auf! --Koethnig 22:49, 7. Jan. 2007 (CET)

Ah, ok! Danke. Hab's geändert. -- Sdo 23:22, 7. Jan. 2007 (CET)

Typo?

"im schlimmsten Fall exponentiell von der Anzahl der Städte abhängt" im besten Fall? 90.128.111.200 13:59, 10. Jan. 2007 (CET)

Im besten Fall findet der Algorithmus die optimale Lösung sofort. --Scherben 14:20, 10. Jan. 2007 (CET)

Es handelt sich glaube ich um ein Sprachproblem: (ein guter, der beste) Algorithmus braucht schlimmstenfalls (im ungünstigsten Fall) exponentielle Zeit, oder aber ein (schlechter) schlimmer Algorithmus braucht exponentielle Zeit, was zugegebenermaßen nicht besonders sinnvoll ist (der schlechteste A. braucht ewig...). 90.128.111.200 16:16, 10. Jan. 2007 (CET)

du hast Recht: ein gegebener Algorithmus kann eine Best-Case-Laufzeit in O(1) haben, während die Worst-Case-Laufzeit exponenziell sein _sollte_ (es wären aber prinzipiell auch schlechtere Algorithmen denkbar). Ich glaube aber, die Aussage sollte sich sinnvollerweise auf die Average-Case-Laufzeit beziehen, und die ist für keinen Algorithmus besser als exponenziell. (wie oben könnte ein Algorithmus auch prinzipiell eine schlechtere Laufzeit haben)

... wie dekliniert man Algorithmus? Des Algorithmusses? --androl 12:05, 11. Jan. 2007 (CET)

So dekliniert man Algorithmus: [5] :-) --jpp ?! 13:00, 11. Jan. 2007 (CET)

Die Änderung mit der durchschnittlichen Laufzeit habe ich mal wieder rückgängig gemacht. Um durchschnittliche Laufzeit geht es hier definitiv nicht. Die Aussage lautet m.E.: Falls P $\neq$ NP ist, dann kann man für jeden polynomialen deterministischen Algorithmus eine Instanz konstruieren, für die dieser Algorithmus mindestens exponentielle Laufzeit benötigt. Anders ausgedrückt: die Worst-Case-Laufzeit jedes polynomialen deterministischen Algorithmus ist im besten Fall exponentiell. Ich habe das in der Einleitung etwas umformuliert und hoffe, es ist jetzt klarer (und korrekt...;)). -- Sdo 01:03, 12. Jan. 2007 (CET)

AMAZON.COM und der Algorhythmus

Es scheint, dass Amazon.com in seinem Versandzentrum ebenfalls einen entsprechenden Algorhythmus zum Zusammenstellen der Sendungen verwendet, der mit dem Problem des Handlungsreisenden in Verbindung steht. Leider ist der Artikel in dem populärwissenschaftlichen Magazin "P.M." nur kostenpflichtig abrufbar. Wer das Heft hat - der Artikel steht in Heft 07/2005.

http://www.pm-magazin.de/de/aktuellehefte/inhalt/inhalt_id345.htm -- (nicht signierter Beitrag von 217.184.123.208 (Diskussion) 17:45, 10. Jan. 2007)

Danke für den Tip! Da ich das Heft nicht habe, interessehalber die Frage: welchen Algorithmus verwenden sie? Steht das in dem Artikel drin, oder steht da nur, dass Amazon TSPs zu lösen hat? -- Sdo 19:23, 10. Jan. 2007 (CET)

Nettes Applet zum Problem

Ich habe hier ein nettes Java-Applet zum Problem, bei dem die Sache mit genetischen algorithmen gelöst wird. (D.h. es gibt eine zufällige Lösung ("Individuum"), die mit einer anderen zufälligen Lösung gekreutzt wird. Daraus ergibt sich eine Tochtergeneration, die Zahl der Individuen erhöht sich. Das Programm beschränkt allerdings diese Zahl und löscht die schwächsten individuen (die mit dem längsten Weg). Die Population bleibt also immer gleich groß. Damit ein möglichst gutes Ergebnis erziehlt wird, kommen auch mutationen vor (zufällige veränderungen). Das ganze ist auch grafisch recht anschaulich: http://www.geosimulation.de/umsetzungen/2_0_2_Modelle/Problem_des_Handlungsreisenden.html

Christoph -- (nicht signierter Beitrag von 84.148.204.165 (Diskussion) 18:48, 10. Jan. 2007)

Ich sehe da leider nur ein schwarzes Applet. Ich kann alles mögliche einstellen und das Ding scheint auch zu rechnen (mein Rechner ist jedenfalls platt), aber der Kasten unten links mit der Scrollbar ist leer, das Applet bleibt schwarz, und der Kasten rechts daneben erschließt sich mir auch nicht. Ich kann mir da irgendwelche Koordinaten anzeigen lassen, aber was mache ich damit? Ich benutze firefox-2.0 unter Linux. Gruß, -- Sdo 19:23, 10. Jan. 2007 (CET)

Hast du vorher auf den Setup-Button gedrückt? Dann werden in dem Schwarzen Fenster die Städte gesetzt und du siehst auch den Graphen und die Logdaten. Christoph

Nathraq--Nathraq 11:03, 8. Mär. 2008 (CET)

Auch ich hab noch einen netten Link http://www.math.tu-clausthal.de/Arbeitsgruppen/Stochastische-Optimierung/tspapplet/applet.html Wäre dieses Lösungsansatz des Problems nicht auch erwähnenswert?

Wird schon erwähnt, unter Metaheuristiken. Ameisenalgorithmen und Simulated Annealing sind halt zwei von vielen metaheuristischen Verfahren. -- Sdo 15:24, 8. Mär. 2008 (CET)

Buch von 1832

Das Werk von 1832 wird immer wieder als fruehe Quelle zum TSP angeführt. Ich habe mich einmal hindurchgequält. Man erfährt allerhand über das Leben eines "Commis-Voyeurs", auch bei großzügiger Interpretation läßt sich jedoch das TSP nicht einmal in Ansätzen identifizieren. -- (nicht signierter Beitrag von 80.143.186.8 (Diskussion) 21:58, 6. Feb. 2007)

Diesen Teil habe ich aus einer früheren Version des Artikels übernommen, aber ich habe das Buch nicht gelesen. Wo um Himmels willen hast Du das Buch aufgetrieben? Gibt es das irgendwo eingescannt online? Dann würde ich da gerne mal reingucken. -- Sdo 21:01, 7. Feb. 2007 (CET)

travelling hat 2 l

das ist ganz am anfang falsch geschrieben (Der vorstehende, nicht signierte Beitrag stammt von 85.3.1.118 (Diskussion • Beiträge) 07:10, 2. Mär. 2007) --cliffhanger Beschweren? Bewerten! 08:55, 2. Mär. 2007 (CET)

Je nachdem, welches Englisch (british/american) man benutzt. Wir haben uns für die amerikanische Variante entschieden, das korrespondiert besser mit der Literatur. --Scherben 10:10, 2. Mär. 2007 (CET)

weitere dualheuristiken

- ein minimaler 1-baum liefert ebenfalls eine untere schranke für eine tour (da natürlich jede tour auch ein 1-baum ist). ein 1-baum kann durch einen greedy-algorithmus bestimmt werden, d.h. die laufzeit ist identisch mit der laufzeit zur bestimmung eines MST. außerdem ist die so gefundene schranke besser als die schranken der MST-Heuristik oder n-kleinsten kanten-heuristik. (def. 1-baum: aufspannender baum zwischen den knoten {2,...,n} + 2 kanten die mit dem knoten 1 inzidieren)

- eine weitere schranke liefert ein minimales perfektes 2-Matching (für das symmetrische tsp-> laufzeit O(n³)) bzw. das Zuordnungsproblem (für das asymmetrische TSP). (def. (perfektes) 2-Matching: Menge von kanten, so dass jeder knoten auf (genau) 2 kanten liegt.)

-- (nicht signierter Beitrag von 88.73.112.70 (Diskussion) 13:40, 31. Mär. 2007)

Danke für die Hinweise – ich habe sie gerade in den Artikel eingebaut. -- Sdo 01:05, 8. Apr. 2007 (CEST)

Verwendung von Math-Tags im Fließtext

Die HTML-Tags an Stellen, so es gerade noch Möglich ist sieht nicht aufgesetzt aus und zerschiesst nicht das Gesamtbild. Beide setzen kenntnise von HTML bzw MATH-Attributen voraus. Nun stellt sich mal die Frage, ob man an jeder Stelle wo ein x_index, was nur ansatzweise mathematisch aussieht, gleich zu Kanonen wie TeX-Werkzeugen zugreifen muss? --Andromedus 17:50, 27. Jun. 2007 (CEST)

Muss man nicht, nur die meisten Formeln sehen halt einfach besser aus... Dein (n-1)!/2 würde ich z. B. sofort wieder durch den entsprechenden tex-code ersetzen. --Scherben 18:41, 27. Jun. 2007 (CEST)

Ack Scherben. Es ist typographischer Standard, Formeln und Variablen kursiv zu setzen, weil es einfach besser aussieht. Dieses Kursivsetzen mit TeX zu machen statt mit HTML-Tags, hat den Vorteil, dass das Spacing auf jeden Fall ordentlich angepasst wird, während es bei HTML dem Browser überlassen wird und zumindest im firefox oft sehr bescheiden aussieht. Dazu kommt, dass so etwas wie R^m₊ im Quelltext unlesbar ist, im Gegensatz zu <math>R^m_+</math>. -- Sdo 19:02, 27. Jun. 2007 (CEST)

ja, gefällt mir auch nicht so recht, aber kursiv sieht es noch blöder aus im HTML .. in TeX allerdings auch nicht viel besser. Wenn es hier nen Aufstand gibt, mach ich es natürlich wieder rückgängig --Andromedus 22:22, 27. Jun. 2007 (CEST)

Es herrscht doch meines Wissens eine Übereinkunft, in Mathematik-Artikeln TeX zu verwenden (siehe Portal:Mathematik/Projekt). --Stefan Birkner 22:43, 27. Jun. 2007 (CEST)

Nicht nur in Mathematik-Artikeln. Eigentlich sollten alle Formeln mit TeX gesetzt werden. Eine XML-basierte Markup-Sprache wie MathML oder sowas wäre IMHO zwar sinnvoller, aber hier bei Mediawiki hat man sich eben für TeX entschieden. Leider. :-/ --RokerHRO 11:45, 28. Jun. 2007 (CEST)

Globale Verfahren

Kann mir jemand das globale Verfahren erklären, das da gerade neu eingefügt wurde? Es klingt irgendwie nach einer Greedy-Heuristik, aber mir ist noch etwas unklar, was da genau passiert. Anscheinend wird erstmal zu jedem Knoten die kürzeste inzidente Kante gesucht. Die längste davon wird in die Tour aufgenommen. Dieses Verfahren wird unter Vermeidung von Subtouren iteriert. Warum wird die längste der kürzesten Kanten genommen? Wenn das keiner genauer erklären kann, würde ich den Abschnitt erstmal zumindest auskommentieren, weil er dann anscheinend nur eine von beliebig vielen Frickelheuristiken beschreibt. Genausogut könnte ich auch Kanten zufällig oder nach irgendwelchen anderen abstrusen Kriterien auswählen und mir daraus eine Tour basteln. Warum soll die beschriebene Variante besser sein? -- Sdo 01:02, 19. Sep. 2007 (CEST)

Mach's ruhig erstmal so. Ich habe den einfügenden Person schon einen Kommentar auf ihrer Disku hinterlassen, dass man üblicherweise Änderungen dieses Umfangs vorher andiskutieren sollte. Richtig verstehen tue ich's übrigens auch nicht. --Scherben 01:17, 19. Sep. 2007 (CEST)

Hallo Tobias, ich habe den Abschnitt vorerst wieder auskommentiert. Das ist nicht persönlich gemeint, aber angesichts der Länge des Artikels und der Unzahl an existierenden TSP-Heuristiken können wir im Artikel nur einen kleinen Teil davon berücksichtigen. Die jetzt im Artikel beschriebenen Heuristiken sind entweder sehr bekannt und werden von vielen genutzt, oder sie haben eine Gütegarantie. Ich sehe bei deiner Heuristik momentan weder das eine noch das andere, noch, dass sie aus irgendeinem anderen Grund theoretisch oder praktisch besonders gut sein soll. Zumindest eines dieser Kriterien sollte für eine Aufnahme in den Artikel erfüllt sein. Was mir auch noch unklar ist: (1) Warum wird die längste der kürzesten Kanten genommen? Warum soll das gut sein? (2) Meinst du wirklich Symmetrien oder sprichst du von dem Fall, das es zwei kürzeste Kanten der gleichen längsten Länge gibt, so dass man sich entscheiden muss, welche man nimmt? Gruß, -- Sdo 13:36, 19. Sep. 2007 (CEST)

(n − 1)! / 2

n-1 ist defintiv falsch ich, es sind ja 2 Rundreisen von jeder dieser 3 Städte möglich. Z.B. von Berlin als Startpunkt aus entweder zuerst nach Potsdam , dann nach München und zurück nach Berlin , oder erst nach München , dann nach Potsdam und zurück nach Berlin. (mit kürzer oder länger hat's gar nix zu tun) Die Teilung durch 2 ergibt dann e i n e gleiche , 'symetrische' Streckenlänge (vorausgesetzt es handelt sich um ideale gleiche Strecken, was in der Theorie ja der Fall ist) . Im Übrigen: bei 2 Städten ginge dann nur noch 0,5 Rundreise ..

Kann mir mal jemadn diese Formel erklären? Demnach hätte ich bei 3 Städten doch nur eine möglichkeit zu reisen. Reise ich aber z.B. Zwischen Potsdam, Berlin und München so ist die Variante

Berlin-Potsdam-München

doch offensichtlich kürzer als

Berlin-München-Potsdam. Wie ist die Formel also zu verstehen? --E-qual !!! 02:57, 4. Dez. 2007 (CET)

Es geht um Rundreisen. Und Berlin-Potsdam-München-Berlin hat dieselbe Länge wie Berlin-München-Potsdam-Berlin. --Scherben 06:17, 4. Dez. 2007 (CET)

---

Exponentielles Wachstum?

Zu der Formel (n − 1)! / 2 hätt ich auch noch ne Frage! Im Artikel steht zur Komplexität, dass die Größe des Suchraums (also der möglichen Wege) exponentiell von der Anzahl der Städte abhängt. Aber eine Fakultät-Fkt. wächst doch schneller als eine Exponentialfkt.! Also ist die Aussage doch falsch, oder?

n! = n*(n-1)*(n-2)*...*3*2*1 < n*n*...*n (mit n Faktoren) = n^n für alle n>1, also n! < n^n, und Letzteres ist ja eine Exponentialfunktion--Lizziemcguire 13:18, 4. Mär. 2008 (CET)

Die Fkt. f(n)=n^n, welche du hier anbringst, habe ich noch nie gesehen, aber es ist keine Exp.fkt.! Es ist wohl eher eine Kombination aus Potenzfkt. und Exp.fkt.! Denn die Exp.fkt hat die Form: f(n)=a^n und nicht f(n)=n^n !!!

Was ich sagen wollte ist: Wenn man z.B. den Grenzwert der Fkt. f(n)= "Fakultät geteilt durch Exp.fkt." für n gegen Unendlich,

also n-->∞ f(n)=n!/(a^n) a>0 bildet,

dann geht dieser Ausdruck f(n) gegen Unendlich. Das liegt daran, dass die Fakultät ein "schnelleres" Wachstum hat als die Exp.fkt! Und da die Anzahl der Möglichkeiten für den Handlungsreisenden durch die Formel (n − 1)! / 2 gegeben sind, ist es doch falsch von Exponentiellem Wachstum zu sprechen, da die Anzahl der Möglichkeiten noch schneller wächst!!!???

Ja, im Prinzip hast Du schon recht. Die Fakultätsfunktion wächst schneller als exponentiell. Aber das spielt aus komplexitätstheoretischer Sicht nicht mehr wirklich eine Rolle (und aus praktischer Sicht schon gar nicht). Entscheidend ist da eigentlich nur, ob der Aufwand polynomial oder pseudopolynomial wächst oder mindestens exponentiell. -- Sdo 01:23, 5. Mär. 2008 (CET)

Na gut! Falsch ist die Aussage trotzdem. Was bedeutet denn pseudopolynomial?

Siehe Pseudopolynomiell. Ein Algorithmus ist pseudopolynomial, wenn er polynomial in der unär kodierten Eingabelänge ist und nicht in der binär kodierten Eingabelänge, wie es für Polynomialität erforderlich wäre. Beispiel: der Aufwand von dynamischer Programmierung beim Rucksackproblem ist linear in der Rucksackkapazität. Für Polynomialität müsste der Aufwand polynomial im Logarithmus der Kapazität sein. -- Sdo 23:34, 6. Mär. 2008 (CET)

Trotzdem standen da unter "Algorithmische Komplexität" die Sätze <quote> Da dem Handlungsreisenden in jedem Schritt die Städte zur Auswahl stehen, die er noch nicht besucht hat, gibt es (n-1)! mögliche Touren für ein asymmetrisches und (n − 1)! / 2 Touren für ein symmetrisches TSP. Die Größe des Suchraums hängt also exponentiell von der Anzahl der Städte ab. </quote> Aber der Suchraum ist doch (n-1)! groß, und das ist eine überexponentielle (nämlich fakultative) Abhängigkeit. Also habe ich das abgeändert.

1 Million Dollar

Wer das Problem des Handlungsreisenden löst, bekommt von der amerikanischen Clay Foundation ein Preisgeld von einer Million Dollar. http://www.sueddeutsche.de/wissen/625/305593/text/ (nicht signierter Beitrag von 91.67.150.32 (Diskussion) 11:51, 9. Aug. 2008)

Na ja, das ist im SZ-Artikel arg verkürzt dargestellt. Lösen kann man das TSP aus praktischer Sicht jetzt schon, solange die Zahl der Städte in vernünftigen Größenordnungen bleibt. Die Million Dollar gibt es für den Beweis, das $P=NP$ oder $P\neq NP$ gilt. Ersteres könnte man zeigen, indem man einen polynomialen Algorithmus für ein beliebiges NP-schweres Problem angibt. Ein Beispiel für solche Probleme ist das TSP. -- Sdo 09:25, 11. Aug. 2008 (CEST)

Formulierung als ganzzahliges Problem

Bezüglich Formel (3) stelle ich die Frage, ob "x_ij e {0;1}" notwendig ist. (Wenn ja, gerne erläutern. Mein Eindruck: Überflüssig, denn dass x_ij e {0;1}, wurde zuvor festgelegt, oder? Dass alle i,j durchlaufen werden, ist klar aufgrund der Summenzeichenunterschriften.)

Der Satz "Man kann zeigen, dass die meisten der Bedingungen (1) und (2) Facetten des TSP-Polytops definieren, d. h., dass sie zu den besten linearen Ungleichungen gehören, die es zur Beschreibung einer Tour geben kann." stößt mir auf. Die ersten beiden Teilsätze ("Man kann... definieren") sind kaum verständlich. Muss man erst unter "Facetten" nachschlagen, um zu wissen, dass es sich hierbei um Seitenflächen eines Würfel-Gebildes handelt? Das "TSP-Polytop" immerhin wird später anschaulich erklärt. Der folgende Satz beginnt mit "d.h.", erklärt aber weder das Vorige, noch wird mir ein kausaler Zusammenhang klar. Kann man diesen Zusammenhang erläutern? (Wann sind die Ungleichungen "gut", wann "schlecht"? Warum sind solche gut, die Seitenflächen definieren? Was wären andere Ungleichungen, die für Touren notwendig gelten müssen?) Aus meiner Sicht wäre ein Einbau dieses Sachverhaltes - mit mehr Erklärung - im Abschnitt zum Polytop sinnvoll.

P.S.: @Praxisbeispiele -> Das TSP kommt mir von meinen todo-Listen sehr bekannt vor, inkl. Zeitfenstern. Zur Post bis 17.30 Uhr, Wäsche raus (Keller) möglichst bald nach Spülstopp, zum Markt vor 12.30 Uhr, Brot backen lassen (Wohnung, da sein zur Entnahme), "Rundreise" zu verschiedenen Läden... -- (nicht signierter Beitrag von Seakaye (Diskussion | Beiträge) 00:54, 14. Aug. 2008)

Hallo Seakaye, danke für Deine Anregungen. Dass die Variablen binär sein sollen, steht zwar auch vorher im Text, sollte aber der Übersicht halber auch nochmal in (3) stehen, damit die Definition des Problems stimmt. Sonst stünde in (3) da nur die LP-Relaxierung, das wäre verwirrend. Das mit dem Polytop und den Facetten habe ich jetzt etwas genauer erklärt; ist es so verständlicher? Polyedertheorie hier allgemein zu erklären, sprengt aber den Rahmen des Artikels. Der Begriff gute Ungleichung ist relativ. Die Ungleichung $x\geq 2$ ist besser als die Ungleichung $x\geq 1$ in dem Sinne, dass die erste Ungleichung die zweite dominiert, d.h., alle Punkte $x$, die die erste Ungleichung erfüllen, erfüllen auch die zweite. Das wird weiter unten im Abschnitt zu Branch-and-Cut zumindest ansatzweise erklärt. Zu Deinem Praxisbeispiel: ja, das kann man als TSP mit Zeitfenstern sehen. Ich würde es allerdings eher als Scheduling-Problem betrachten: es gibt zu erledigende Aufgaben, die eine bestimmte Zeit dauern, die wahrscheinlich nicht in beliebiger Reihenfolge ablaufen dürfen (das ist der wesentliche Unterschied zum TSP), und zwischen zwei Aufgaben muss eine bestimmte Zeit gewartet werden (Reisezeit). Gruß, Sdo 10:19, 14. Aug. 2008 (CEST)

Mir fehlt zur Lösung des Traveling Sales Man Problems die Lagrange Relaxation mit der Ascent Methode. Wäre es nicht sinnvoll diese einzufügen?

MfG

Verteiltes Rechnen

moien, ich bin ja kein fachmann in diesen dingen, und deswegen wollte ich erst hier schreiben, was ich wohl ergänzen würde,bevor ich gesteinigt werde ;). wenn ihr verteiltes rechnen kennt, zb bei seti@home und dem BOINC client, da gab es auch mal ein prejekt zum TSP [6]. ich würde also etwas zur berechnung des TSP durch verteiltes rechnen einfügen, sofern ihr mich lasst und das hier gebraucht werden kann. grüße, --Andreas -horn- Hornig 11:27, 7. Jul. 2009 (CEST)

Schreib das doch erst hier in der Diskussion, dann können die Moderatoren sagen, ob es passt oder nicht!

-- H007A 15:56, 16. Jul. 2009 (CEST)

Zur Geschichte...

...wird hier von idR nicht inkompetenter Stelle weiter ausgeführt - vielleicht eine Ergänzung? --NB > ?! > +/- 18:39, 27. Jul. 2009 (CEST)

In Graham, Grötschel, Lovasz: Handbook of combinatorics wird geschrieben, dass eine rudimentäre Beschreibung Problem des Handlungsreisenden zum ersten Mal 1831 erwähnt wird:

Voigt, B.E
[1831] Der Handtunsvreisende, wie er sein soll und was er zu thun hat,
um Aufträge zu erhalten und einer glücklichen Erfolgs in seiner Geschäften
gewiss zu sein (von einem alten Commis-Voyageur; Ilmenau). Reprinted 1981 (Schramm, Kiel)

Kann man vieleicht ja im Artikel einbauen...--Flegmon 19:20, 24. Mai 2010 (CEST)

Berechnung eines Hamilton-Zyklus mit drei Knoten durch Bakterien

JBiolEng.org heise.de

Kann das einer einbauen? (nicht signierter Beitrag von In4matic (Diskussion | Beiträge) NB > ?! > +/- 20:29, 27. Jul. 2009 (CEST))

Bitte

a) neue Beiträge unten anfügen,

b) letzte Beiträge lesen (der Artikel ist in meinem letzten Absatz bereits verlinkt und hätte hinsichtlich der Anregung nur ergänzt werden müssen) und

c) das Signieren nicht vergessen

In jedem Fall aber noch einen schönen Abend ;-)... --NB > ?! > +/- 20:29, 27. Jul. 2009 (CEST)

Ich habe den Link wieder entfernt. Der o.a. Artikel ist für den Themenkomplex TSP meiner Meinung nach vollkommen irrelevant, da gerade einmal ein Problem mit 3 Städten gelöst wurde. Der Artikel ist wenn überhaupt nur für Biocomputer o.ä. interessant.  — Felix Reimann 15:30, 28. Jul. 2009 (CEST)

Oder, wie im Absatz hierüber angedeutet, als Ergänzung der Geschichte des Problems... ;-) --NB > ?! > +/- 20:48, 28. Jul. 2009 (CEST)

Formulierung_als_ganzzahliges_lineares_Programm

Bei der Formulierung als ganzzahliges lineares Programm ist einiges schiefgelaufen. So ist in einem ungerichtete Graphen (der ja vorliegt) die Kante {i,j} gleich der Kante {j,i}, da sie zweielementige Teilmengen der Knotenmenge darstellen und Mengen gleich sind, wenn sie die gleichen Elemente enthalten. Demzufolge muss man entweder jeder Kante {i,j} zwei Variablen x_i,j = x_j,i zuordnen oder man beschränkt sich auf die Variablen x_i,j mit i< j oder man definiert die Variablen x mit der Menge aller Kanten als Indexmenge, also x_{i,j}. Demzufolge muss die Summation über j aus V\{i} x_i,j ggf. geändert werden. In der vorliegenden Fassung wäre in einem vollständigen Graphen |V| = 5 bei gleichmäßiger Anordnung der Knoten im Kreis und c(e) = 1 für alle e in E zum Beispiel eine Tour, in der jeder Knoten zweimal besucht wird, zulässig. In Ermangelung einer Grafik bestehe diese Tour aus dem Weg "außen" um die Knoten verknüpft mit dem Weg über ein Pentagramm "innen". Da x_i,j != x_j,i erlaubt ist und alle anderen Nebenbedingungen erfüllt sind, erfüllt diese Tour alle Nebenbedingungen.

Die in der Formulierung einfachste Möglichkeit bestünde darin, x_i,j = x_j,i zu definieren, wodurch pro Kante wieder effektiv genau eine Entscheidungsvariable existiert. (nicht signierter Beitrag von 129.217.233.46 (Diskussion | Beiträge) 14:17, 25. Nov. 2009 (CET))

Kann es sein, dass dein Denkfehler darin liegt, dass du i,j als Indizes verstehst, obwohl sie als Knotenplatzhalter erklärt werden? Siehe Formullierung „für jede Kante {i,j} erklärt man ...“--goiken 18:01, 25. Feb. 2010 (CET)

Was genau soll ein Knotenplatzhalter sein? Sowohl i als auch j werden als Element der Knotenmenge V definiert, somit sind sie Indizes der Indexmenge V. Wichtig ist, dass Indizes an sich geordnet sind und nicht per se einer gewissen Symmetrie unterworfen sind. Wenn man also zu einer Kante {i,j} eine Variable erklären will, so sollte auch die Kante der Index der Variable sein (also x_{i,j}), wählt man die beiden "Kantenbestandteile", also Knoten, i und j, so kommt es zu dem von mir beschriebenen Effekt, dass nicht jeder Kante {i,j} genau eine Variable x_ij zugeordnet wird. Ein kleines Beispiel: Der Kante {1,2} wäre jetzt nach Obigem die Variable x_1,2 zugeordnet. Allerdings ist die Kante {1,2} = {2,1}. Demzufolge wäre die zugeordnete Variable x_2,1. Da bei Indizes die Reihenfolge wichtig ist (!), geht an dieser Stelle die Eindeutigkeit der Zuordnung im mathematischen Modell verloren und muss durch Fordern der Symmetrie x_ij = x_ji (oder indem man direkt die Kantenmenge als Indexmenge wählt -> x_{i,j}) wiederhergestellt werden.

--129.217.233.46 13:04, 20. Apr. 2010 (CEST)

Entschuldigung: Dass du geantwortet hast, ist mir entgangen…

$x_{ij}=1\Leftrightarrow _{\text{Def}}\{i,j\}{\text{ in der Tour}}\Leftrightarrow \{j,i\}{\text{ in der Tour}}\Leftrightarrow _{\text{Def}}1=x_{ji}$

Die Symmetrie von $x_{ij}=x_{ji}$ im Fall eines ungerichteten Graphen ergibt sich aus dieser Definition doch in ganz natürlicher Art und Weise, denn $\{i,j\}=\{j,i\}$. Ich verstehe wirklich nicht, wo das Problem liegt.

Man kann zwar streng genommen von „zwei Variablen“ sprechen; Sie gleichen sich aber in ihren Werten. Und noch mal zu dem „Gegenbeispiel“ aus dem ersten Beitrag: (das ich erst jetzt verstehe) Betrachte den $K_{5}$ und numeriere die Vertices im Urzeigersinn. Betrachte dann den Weg „Fünfeck außen + Stern innen“. Dann gilt: $1=x_{21}=\underbrace {x_{31}} _{=x_{13}}=x_{41}=\underbrace {x_{51}} _{=x_{15}}$. Durch Summation sieht man, dass die Bedingung (1) aus dem Artikel verletzt ist.--goiken 13:38, 4. Jul. 2011 (CEST)

Das Problem ist allerdings, dass $x_{ij}=x_{ji}$ nirgends im mathematischen Modell steht. -- Exxotiker 14:06, 4. Jul. 2011 (CEST)

Ja… Weil das im Gerichteten Fall direkt aus der Definition folgt. Meinethalben können wir das ãber auch explizit hinschreiben: Nur die neue Notation $x_{\{i,j\}}$ ist eher unglücklich.--goiken 14:52, 4. Jul. 2011 (CEST)

Die Definition ist das eine, das mathematische Modell das andere. In (3) wird explizit nur die Zielfunktion unter den Nebenbedingungen (1) und (2) minimiert. Dass die Formulierung in der jetzigen Form vielleicht nicht schön ist gebe ich zu, bei ein wenig Muße werde ich das ganze vielleicht nochmal anpassen an $x_{ij}=x_{ji}$, wobei dann noch ggf. sprachliche Änderungen hinzukommen ("Für jede Kante $\{i,j\}$ wird eine binäre Variable $x_{i,j}\in \{0,1\}$ eingeführt"... u. ä. (man mag anmerken, dass mit "eine" im Allgemeinen "mindestens eine" und nicht "genau eine" gemeint ist, allerdings lädt die Formulierung zu Missverständnissen ein, wo doch offensichtlich -- siehe Dein Kommentar -- zwei Variablen eingeführt werden)). -- Exxotiker 15:11, 4. Jul. 2011 (CEST)

Ich finde es nicht offensichtlich, dass zwei Variablen eingeführt werden, schließlich ist $\{s,t\}=\{t,s\}=\{s,s,t\}=\{t,s,s\}=\ldots$. Wenn man genauer sagt, dass genau eine Variable für jede Kante eingeführt wird, ist die ursprüngliche Schreibweise doch wieder in Ordnung? --Zahnradzacken 15:22, 4. Jul. 2011 (CEST)

Dann stellt sich wiederum die Frage, welche Variable eingeführt wurde, $x_{ij}$ oder $x_{ji}$. Da man aber in den Summen in (2) sowohl über $x_{ij}$ als auch (in einer anderen Nebenbedingung) über $x_{ji}$ summiert, müssen bei dieser Formulierung beide eingeführt werden. -- Exxotiker 15:38, 4. Jul. 2011 (CEST)

Ich meinte man könne zwei (und meinethalben auch beliebig viele) Variablen einführen. Weil die sich aber im ungerichteten Fall alle identisch verhalten wäre das ziemlich sinnlos. --goiken

Genau aus diesem Grund ist es in der Literatur üblich, in solchen Fällen nur $x_{ij}$ für $i<j$ zu definieren (siehe ersten Post). Genau eine binäre Variable $x_{ij}$ für jede Kante $\{i,j\}$ lässt sich nicht definieren. -- Exxotiker 15:38, 4. Jul. 2011 (CEST)

unscharf formulierter Satz

Hallo, ist der letzte Satz aus dem 2. Absatz "In vielen praktischen Anwendungen müssen zudem Zusatzbedingungen wie Zeitfenster oder eingeschränkte Ressourcen beachtet werden, was die Lösung des Problems erheblich erschwert." nicht zu ungenau formuliert? Wie ich die NPC Probleme aus der Uni kenne, kann man per polynomieler Reduktion leicht zeigen das das allg. TSP Problem nicht schwerer ist als wenn noch andere Resourcenbeschränkungen gefordert werden.

Gruß Robert Eikermann -- Tr3bor 20:15, 25. Feb. 2010 (CET)

Link

Sollte hier nicht der Link http://zrp.tournament.de/ aufgenommen werden? Dies ist eine kostenlose Routenoptimierung. Frits 13:56, 28. Feb. 2010 (CET)

salesperson

[7] --goiken 03:27, 20. Mär. 2010 (CET)

Merci. War mir echt nicht klar. --Scherben 09:57, 20. Mär. 2010 (CET)

Wrong map

Sorry, I cannot speak German. But the opening map (TSP Deutschland 3.png) is wrong. It shows only 14 cities, not 15. Dortmund is missing. --Fioravante Patrone 15:55, 14. Mär. 2011 (CET)

It's not explicitly marked, but the route's probably correct nonetheless. Dortmund is just on the way between Düsseldorf and Hannover. I suppose there just wasn't enough space left, to place a label. --~~

Two comments (still in English, sorry)

1.The original author of the map has said on en:wiki that he does not know whether the marked tour is optimal (see [8])

2. I don't see why one, interested in TSP, should know where Dortmund is, to understand the opening example on TSP. Moreover, there is enough room to place it (see again en:wiki [9] where I give an external link temporarily hosting a slight modification of the map, which includes Dortmund [10]. I would have uploaded this map, or an improved version of it, but I don't think it is the case, given what I mentioned in point 1. here. --Fioravante Patrone 13:58, 25. Mär. 2011 (CET)

Berlin Hamburg München Köln Franfurt am Main Stuttgart Düsseldorf Dortmund Essen Bremen Hannover Leipzig Dresden Nürnberg Duisburg

According to this applet this is the fastest tour for the 15 biggest cities. Feel free to make a nice map off it. I don't feel it is too important though. It is practically impossible for a human to prove the correctness anyways… so nobody would really notice. The main purpose of the map, as i see it, is only to clarify the basic concepts of the problem, i.e. what is meant by a "tour", "optimal tour" etc. --goiken 14:24, 25. Mär. 2011 (CET)

… Seems to be the same result as showed here --goiken 14:30, 25. Mär. 2011 (CET)

5.5 Biologie / TSP und Hummeln

Ich kann in Ref. [7] (Lihoreau et. al) keine Hinweise auf die besonders effiziente Lösung des Problems durch Hummeln finden. Siehe dazu auch http://animalwise.org/2011/07/14/did-you-hear-the-one-about-the-traveling-salesman-and-the-bumblebee/

Now, in their research paper5, the UK team did note that the bees’ search to find the shortest path among flowers is analogous to the traveling salesman problem, and did state that “Our findings suggest that traplining animals can find (or approach) optimal solutions to dynamic traveling salesman problems (variations of the classic problem where availability of sites changes over time) simply by adjusting their routes by trial and error in response to environmental changes.” These observations are, however, just a tad less dramatic than the “triumph over supercomputers” celebrated in the popular media reports on the research. (nicht signierter Beitrag von Mahafner (Diskussion | Beiträge) 20:51, 13. Jun. 2012 (CEST))

hier was zu Vögeln. --Edith Wahr (Diskussion) 17:40, 19. Nov. 2012 (CET)

Ich habe die Aussage "... das Problem des Handlungsreisenden besser und effizienter zu lösen, als dies mit den bislang bekannten mathematischen Computerverfahren möglich ist." entfernt, da es so falsch ist. Mathematische Verfahren sind beweisbar optimal, es geht also nicht besser. Bzgl. Effizienz/Laufzeit sind die im Paper betrachteten Probleme extrem klein und damit einfach (für Computer). (nicht signierter Beitrag von 132.230.166.72 (Diskussion) 15:35, 24. Feb. 2013 (CET))

Es wird daher mit sehr großer Sicherheit angenommen, dass die Worst-case-Laufzeit jedes deterministischen Algorithmus, der für dieses Problem stets optimale Lösungen liefert, im besten Fall exponentiell von der Anzahl der Städte abhängt.

Die Aussage entspricht nicht dem Stand des aktuellen Wissens und von Sicherheit zu reden ist blödsinn, denn entweder ist es so, oder nicht. Aber vielleicht gibt es ja jemand, der das behauptet. Man sollte dafür einen Beleg ergänzen und dies als Meinung schildern. Ich habe es mal im Artikel entsprechend markiert.--Jocme (Diskussion) 11:35, 18. Sep. 2013 (CEST)

Hab es jetzt mal vorsichtiger und klarer formuliert. Reicht dir das so? --Andreschulz (Diskussion) 12:25, 19. Sep. 2013 (CEST)

Nicht nur vorsichtiger, sondern richtig! Sehr schön. Den Quellennachweis kann man da von mir aus wieder rausnehmen, wenn auch etwas mehr Fußnoten dem langen Artikel sicher gut tun würden.--Jocme (Diskussion) 15:20, 19. Sep. 2013 (CEST)

Da Stimme ich zu. Gerade für einen Exzellenten Artikel liegt hier doch einiges im Argen. Vielleicht finde ich ja mal die Zeit .... --Andreschulz (Diskussion) 15:59, 19. Sep. 2013 (CEST)

Abschnitt Metaheuristiken

Ein schöner Artikel!

Allerdings wird im Abschnitt Metaheuristik lediglich erläutert, was man sich unter einer solchen vorstellen soll. Es wird kein Bezug zum Salesman gemacht. Vielleicht kann ja jemand, der da ein paar Beispiele parat hat, da nachbessern. -Schwatzwutz !?! 10:31, 22. Sep. 2013 (CEST)

Definition/Problemformulierung

Ich habe dort die m.E. irritierenden Worte "nach Rückkehr des Handlungsreisenden" (oder so ähnlich) gestrichen. Selbstverständliches zu erwähnen irritiert, zumal es zusätzlich irritirend formuliert war: Das Wort "nach" scheint hier plötzlich eine zeitliche Komponente anzudeuten, während es hier um REINE Strecken- bzw. Längenoptimierungen geht. Mir ist die Doppelbedeutung des Wortes "nach" bewusst, also dass sie ebenfalls rein räumlich verstanden werden kann. Aber genau diese Irritation kann man auch einfach unterlassen, denn dass der Handlungsreisende NICHT letztlich nach Hause will, sagt ja niemand. (nicht signierter Beitrag von 88.130.34.24 (Diskussion) 23:30, 23. Aug. 2015 (CEST))

Die Bemerkung ist überhaupt nicht selbstverständlich. Mann kan ja auch alle Orte bereisen ohne zum Ausgangzort zurückzukehren. Eine solche Reise wird auch kürzer sein. Das Wort "nach" deutet eine temporale Abhängigkeit ab. So wie es jetzt im Text steht, ist es die Beschreibung definitiv falsch. --Andreschulz (Diskussion) 16:28, 26. Aug. 2015 (CEST)

NP vollständig

Im Artikel steht, dass TSP NP-vollständig ist, dies ist aber gar nicht bekannt. Bekannt ist nur, dass TSP NP-hard ist.

Siehe: englischen wiki-Eintrag oder https://www.ibm.com/developerworks/community/blogs/jfp/entry/no_the_tsp_isn_t_np_complete?lang=en (nicht signierter Beitrag von 194.230.159.159 (Diskussion) 15:15, 28. Apr. 2016 (CEST))

Nun ja, die Entscheidungsversion "Gibt es eine Tour der Länge <= x?" ist natürlich NP-vollständig. Das abgeleitete Optimierungsproblem "Wie lang ist die kürzeste Tour" ist nur NP-schwer (NP-schwer ist ein besserer Ausdruck als NP-hard/hart), da nach Definition nur Entscheidungsprobleme NP-vollständig sein können. Im einleitenden Teil würde ich auf diesen eher subtilen Unterschied nicht eingehen wollen und den Text so lassen. --Andreschulz (Diskussion) 19:02, 28. Apr. 2016 (CEST)

Im einleitenden Teil wird das TSP aber eindeutig und ausschließlich als Optimierungsproblem definiert. Daher würde ich hier nicht Aussagen über das noch nicht beschriebene Entscheidungsproblem tätigen, um Verwechslungen zu vermeiden. Der Satz sollte an dieser Stelle gestrichen werden oder die Definition als Optimierungsproblem geändert werden. --KNSTB (Diskussion) 00:17, 12. Sep. 2018 (CEST)

Einheitliche Schreibweise von Travelling/Traveling

In dem Artikel wird die englische Bezeichnung des "Problem des Handlungsreisenden" teilweise mit "Travelling Salesman Problem" und teilweise mit "Traveling Salesman Problem" übersetzt. Dabei wäre eine einheitliche Übersetzung im gesamten Artikel besser. (nicht signierter Beitrag von Alexxx.ander.k (Diskussion | Beiträge) 09:35, 11. Jan. 2017 (CET))

Das ist nicht ganz so einfach. Selbst in der englischen WP ist es nicht einheitlich geschrieben: in WP selber fast überall mit 2 L (z.B. im Lemma: https://en.wikipedia.org/wiki/Travelling_salesman_problem), aber in der zitierten Literatur überwiegend mit einem L. Das ist dort aber ebenfalls diskutiert worden: https://en.wikipedia.org/wiki/Talk:Travelling_salesman_problem#Spelling Es ist also British vs. American Englisch. Dort wird noch dies angegeben: http://www.math.uwaterloo.ca/tsp/history/travelling.html was zu einem einzelnen L rät, weil historisch korrekt.

Und nu? weiß auch nicht recht. --H.Marxen (Diskussion) 16:03, 11. Jan. 2017 (CET)

Eingangsbild 15 Städte

"Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen"

Hm, es gibt 15!=1.307.674.368.000 Möglichkeiten, die Städte linear anzuordnen. Wenn ich das als geschlossenen Weg betrachte und mich die Wahl der Startortes nicht interessiert, sind es 14!=87.178.291.200 Wege. Wie erklärt sich die 43.589.145.600? --217.238.132.205 09:53, 19. Jun. 2022 (CEST)

Selbst geklärt: 14!/2 wenn mich auch nicht interessiert, in welche Richtung ich einen geschlossenen Weg durchlaufe. Vielleicht sollte man 14!/2 einbauen? --217.238.132.205 10:05, 19. Jun. 2022 (CEST)

"Praktische Grenzen der Berechenbarkeit" Stand veraltet

Eben zitierter William Cook hat mittlerweile deutlich größere Instanzen des TSP nachweislich optimal lösen können als hier angegeben. Hier etwa eine nachweislich kürzeste Tour durch 57.912 Sehenswürdigkeiten in den Niederlanden (https://www.math.uwaterloo.ca/tsp/nl/index.html). Ich meine, dass in seinen Videos auch von deutlich größeren Instanzen die Rede ist und werde das bei Gelegenheit noch nachreichen. Die Frage ist auch ob, "nachweislich optimal" noch gilt, wenn man zeigen kann, dass etwa eine Tour durch 100.000 Städte im worst case noch 10m kürzer sein könnte. Diese Art von Optimalitätszertifikat wird ja in Branch-and-Cut-Ansätzen berechnet --BumbleMath --BumbleMath (Diskussion) 20:52, 3. Dez. 2023 (CET)

Habe es aktualisiert. Sehr schade, dass @Sdo nicht mehr aktiv ist. Seine Beiträge zur kombinatorischen Optimierung sind Gold. --BumbleMath (Diskussion) 07:36, 16. Jan. 2024 (CET)

dass keine Station außer der ersten mehr als einmal besucht wird

Es müsste doch das Problem vereinfachen, wenn man diese Bedingung weglässt. In der Praxis schadet es ja nichts, wenn ein Reisender mehrmals einen Ort durchquert. Bei manchen Problemstellungen, etwa bei Schaltkreisen, ist diese Forderung aber wohl notwendig. Gibt es Untersuchungen, was es bedeutet, wenn man einen Ort mehrmals besucht? tsor (Diskussion) 21:20, 15. Jun. 2024 (CEST)

Der Schleimpilz zeigt, N=NP am Beispiel des Handlungsreisenden

Tja, also gibt es einen uns noch unbekannten Algorithmus,

der das Problem des Handlungsreisenden in LINEARER Zeit löst,

liebe Grüße

Dietmar

https://www.youtube.com/watch?v=TXSN0ERei50 ab 18:06 min --91.51.15.10 15:26, 30. Jun. 2024 (CEST)