Allgemeine Beschreibung der Branch-and-bound Organisation vollen Suchfunktionen.
Lösung des Handlungsreisenden Branch and Bound Methode:. Grundlayout
Lassen Sie - eine endliche Menge und - eine reellwertige Funktion darauf; erfordert
finden Sie das Minimum dieser Funktion und die Element der Menge, zu dem dieses Mindest
erreicht.
Wenn es die eine oder andere zusätzliche Informationen über die Menge, die Lösung dieses
das Problem manchmal ohne erschöpfende Suche aller Elemente der Menge
M. Aber mehr
nur noch eine erschöpfende Suche zu machen. In diesem Fall gibt es sicherlich
die Aufgabe, wie man am besten organisieren die Büste.
Branch and Bound Verfahren - ist eine der Methoden der Organisation des erschöpfende Suche. Er
nicht immer anwendbar, aber nur, wenn die folgenden spezifischen
zusätzliche Bedingungen für die Menge M und der minimierten Funktion auf sie. Das heißt,
-
davon ausgehen, dass es eine Echtwertfunktion auf den Satz von Teilmengen von j
Set M mit den folgenden zwei Eigenschaften:
für (hier - ein Set bestehend aus einem einzigen Element);
2), wenn und dann.
Unter diesen Bedingungen ist es möglich, eine Suche von Elementen M, um
Minimierung der Funktion auf diesem Satz wie:
Wir unterteilen die Menge M in Stücke (in irgendeiner Form) und wähle das aus seiner Teile W1, auf
die die Funktion j ist minimal; dann in mehrere Teile aufgeteilt und eine Menge W1
wir wählen einen ihrer Teile W2, die minimale Funktion j; dann teilen W2
in mehrere Teile und wählen Sie das in dem die Mindest j, und so weiter, bis
kommen zu jeder Singleton Satz.
Diese Aufzeichnung wird als ein Singleton.
Funktion j, die wir für diese Wahl wird als Bewertungs.
Offensichtlich ist, dass die Platte nicht das Minimum der Funktion f zu liefern; aber das ist, was
sich die Gelegenheit bietet, um Büste unter günstigen Umständen zu reduzieren.
Der oben beschriebene Prozess der Erstellung eines Datensatzes, bestehend aus einer Abfolge von Schritten zu
von denen jedes ein paar Sätze aufgezeichnet und wählt dann eine der
ihnen. Lassen - Teilmengen von M, was in der vorletzten Etappe
Aufbau eines Datensatzes, und lassen Sie den Satz bewiesen anhand von Bewertungs
ausgewählt Funktion. Es entstand in der Division und einem Rekord, dass für jetzt
Sicherheit wird durch gekennzeichnet. Gemäß der oben ,,; Darüber hinaus
Definition Bewertungsfunktion ,.
Angenommen; dann für jedes Element m der Menge M,
prozentige gesetzt ist, wird die Ungleichheiten; Dies bedeutet, dass der vollständige Enumeration
Elemente der M-Elemente haben keine Notwendigkeit, zu berücksichtigen. Wenn
Ungleichheit nicht erfüllt ist, dann alle Elemente von der Notwendigkeit, konsequent
gegenüber dem Rekord gefunden und werden so schnell wie das Element, das weniger
gibt gefunden werden Wertfunktion zu optimieren, ist es notwendig, sie zu ersetzen und weiterhin zuviel aufzuzeichnen.
Die letzte Aktion wird als Verbesserung Rekord.
Das Wort Branch and Bound Verfahren mit natürlichen grafische Interpretation
verbunden alle oben: ein Multi-Level-Baum ist im Erdgeschoss, die
gebaut sind die Elemente der Menge M, wobei Äste führen zu erfassen und seine
Verbesserungen und an dem Teil der Zweige bleiben" hängen", weil ihr
Entwicklung bewiesen unpraktisch.
Wir betrachten nun die erste von zwei in diesem Kurs Beispielen geplant
Anwendung Branch and Bound Verfahren - Lösung des Problem des Handlungsreis. Leider
Wortlaut.
Es gibt mehrere Städte in irgendeiner Weise mit den bekannten Straßen verbunden
Länge; erforderlich, um festzustellen, ob es einen Weg von beweglichen, die Sie
ermöglicht u...

Seite 1 der 3 | Nächste Seite




Ähnliche abstracts: