Complessità temporale ricerca alfa beta

Question

Comprendo le nozioni di base di potatura minimax e alfa-beta. In tutta la letteratura, parlano della complessità temporale per il caso migliore è O (b^(d/2)) dove b = fattore di ramificazione e d = profondità dell'albero, e il caso base è quando tutti i nodi preferiti sono espanso prima.

Nel mio esempio del "caso migliore", ho un albero binario di 4 livelli, così fuori dei 16 nodi terminali, devo ampliare al massimo 7 nodi. Come si riferisce a O (b^(d/2))?

Non capisco come vengono a O (b^(D/2)).

Per favore, qualcuno può spiegarmelo? Grazie mille!

Answer 1

O (b^(d/2)) corrisponde al caso migliore tempo complessità della potatura alfa-beta. Explanation:

Con una (media o costante) ramificazione fattore b, e una profondità di ricerca di d strati, il numero massimo di posizioni nodo foglia valutati (quando l'ordinamento mossa è pessimal) è O (b b ... * b) = O (b^d) - lo uguale a una semplice ricerca minimax. Se la mossa di ordinare per la ricerca è ottimale (cioè le mosse migliori sono sempre cercati prima), il numero di posizioni nodo foglia valutati è di circa O (b * 1 * b * 1 * ... * b) per dispari profondità e O (b * 1 * b * 1 * ... * 1) per profondità pari o O (b^(d/2)). In quest'ultimo caso , in cui lo strato di una ricerca è ancora, il fattore effettivo di ramificazione è ridotto alla sua radice quadrata, o, equivalentemente, la ricerca può andare due volte profondo con la stessa quantità di calcolo.

La spiegazione di B * 1 * b * 1 * ... è che tutte le mosse del primo giocatore devono essere studiati per trovare quello migliore, ma per ciascuno, è necessario spostare solo il meglio secondo giocatore di confutare tutto tranne il primo (e migliore) movimento del primo giocatore - alpha-beta non garantisce altri spostamenti del secondo giocatore deve essere considerato.

In parole povere, si "salta" ogni due livelli:

O descrive il comportamento di limitazione di una funzione quando l'argomento tende verso un particolare valore o infinito, così nel tuo caso il confronto precisamente O (b^(d/2)) con piccoli valori di b e d non ha senso.