N后问题的拉斯维加斯算法研究

王立志

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

1 引言

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

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

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

2 相关工作

拉斯维加斯算法是由László Babai 在1979年提出的，最初是为了解决图同构问题。Babai给这种算法命名为“拉斯维加斯算法”，并且使用“抛硬币”的例子来解释这个算法[3]。Max Bezzel 于1848年提出了八皇后问题，Franz Nauck 提出了第一种解决方案，同时他也将这个问题推广到n皇后的问题，即在n×n的棋盘上放置n个皇后。Edsger Dijkstra发表了一篇关于深度优先回溯算法的非常详细的描述[4]。在使用回溯法解决n后问题的研究中，陈晓梅等将位运算运用到回溯法的剪枝函数中，这一方法能够加速获得正确解的效率[5]。刘寒冰等改进了互不攻击的条件[6]。黄建民等通过使用较好的数据类型表示解空间，设计了八皇后问题的非递归算法[7]。张万军借助矩阵改进了检测攻击条件的方法，并且优化了算法的循环结束条件[8]。 有学者在研究拉斯维加斯算法解n后问题的算法效率后，通过加入随即策略改进回溯法，并验证该改进算法具有更好的算法效率[9][10]。

3 算法介绍

棋盘通过一个排列向量来表示，在排列向量中给出了n行中n个皇后的位置，这意味着在水平和垂直的方向上都没有攻击，算法只需检查两侧对角线方向的攻击。一个向量标记对角线的常数（行-列）；另一个标记常数（行+列）的对角线。

基本逻辑

repeat

将有效值设为真

将当前的排列向量重置

将两个对角向量都设置为false

标记两个对角线中的第0行女王

for row = 1 to n–1

set test = row+1

while

if test = n

set valid to false

打破while循环

else

交换位置行和测试

增量测试

end if/else

end while

如果无效

退出for循环

在对角线上标记该行的女王

vectors

end for

循环直到有效

使用类范围生成器将整个数组混洗

拉斯维加斯算法针对N皇后问题构建一个可能有效的棋盘：随机排列，然后进行验证或不做（因此返回的布尔值-仅在发现的棋盘为有效解决方案时为true）。

在使用拉斯维加斯算法解决N后问题的代码基础上，我们加入了线程的思想，使用多线程加快了查找解决方案的速度。计算是在充当计算引擎的线程内完成的。线程类是QueenLasVegas的内部类，因此其代码可以完全访问线程类的所有私有部分。为了确保每个线程使用一个_different_随机数序列，每个线程都有自己的生成器，并且该生成器由System.currentTimeMillis（）和this.hashCode（）的乘积作为种子：第一个在连续运行时生成机会种子，第二个在相同的运行中生成机会种子。ComputeEngine类具有一个静态int []解决方案，该解决方案接收对其中一个线程发现的第一个成功解决方案的引用。当此静态数据成员变为非空时，所有线程都会终止处理。

4 实验及结果分析

使用安装Window 10系统，使用3.20GHz AMD Phenom处理器，RAM为4GB的计算机作为测试环境。表1比较了使用传统回溯法和使用拉斯维加斯算法，以及多线程拉斯维加斯算法在解决N后问题上使用的时间。

表1：回溯法与拉斯维加斯算法时间效率比较

可以看出，在N后问题中，使用拉斯维加斯算法能够有效地加快获取可行解需要的时间，其程序运行时间明显优于传统回溯法，并且加速效果随问题规模的扩大变得更加明显。通过理论分析及实验结果证明，拉斯维加斯算法解决N后问题是可行并且有效的。

5 结束语

在解决N后问题的方法中大多采用了回溯法，而拉斯维加斯算法解决N后问题时选择最优解需要更少的时间，得益于该算法的随机性，可以降低求解算法的复杂度。本文使用了拉斯维加斯算法设计并实现了N后问题的解决办法，并且结合线程的办法对实现程序进行了优化。拉斯维加斯算法有一定的缺陷，在后续的研究中，我们将从该算法的缺点着手，对拉斯维加斯算法进行改进，以获得更好的算法效率。