algorithm - 当我必须遍历完整的图形以找到终止状态时，修剪有何帮助？

Question

我阅读了minimax 算法，然后阅读了alpha beta 剪枝。虽然我能够理解修剪的想法，但我无法理解的是我仍然必须提前知道终端状态/叶节点。

要知道终端状态，我必须在内存中绘制完整的图形，并提前遍历每个节点。不是吗？

我在下图中有一个 1 维 1 X 3 网格。所以有 3 列但 1 行。我拿这个是为了更容易说明。

如您所见，我通过找出所有可能的状态然后遍历每个节点来计算每个 MIN/MAX。虽然修剪肯定会阻止额外的遍历，但它仍然有益，因为我必须遍历整个图。

Answer 1

您不必遍历整个图，因为修剪将确定不会确实为您提供更好解决方案的分支，并将它们从图中“删除”。 Here是帮助我理解算法的视频。