【摘要】：负侦查搜索算法的基本思想如下：在搜索中，对于每一个搜索树节点，永远把一个子节点选作其主变量。负侦查搜索算法的伪代码如算法2.6所示。对于第一个子节点，负侦查搜索算法做了一个完整的α-β搜索，其返回值a，并使用位于a的空窗口对其余子节点进行侦察搜索。但在子节点已被适当排序的情况下，由于其高效剪枝，负侦查搜索算法的效率要高于α-β搜索算法。因此，负侦查搜索在计算机博弈中被广泛应用。
2.7 负侦查搜索
负侦查（NegaScout）搜索算法，也叫做主变量搜索算法（Principal Variation Search），就是使用渴望搜索对α-β搜索算法进行改进后所获得的一种高效率的搜索算法。负侦查搜索算法的基本思想如下：在搜索中，对于每一个搜索树节点，永远把一个子节点选作其主变量。初始的主变量是静态排序后的第一个子节点；对于主变量之外的子节点；使用以位于主变量返回结果的空窗口对其进行搜索。如果搜索返回结果大于搜索窗口上限，则证明这一子节点亦为主变量，并根据其返回结果对搜索窗口进行修正；如果返回值小于搜索窗口下限，这一子节点即可被剪枝，因为它的最佳结果也劣于主变量。
负侦查搜索算法的伪代码如算法2.6所示。对于第一个子节点，负侦查搜索算法做了一个完整的α-β搜索，其返回值a，并使用位于a的空窗口对其余子节点进行侦察搜索。如果负侦查搜索算法在某个子节点上搜索失败了，它会返回使用原始的α-β搜索对该子节点重新再做搜索。
算法2.6 负侦查搜索算法的伪代码
可以证明，被α-β搜索剪枝的节点也同样会被负侦查搜索剪枝。换句话说，负侦查搜索算法不会搜索不被α-β搜索算法所搜索的节点。这说明，在最坏的情况下，负侦查搜索算法与α-β搜索算法的复杂度是相同的。但由于负侦查搜索算法可能多次搜索某些节点，导致在最坏的情况下，比α-β搜索算法的效率低。但在子节点已被适当排序的情况下，由于其高效剪枝，负侦查搜索算法的效率要高于α-β搜索算法。因此，负侦查搜索在计算机博弈中被广泛应用。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
