verzweigt und gebunden

Question

Kann mir jemand die Technik der Verzweigungssuche (branch and bound) erklären? Ich muss einen Pfad mit den kleinsten Kosten von einem beliebigen Startknoten zu einem Endknoten eines beliebigen Graphen mit Hilfe des Branch-and-Bound-Suchalgorithmus finden.

Answer 1

Der Grundgedanke von B & B ist:

1. Bei der Lösung eines Optimierungsproblems ("Finde ein X, das die Kriterien Y erfüllt, um die Kosten f(X) zu minimieren") baut man eine Lösung Stück für Stück auf - zu jedem Zeitpunkt hat man eine Teillösung die einen Kosten .
2. Wenn das Problem so beschaffen ist, dass die Kosten einer Teillösung nur gleich bleiben oder steigen können, wenn man weitere Teile hinzufügt, dann weiß man, dass Es macht keinen Sinn, eine Teillösung weiter auszubauen, wenn es bereits eine vollständige Lösung mit geringeren Kosten gibt. . In diesem Fall können Sie auf die weitere Bearbeitung dieser Teillösung verzichten (oder "stutzen", oder "ausloten").

Viele Probleme haben die letztgenannte Eigenschaft, was B & B zu einer weithin anwendbaren Algorithmustechnik macht.

Der Prozess der Lösungssuche kann durch eine Suchbaum wobei der Wurzelknoten den Ausgangspunkt darstellt, an dem noch keine Entscheidungen getroffen wurden, und jede von einem Knoten ausgehende Kante eine Entscheidung über etwas darstellt, das in eine Teillösung aufgenommen werden soll. Jeder Knoten ist eine Teillösung, die die Entscheidungen (Kanten) von der Wurzel bis zu diesem Knoten umfasst.

Beispiel: Wenn wir ein Sudoku-Rätsel lösen wollen, würde der Wurzelknoten das Brett darstellen, in das nur die ursprünglich angegebenen Zahlen eingetragen sind; von dieser Wurzel aus könnte es 9 Kanten geben, von denen jede die Entscheidung darstellt, der Zelle oben links eine Zahl von 1 bis 9 zuzuweisen. Jeder dieser 9 Teillösungsknoten könnte 8 Verzweigungen haben, die die gültigen Zuweisungen für die Zelle an der Position (1, 2) darstellen, und so weiter. Normalerweise stellt jede Kante einen Rekursionsschritt in einem Programm dar.

Mit B & B wird im besten Fall eine gute Lösung früh gefunden, was bedeutet, dass nicht vielversprechende Bereiche des Suchbaums in der Nähe der Wurzel beschnitten werden können; im schlimmsten Fall wird jedoch der gesamte Baum mit gültigen Lösungen generiert. Aus diesem Grund wird B & B in der Regel nur zur Lösung von Problemen verwendet, für die kein schnellerer Algorithmus bekannt ist (z. B. NP-schwere Probleme).

Answer 2

Dieser Link bietet eine grafische Darstellung von Konzepten im Zusammenhang mit B & B.

Dieser Link bietet eine Erläuterung des Algorithmus und C#-Beispielcode in einer herunterladbaren Zip-Datei.

Ich hoffe, das hilft.

Answer 3

Im Internet finden sich zahlreiche Hinweise auf Branch-and-Bound-Algorithmen.

これ können Sie eine theoretische Erklärung finden.

während der Code in C# lautet これ

Answer 4

Fantastische Antwort @j_random_hacker !!!!

Siehe S. 439 (Beispiel 18.2) in Papadimitriou und Steiglitz, Combinatorial Optimization.

Dieses Buch ist ein Klassiker, in dem genau Ihr Problem behandelt wird.