Alpha Beta Suchzeit Komplexität

Question

Ich verstehe die Grundlagen der Minimax und Alpha-Beta-Beschneidung. In der ganzen Literatur sprechen sie von der Zeitkomplexität für den besten Fall ist O (b^(d/2)), wobei b = Verzweigungsfaktor und d = Tiefe des Baumes, und der Basisfall ist, wenn alle bevorzugten Knoten sind zuerst erweitert.

In meinem Beispiel des "besten Falles" habe ich einen binären Baum von 4 Ebenen, so dass ich von den 16 Endknoten maximal 7 Knoten erweitern muss. Wie verhält es sich mit O (b^(d/2))?

Ich verstehe nicht, wie sie zu O kommen (b^(d/2)).

Bitte, kann mir das jemand erklären? Thans viel!

Answer 1

O (b^(d/2)) entsprechen der besten Zeitkomplexität von Alpha-Beta-Beschneidung. Explanation:

mit einem (Mittelwert oder konstant) Faktors b Verzweigung und einer Such Tiefe d Lagen, bewerteten die maximale Anzahl der Blattknotenpositionen (wenn die Bewegungs Ordnung ist pessimal) O (b b ... * b) = O (b^d) - das entspricht einer einfachen Minimax-Suche. Wenn die Bewegungsreihenfolge für die Suche optimal ist (dh die besten Züge werden immer zuerst gesucht), ist die Anzahl der bewerteten Blattknotenpositionen ungefähr 0 (b * 1 * b * 1 * ... * b) für ungerade Tiefe und O (b * 1 * b * 1 * ... * 1) für gerade Tiefe oder O (b^(d/2)). In dem letzteren Fall, in dem die Suchlage gerade ist, wird der effektive Verzweigungsfaktor auf seine Quadratwurzel reduziert, oder äquivalent kann die Suche bei derselben Berechnungsmenge zweimal so tief gehen.

Die Erklärung von b * 1 * b * 1 * ... ist, dass alle Bewegungen des ersten Spielers muss finden untersucht werden, um die besten, aber für jeden, nur den besten zweiten Spieler bewegen müssen widerlegen alle außer dem ersten (und besten) erster Spielerzug - alpha-beta stellt sicher, dass keine anderen zweiten Spielerzüge in Betracht gezogen werden müssen.

Vereinfacht gesagt, Sie „überspringen“ alle zwei Level:

O, um das Grenzverhalten einer Funktion beschreibt, wenn das Argument auf einen bestimmten Wert oder Unendlich, so in Ihrem Fall zu vergleichen genau O (b^(d/2)) mit kleinen Werten von b und d ergibt keinen wirklichen Sinn.