Ich verstehe, dass DP eine bessere Leistung für viele NP komplette Probleme wie TSP bietet. Obwohl der Platzbedarf groß ist, reduziert sich die Komplexität erheblich.Vorteil der Verwendung von Backtracking und verzweigen und binden
Aber ich konnte die Effizienz von Branch und Bound und Backtracking im Vergleich zu einer Brute-Force-Suche nicht verstehen.
Im schlimmsten Fall, ob Brute Force gleich & b oder Backtracking ist?
Mit erschöpfender Suche würden Sie alle N berechnen! mögliche Routen zwischen den Knoten. Mit Backtracking können Sie eine Route berechnen, die die Hälfte der Knoten besucht, und feststellen, dass sie bereits teurer ist als die bisher beste Route, und an diesem Punkt die Teilroute nicht mehr untersuchen. Auf diese Weise haben Sie die Berechnung aller Routen, die durch die Fertigstellung dieser Teilroute erstellt wurden, übersprungen und so Zeit für eine erschöpfende Suche gespart, die sie alle weiterhin überprüft hätte.
Aber im schlimmsten Fall müssen beide N überprüfen! Kombinationen! – user567879
@ user567879: Korrigieren. Es gibt keine Silberkugel. Die Branch-and-Bound-Lösung hilft beim * durchschnittlichen * Fall, nicht * schlechtesten * Fall. – amit
Ich kenne keine guten Worst-Case-Grenzen für die Verzweigung und gebunden an den TSP. Alle Beschreibungen, die ich gesehen habe (die bessere Auswahlmöglichkeiten für die Verzweigung und bessere Begrenzungsfunktionen verwenden als mein übermäßig vereinfachtes Beispiel) konzentrieren sich auf das erwartete Verhalten, das typischerweise durch Computerexperimente analysiert wird. Diese Experimente zeigen jedoch, dass eine sorgfältige Verzweigung und Grenze in der Praxis viel effektiver ist als die rohe Gewalt - das Beispiel unter http://www.tsp.gatech.edu/sweden/compute/compute.htm - das auch etwas Handabstimmung verwendet - ist mir aufgefallen. – mcdowella
Durch erschöpfende Suche meinen Sie eine Brute-Force-Suche? – Gangadhar
@Gangadhar Auf Brute-Force-Suche geändert – user567879