Prinzip: Teile und Herrsche
- Suchraum ist in disjunkte Teilmengen zerlegbar.
- Eine untere Schranke einer Teilmenge ist leicht berechenbar
- Heuristik für den wirklichen Funktionswert
- Suche in der Teilmenge weiter, in der sich der Funktionswert
verbessert.
- Ende, wenn ein bestimmtes Abbruchkriterium erfüllt ist
z.B.
- Zeit
- Rekursionstiefe
- keine Verbesserung nach n Schritten
- Bewertungsfunktion liefert "akzeptables" Ergebnis
Im WORST-CASE ist
dieses Verfahren auch exponetniell
(Wenn denn wirklich das globale Optimum erreicht werden soll.)
|