Komplexitaet des Travelling Salesman Problems



  • Hi.

    Auf Wikipedia steht:

    http://en.wikipedia.org/wiki/Travelling_salesman_problem

    In the theory of computational complexity, the decision version of the TSP (where, given a length L, the task is to decide whether the graph has any tour shorter than L) belongs to the class of NP-complete problems.

    aber auch http://en.wikipedia.org/wiki/List_of_NP-complete_problems

    The problem for graphs is NP-complete if the edge lengths are assumed integers. The problem for points on the plane is NP-complete with the discretized Euclidean metric and rectilinear metric. The problem is known to be NP-hard with the (non-discretized) Euclidean metric.

    Was ist denn jetzt richtig? Ist TSP NP vollstaending oder sind nur bestimmte Varianten von TSP mit gewissen Zusatzbedingungen NP vollstaending? Wurde da vielleicht in letzter Zeit etwas veroeffentlicht, das zu dieser Diskrepanz in den unterschiedlichen Wikipedia-Artikeln fuehrt?



  • Es ist NP-vollständig, wenn die Kantengewichte Integer sind. Beide Wikipedia-Artikel stimmen in diesem Punkt überein.

    Wenn man die Knoten des Graphen in einem metrischen Raum platziert und die Kantengewichte über den Abstand zwischen den entsprechenden Knotenpaaren definiert, gibt es mehrere Möglichkeiten:

    1. Die Metrik liefert keine rationalen Zahlen, d.h. die Kantengewichte lassen sich nicht mehr als Integer darstellen.
    2. Die Metrik liefert immer rationale Zahlen, d.h. die Kantengewichte lassen sich als Integer darstellen.

    Im Fall 2) ist das Problem nicht schwieriger als NP, denn die Zusatzinformation "die Kantengewichte stammen aus einer Metrik" kann es nur einfacher machen. Zum Beispiel gilt dann die Dreiecksungleichung, die auf allgemeinen gewichteten Graphen nicht gilt.

    Im Fall 1) ist es nicht so klar, was passiert. Zum einen kann das Problem einfacher werden, weil man die Zusatzinformation "die Kanten stammen aus einer Metrik" hat. Zum anderen kann das Problem schwieriger werden, weil die Kantengewichte keine Integer mehr sind. Bei der gewöhnlichen euklidischen Metrik bist du im Fall 1).



  • Christoph schrieb:

    Es ist NP-vollständig, wenn die Kantengewichte Integer sind. Beide Wikipedia-Artikel stimmen in diesem Punkt überein.

    Hi Christoph!

    1. Danke fuer die Klarstellung.

    2. Kannst Du mich mal auf diese Einschraenkung im ersten Artikel stossen. Ich lese da vor allem die allgemeine Aussage ohne die Einschraenkung.



  • Christoph schrieb:

    Im Fall 1) ist es nicht so klar, was passiert. Zum einen kann das Problem einfacher werden, weil man die Zusatzinformation "die Kanten stammen aus einer Metrik" hat. Zum anderen kann das Problem schwieriger werden, weil die Kantengewichte keine Integer mehr sind. Bei der gewöhnlichen euklidischen Metrik bist du im Fall 1).

    Ja? Im Artikel ist von einer "diskretisierten" euklidischen Metrik die Rede.



  • Gregor schrieb:

    Christoph schrieb:

    Im Fall 1) ist es nicht so klar, was passiert. Zum einen kann das Problem einfacher werden, weil man die Zusatzinformation "die Kanten stammen aus einer Metrik" hat. Zum anderen kann das Problem schwieriger werden, weil die Kantengewichte keine Integer mehr sind. Bei der gewöhnlichen euklidischen Metrik bist du im Fall 1).

    Ja? Im Artikel ist von einer "diskretisierten" euklidischen Metrik die Rede.

    Die diskretisierte euklidische Metrik ist definiert als "zur nächsten natürlichen Zahl aufgerundeter euklidischer Abstand". Du bekommst also Integer-Kantengewichte, damit ist das Problem schonmal nicht schwieriger als NP. Es könnte aber einfacher werden, weil z.B. die Dreiecksungleichung gilt. Das ist aber anscheinend nicht der Fall.



  • Gregor schrieb:

    Christoph schrieb:

    Es ist NP-vollständig, wenn die Kantengewichte Integer sind. Beide Wikipedia-Artikel stimmen in diesem Punkt überein.

    2. Kannst Du mich mal auf diese Einschraenkung im ersten Artikel stossen. Ich lese da vor allem die allgemeine Aussage ohne die Einschraenkung.

    Dass die Kantengewichte Integer sind, kann ich im ersten Artikel nicht finden. Vielleicht ist Wikipedia hier einfach unpräzise. Das übliche NP-vollständige TSP-Problem, das ich kenne, redet von Graphen mit ganzzahligen Gewichten.



  • Christoph schrieb:

    Die diskretisierte euklidische Metrik ist definiert als "zur nächsten natürlichen Zahl aufgerundeter euklidischer Abstand". Du bekommst also Integer-Kantengewichte, damit ist das Problem schonmal nicht schwieriger als NP. Es könnte aber einfacher werden, weil z.B. die Dreiecksungleichung gilt. Das ist aber anscheinend nicht der Fall.

    AFAIK bietet einem diese Zusatzeigenschaft wenigstens Ansatzpunkte fuer entsprechende Approximationsalgorithmen. Insofern bringt es durchaus etwas. ...aber, wie Du schon sagst, nicht fuer die strikte Auslegung des eigentlichen Problems.

    ...eigentlich sehr interessant.

    Christoph schrieb:

    Dass die Kantengewichte Integer sind, kann ich im ersten Artikel nicht finden. Vielleicht ist Wikipedia hier einfach unpräzise. Das übliche NP-vollständige TSP-Problem, das ich kenne, redet von Graphen mit ganzzahligen Gewichten.

    Ja, da scheinen die Wikipedia-Artikel tatsaechlich nicht genau genug zu sein. ...ist beim deutschen Wikipedia-Artikel genauso unklar definiert.

    Christoph: Danke fuer die Klarstellung, wie es im Detail aussieht. Hast Du eigentlich ein gutes Buch oder Paper in diesem Zusammenhang?



  • Gregor schrieb:

    Hast Du eigentlich ein gutes Buch oder Paper in diesem Zusammenhang?

    Generell würde ich das Buch empfehlen, eines meiner Lieblingsfachbücher:
    Computational Complexity | ISBN: 0521424267
    Aber das hast du schon, wenn ich mich nicht irre.

    Für präzise Formulierungen von vielen NP-vollständigen Problemen inklusive Referenzen auf Papers, wo mehr zu den einzelnen Problemen steht, ist das hier gut:
    Computers and Intractability: A Guide to the Theory of NP-Completeness | ISBN: 0716710455



  • Christoph schrieb:

    Gregor schrieb:

    Hast Du eigentlich ein gutes Buch oder Paper in diesem Zusammenhang?

    Generell würde ich das Buch empfehlen, eines meiner Lieblingsfachbücher:
    Computational Complexity | ISBN: 0521424267
    Aber das hast du schon, wenn ich mich nicht irre.

    Für präzise Formulierungen von vielen NP-vollständigen Problemen inklusive Referenzen auf Papers, wo mehr zu den einzelnen Problemen steht, ist das hier gut:
    Computers and Intractability: A Guide to the Theory of NP-Completeness | ISBN: 0716710455

    Ja, das erste habe ich.

    Das zweite kenne ich nicht. Mir faellt aber auf, dass es ein recht altes Buch ist. Meinst Du, es ist trotzdem noch up-to-date und laesst keine wichtigen Aspekte aus, die vielleicht in der Zwischenzeit entdeckt wurden?



  • Das zweite Buch ist auf jeden Fall sehr gut. Es ist ein umfangreiches Kompendium von NP-schweren Problemen. Natürlich ist es bei weitem nicht vollständig. Aber es enthält mit Sicherheit die wichtigsten Probleme und sehr viele Verweise. Zumindest wenn man beweisen will, dass etwas NP-schwer ist, und man keinen Ansatz hat, dann lohnt es sich auf jeden Fall mal darin zu blättern. Den enormen Einfluss dieses Buches sieht man auch an der Zahl der Zitationen. Laut google scholar derzeit 46339 😮 Das ist schon ne Hausnummer.

    Aber zurück zum Thema NP-schwer vs. NP-vollständig. Eine Frage, die ich gerne stelle ist die Frage nach euklidischem minimalem Spannbaum. Also was ist die Komplexität folgenden Problems: Gegeben eine Menge von Punkten im R^2 (mit rationalen Koordinaten), berechne einen miminalen Spannbaum. Genauer gesagt: Ist dieses Problem in NP? -- Klar, jeder Informatiker der was auf sich hält kennt die Antwort. Mittels Kruskal-Algorithmus kann man den MST ausrechnen und damit ist das Problem in P.

    Aber jetzt kommt die große Überraschung: Es ist nichtmal klar ob das Problem in NP ist. Das obige Argument ist nicht falsch, wir können den minimalen Spannbaum tatsächlich in polynomieller Zeit bestimmen: Sortiere die Kanten nach Länge (am besten nach quadrat der Länge, das ist dasselbe aber braucht keine wurzeln), dann gehe greedy vor und nimm Kanten dazu, die keine Kreise erzeugen. Dummerweise geht das aber an der NP-Frage vorbei. Die Klasse NP ist eine Klasse von Entscheidungsproblemen: Die richtige Frage lautet also, gegeben n Punkte im R^2 (mit rationalen Koordinaten) und eine rationale Zahl b, gibt es einen Spannbaum mit Gesamtlänge kleiner oder gleich b. Natürlich können wir wie zuvor beschrieben den kürzesten Spannbaum ausrechnen. Das große Problem ist die Länge mit b zu vergleichen. Die Länge des Spannbaums ist nämlich eine Summe von n-1 Wurzeln von rationalen Zahlen, die mit einer rationalen Zahl verglichen werden sollen. Gelingt uns das, so ist damit nachgewiesen dass das Problem in NP ist, geht das aber nicht effizient, dann ist das Problem nicht in NP. Und genau diese Frage, ob man eine Summe von Wurzeln rationaler Zahlen effizient mit einer rationalen Zahl vergleichen kann ist ein großes offenes Problem.

    Beim TSP und letztlich bei sehr vielen Problemen in denen Geometrie vorkommt, ist deshalb häufig nicht so leicht zu klären, ob sie nun in NP liegen oder nicht.


Anmelden zum Antworten