„Alfa-béta vágás” változatai közötti eltérés

[[Fájl:AB pruning.svg|bélyegkép|400px| Az alfa-béta vágás szemléltetése. A beszürkített részfákat nem kell megvizsgálni, mivel a baloldalt mellettük lévő lépés miatt alfa/béta vágás hajtható végre.]]

 

 

Egy képzeletbeli játékfa estében aminek minden csomópontjában konstans '''b''' lehetséges lépés van és '''d''' a mélysége, legkedvezőtlenebb esetben az alfa-béta algoritmus műveletigénye egyenlő a minimax algoritmus műveletigényével = '''O'''('''b'''^'''d'''). A legkedvezőbb esetben, amikor minden csomópontban a legjobb lépéssel kezdjük a vizsgálatot = <math>O(\sqrt{b^d})</math>. Azaz ugyanannak a fának a megvizsgálása négyzetgyöknyi levél csomópont kiértékelését igényli, vagy más nézőpontból megközelítve: ugyanannyi levél csomópont kiértékelése esetén kétszer olyan mély fát tudunk megvizsgálni.

 

[[Kategória:Algoritmusok]]