アルファベータ検索時間の複雑度

Question

私はミニマックスとアルファベータのプルーニングの基礎を理解しています。すべての文献において、最良の場合の時間複雑度は、b =分岐因子およびd =木の深さであるO（b ^（d/2））であり、すべての優先ノードが最初に展開されます。

"ベストケース"の私の例では、私は4レベルのバイナリツリーを持っているので、16のターミナルノードのうち、最大7つのノードを展開する必要があります。これはO（b ^（d/2））にどのように関連していますか？

彼らがどのようにO（b ^（d/2））に来るのか分かりません。

どうか、私にそれを説明できますか？多くのThans！

Answer 1

O（b ^（d/2））は、アルファベータプルーニングの最良のケース時間複雑さに対応する。 Explanation：Bの因子、およびdプライの検索 深分岐（平均値または定数）で

（移動順序がpessimalである場合）、リーフノード位置の最大数は を評価O（Bでありますb ... * b）= O（b^d） - 単純なミニマックス検索と同じです。探索 の移動順序が最適である場合（最善の動きが常に最初に検索されることを意味する）、 の奇数については、O奥行きはO（b * 1 * b * 1 * ... * 1）、O（b ^（d/2））とする。 検索のプライが偶数である後者の場合、有効な 分岐係数は平方根に縮小されるか、同等に同じ量の計算で2倍の深さになる可能性があります。

b * 1 * b * 1 *の説明は、最初のプレイヤーのすべての動きが最も良いものを見つけるために検討されなければならないということです。しかし、それぞれについて、最も良い唯一の は、最初の（そして最高の） 最初のプレイヤーの移動 - アルファベータは他の第2プレイヤーの移動を保証しません。 を考慮する必要があります。簡単に言えば

、あなたはすべての2つのレベルの「スキップ」：引数が特定の値または無限大に向かう傾向があるので、あなたのケースで比較するとき

をOは、機能の制限動作について説明します正確には、bとdの値が小さいO（b ^（d/2））は実際には意味をなさない。