极小极大算法队列可行吗？

Question

3

在队列数据结构中实现极小化极大算法是否可能？还是只能在树中实现？

- Bob

你的意思是询问在minmax算法中是否可以使用队列吗？还是在表示游戏的不同状态时是否可以使用队列？ - aspiring.algorist

游戏状态形成一棵树，有子节点和父节点。使用双端队列遍历树是一种方便的方式，可以选择深度优先或广度优先。因此，您可以使用双端队列来实现它，但仍需要知道哪个状态是哪个父节点的子节点。 - Mark

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kyle Jones · Accepted Answer

如果您将Minimax实现为广度优先的游戏树搜索，那么队列的FIFO特性自然适合该算法。您将在队列中存储每个位置，然后存储所有可能从该位置得出的位置。递归直到达到终止搜索深度。但缺点是，与树的深度相比，终端节点的数量呈指数级增长，并且您必须在广度优先搜索中将它们全部存储在队列中。

Minimax最好作为深度优先搜索来实现，这仅需要与树深度成比例的线性内存量。用于此搜索的数据结构是堆栈，可以通过递归函数调用或无功能调用开销的直接堆栈实现来实现。