Las Vegas

拉斯维加斯算法是一种随机化算法。总之可以用来骗分。

以下类型的问题可以使用拉斯维加斯算法:

1.寻找任意一个可行解。

2.最优解占可行解集的比例较大。

3.类似质因数分解的单一解问题,可以用此算法一步步得出解。

一般形式

N皇后问题

目前公认的最优N皇后问题的解法是回溯(搜索)。复杂度约为O(NN),虽然当N大于15时搜索便开始罢工,但这样当然可以找到所有可行解。但是如果只要求找到任意一个解,回溯法就显得有些多余。

注意到N皇后问题的解并没有什么规律,皇后类似于随机摆放在棋盘上。所以可以利用LasVegas算法在前k行随机摆放皇后,后(N-k)行利用回溯完成。实践证明1s内可以在N<=200的范围内较为稳定地得出至少一个可行解。这比普通回溯法的效率高出了至少2000个数量级。%%%