王立志

（河南大学计算机与信息工程学院 河南省开封市 475004）

1 引言

随机化算法是一种将一定程度的随机性作为其逻辑的一部分的算法。随机化算法通常使用统一的随机位作为辅助输入来指导其行为，以期在所有随机位的可能选择的“平均情况”下获得良好的性能[1]。拉斯维加斯算法的一个显著特征是它所做的随机性决策有可能导致算法找不到所需的解[2]。

拉斯维加斯算法是一种永远给出正确结果的随机化算法[3]。拉斯维加斯算法的性质使它们适合于可能的解决方案数量有限的情况，在这种情况下，验证候选解决方案的正确性相对容易，而寻找解决方案则比较复杂。拉斯维加斯算法的运行时间取决于输入的规模。拉斯维加斯算法找到正确解的概率与所使用的计算时间有关，对于同一问题，使用拉斯维加斯算法反复计算求解足够多次就可以不断缩小算法失效的概率[2]。

n后问题等价于在n×n格的棋盘上放置n个皇后，在可行的解棋盘中，同一行、列或者斜线上不会同时出现两个皇后。N后问题提供了设计高效的拉斯维加斯算法的很好的例子。在使用回溯法解n后问题时，实际上是在系统地搜索整个解空间树的过程中找出满足要求的解。对于n后问题的任何一个解来说n个皇后更像是随机放置的，这符合随机化算法的性质。应用拉斯维加斯算法在棋盘上相继的各行中随机地放置皇后，并注意使新放置的皇后与已放置的皇后互不攻击，直至n个皇后均已相容地放好，或已没有下一个皇后的可放置位置时为止[2]。……