Pruning
Pruning bezeichnet in der Mathematik und Informatik ein Vorgehen bei der Enumeration (einem Algorithmus zum Finden aller Objekte mit einer gewissen Eigenschaft), bei dem bestimmte Möglichkeiten "abgeschnitten", d.h. nicht betrachten werden, weil man bereits weiß (bzw. bei spekulativem Pruning davon ausgeht), dass diese das gesuchte Objekt nicht enthalten.
Beispiele
Spieltheorie
In Spielbaumsuchverfahren für Zwei Personen Nullsummenspiele mit vollständiger Information, wie z. B. Minimax, Negamax oder deren optimierte Varianten Principal Variation Search (PVS), Negascout etc. verwendet man verschiedene Pruning Methoden zur Vorwärtsabscheidung von Varianten.
Schach
Wichtige Pruningtechniken in Schachprogrammen sind z. B.
- Nullmove Pruning
- Verified Nullmove Pruning
- Killerheuristk
- Historyheuristik