Die 2 Konzepte beziehen (Sie können manchmal sogar kombinieren), aber Sie sollten nur konzentrieren sich auf die grundlegenden Unterschiede zwischen ihnen, als ihre Namen vermuten lassen:
Branch and Bound erforscht den Suchraum erschöpfend auf Variablen Verzweigung (= teste die Werte der Variablen). Dies erzeugt mehrere Teilprobleme, z.B. Verzweigen auf eine binäre Variable erzeugt ein Problem, in dem die Variable = 0 und ein Problem, in dem es = 1 ist. Sie könnten dann fortfahren und sie rekursiv lösen. Der "Begrenzungs" -Aspekt der Technik besteht darin, Grenzen für die Lösungen abzuschätzen, die im Teilproblem erreicht werden können. Wenn das Teilproblem nur zu schlechten Lösungen führen kann (verglichen mit einer zuvor gefundenen Lösung), können Sie die Erkundung dieses Teils des Suchraums sicher überspringen.
Am besten zuerst versuchen, eine Lösung so schnell wie möglich zu finden, indem Sie zuerst den interessantesten Teil des Suchraums betrachten (am interessantesten = Schätzung). Es teilt den Suchraum nicht auf, sondern versucht so schnell wie möglich eine Lösung zu erreichen.
Beide Ansätze versuchen, die Untersuchung von Teilen des Suchraums zu überspringen. Ihre Nutzung und Effizienz hängt von der Problemstellung ab. Zuerst müssen Sie ein Kriterium für "die interessanteste Lösung zum Erkunden" angeben, was manchmal schwierig/unmöglich sein kann. Branch and Bound ist nur dann interessant, wenn die Bindung, die Sie an die Teilprobleme anlegen können, sinnvoll/nicht zu breit ist. Es hängt von dem Problem ab, das Sie in Betracht ziehen ...
Was ich verstanden habe, ist dies: Best-First-Suche berücksichtigt nur die Kosten des Erreichens eines Zustands (dh die Summe der Kosten vom Stammzustand zu diesem Zustand) für das Ranking , aber BB verwendet geschätzte Mindestkosten für die Bereitstellung vollständiger Lösungen über diesen Staat. Habe ich recht? – Barpa
Nein, Beste Zuerst wird versucht, den nächsten zu prozessierenden Knoten anhand einer globalen Kostenschätzung und nicht nur der aktuellen Kosten auszuwählen. Stellen Sie sich ein Navigationsproblem vor, für das Sie Dijkstra verwenden könnten, um Pfade mit dem kürzesten Pfad zu erstellen. Wenn Dijkstra nur die Kosten für das Erreichen des aktuellen Zustands ermittelt, wählt Dijkstra den Knoten mit der geringsten vorläufigen Entfernung aus, die als nächstes erledigt werden soll. Wenn Sie Best First anwenden, erhalten Sie A * wie in A * wählen Sie immer den Knoten mit der niedrigsten Gesamtkostenschätzung. – Origin
Sorry, aber ich bin jetzt mehr verwirrt. Sie sagen am besten, zuerst den nächsten Knoten mit der globalen Kostenschätzung auszuwählen. Ist die globale Kostenschätzung nicht gleich wie die globale gebundene (untere oder obere) Verzweigung und gebundene Verwendung zum Vergleich mit dem aktuellen Zustand? – Barpa