vorige nächste

Informiertheit bei greedy


Die Strahlsuche hat einen Extremfall: Wenn bei Strahlsuche jeweils nur noch genau ein Nachfolger für jeden expandierten Knoten (Tiefensuche) bzw. für jede Ebene (Breitensuche) bestimmt wird, geht die Strahlsuche in die Strategie des Bergsteigens über.

Strategie des Bergsteigens
Wähle als nächsten Knoten nur den aussichtsreichsten Knoten aus.

Bei der Strategie des Bergsteigens geht nicht nur die Vollständigkeit der Suche verloren. Der wesentliche neue Aspekt ist: Bei der Strategie des Bergsteigens geht der Versuchs - Charakter verloren. Ein reversibler Suchprozess -wenn es so nicht geht, machen wir den Schritt rückgängig- schlägt um in einen irreversiblen Prozess. Jeder Nachfolger eines Knotens wird unwiderruflich bestimmt!

Das Suchverfahren ähnelt einem direkten Verfahrens. Allerdings unterscheidet es sich in einem wesentlichen Punkt von einem direkten Verfahren: Durch eine Bergsteigestrategie werden in der Regel nur suboptimale Lösungen erzeugt. Schlimmer: Im Falle von Satisfizierungsproblemen kann die Suche erfolglos enden, obwohl tatsächlich eine Lösung existiert!

Das Suchverfahren wäre also nur dann ein direktes Verfahren, wenn jede Entscheidung die richtige wäre. Das ist aber in der Regel nicht der Fall. Nur dann, wenn ein Greedy Verfahren nachweislich zur optimalen Lösung führt, stellt es ein direktes Lösungsverfahren dar.

Also nur Spielerei? Nein! Bortfeld schreibt dazu:
Dennoch werden bei kombinatorischen Optimierungsproblemen mit betriebswirtschaftlichem Hintergrund nicht selten Bergsteigestrategien bzw. Greedyverfahren angewendet, weil deren Ressourcenbedarf vergleichsweise gering und kontrollierbar ist. Als Beispiel seien etwa klassische Strategien für Bin Packing-Probleme oder Strategien für die Maschinenbelegung mit Prioritätsregeln genannt.