data-structures - ミニマックスアルゴリズムキューは可能ですか?

Question

キューデータ構造内でミニマックスアルゴリズムを表現することは可能ですか?それともツリー内でのみ可能ですか?

Answer 1

幅優先のゲーム ツリー検索としてミニマックスを実装する場合、キューの FIFO の性質はアルゴリズムに自然に適合します。各位置をキューに格納し、その位置から生じる可能性のあるすべての位置を格納します。終了する検索深度に達するまで再帰します。しかし、大きな欠点は、ツリーの深さに関連して指数関数的な数のターミナル ノードがあり、幅優先検索のためにそれらすべてをキューに格納する必要があることです。

Minimax は、深さ優先検索として実装する方が適切です。これは、ツリーの深さに関連して線形量のメモリのみを必要とします。この検索に使用されるデータ構造は、再帰関数呼び出しによるスタック、または関数呼び出しのオーバーヘッドのない直接スタック ベースの実装のいずれかです。