Als Teil meiner High-School-These beschreibe ich die Heuristiken für das Travelling-Salesman-Problem. ich habe gelesen Dies Art von Fallstudie (Seite 8), aber ich kann nicht verstehen, was diese Sätze bedeuten:
Die Laufzeit für NN wie beschrieben ist Θ (N ^ 2 ). [...] Insbesondere wird garantiert, dass NN (I) / OPT (I) ≤ (0,5) (log_ {2} N + 1).
Dieser Teil ist mir sehr klar. Aber dann:
Nein im Wesentlichen Eine bessere Garantie ist jedoch möglich, da es Fälle gibt, für die das Verhältnis gilt wächst als Θ (logN).
Was bedeutet Es gibt Fälle für die?
Das Gleiche passiert mit dem Greedy-Algorithmus:
... aber das Schlimmste Beispiele, die für Greedy bekannt sind, lassen das Verhältnis nur wachsen als (logN) / (3 log log N).
Was bedeuten diese Aussagen also? Hat es mit nicht euklidischen Instanzen zu tun (ich würde das nicht glauben, weil man nur die Spalte einer Abstandsmatrix durchlesen muss, um sie zu lösen) oder nur Instanzen mit zB mehreren Knoten in der gleichen Entfernung von der Startknoten, der den Algorithmus benötigt, um den Lösungsbaum oder ähnliches zu teilen?
BEARBEITEN: Dank @templatetypedef (Ihre Antwort wird immer noch als korrekt akzeptiert), macht alles Sinn. Ich möchte jedoch fragen, ob jemand ein Beispiel (oder auch nur einen Link) davon kennt spezifische Graphen (Ich kümmere mich nicht um den Algorithmus.) Ich denke nicht, dass es zu viel vom Thema ist, es würde eher etwas Nützliches zum Thema hinzufügen.
Antworten:
1 für die Antwort № 1Sehen Sie sich diese beiden Aussagen nebeneinander an:
Insbesondere wird garantiert, dass NN (I) / OPT (I) ≤ (0,5) (log_ {2} N + 1).
Es ist jedoch keine wesentlich bessere Garantie möglich, da es Fälle gibt, in denen das Verhältnis als Θ (logN) wächst.
Diese erste Aussage besagt, dass der Algorithmus NN, inIm schlechtesten Fall ergibt sich eine Antwort, die (ungefähr) innerhalb von 1/2 lg N der wahren Antwort liegt (um dies zu sehen multiplizieren Sie einfach beide Seiten mit OPT (I)). Das sind großartige Neuigkeiten! Die natürliche Folgefrage ist also, ob die tatsächliche Grenze noch enger ist. Zum Beispiel schließt dieses Ergebnis die Möglichkeit nicht aus, dass wir auch NN (I) / OPT (I) ≤ log log N oder dass NN (I) / OPT (I) ≤ 2 haben können. Diese sind viel engere Grenzen.
Da kommt die zweite Aussage rein. Diese Aussage besagt, dass es bekannte Fälle von TSP gibt (d. H. Spezifische Graphen mit Gewichten auf ihnen), bei denen das Verhältnis NN (I) / OPT (I) Θ (log n) ist (dh das Verhältnis ist proportional zum log der Anzahl der Knoten in der Grafik). Da wir solche Eingaben bereits kennen, gibt es keine Möglichkeit, dass NN (I) / OPT (I) von etwas wie log log n oder 2 von oben begrenzt werden kann, da diese Grenzen zu eng sind.
Diese zweite Aussage ist jedoch isoliertnicht sehr nützlich. Wir wissen, dass es Inputs gibt, die den Algorithmus veranlassen würden, etwas zu produzieren, das durch einen Log-Faktor ausgeschaltet ist, aber es könnte trotzdem möglich sein, dass es Inputs gibt, die dazu führen, dass es viel mehr ausgeht, zum Beispiel durch einen Exponentialfaktor "Mit der ersten Aussage wissen wir, dass dies nicht passieren kann, da wir wissen, dass wir nie mehr als einen logarithmischen Faktor erhalten.
Stellen Sie sich diese Aussagen in zwei Schritten vor: Die erste Aussage ergibt ein obere Grenze wie schlecht die Approximation sein kann - sie ist niemals schlechter als ein 1/2 lg N + 1 Faktor von optimal. In der zweiten Aussage gibt a untere Grenze Wie schlecht die Approximation sein kann - es gibt spezielle Fälle, in denen der Algorithmus nicht besser als eine Θ (log N) Approximation der optimalen Antwort ist.
(Beachten Sie, dass das Θ (log n) hier nichts mit der Laufzeit zu tun hat - es ist nur eine Art zu sagen "etwas Logarithmisches.")
In Zukunft sollten Sie nach Ober- und Untergrenzen Ausschau halten. Die beiden erzählen Ihnen viel mehr als jeder einzelne.
Viel Glück mit der These!