拉斯維加斯算法和N皇後問題

拉斯維加斯算法的一個顯著特征是它所作的随機性決策有可能導緻算法找不到所需的解。是以通常用一個bool型函數表示拉斯維加斯算法。

void Obstinate(InputType x, OutputType &y){
    // 反複調用拉斯維加斯算法LV(x, y)，直到找到問題的一個解
    bool success= false;
    while (!success) 
         success = LV(x,y);
}      

考慮用拉斯維加斯算法解決​​N皇後問題​​：

對于n後問題的任何一個解而言，每一個皇後在棋盤上的位置無任何規律，不具有系統性，而更象是随機放置的。由此容易想到下面的拉斯維加斯算法。

在棋盤上相繼的各行中随機地放置皇後，并注意使新放置的皇後與已放置的皇後互不攻擊，直至n個皇後已相容地放置好，或已沒有下一個皇後的可放置位置時為止。注意這裡解決的是找到其中一個方法，求不是求出N皇後的全部解。

這裡提前說明一下，否則不好了解。

接下來的這個用Las Vegas算法解決N皇後問題，我們采用的是随機放置位置政策和回溯法相結合，具體就是比如八皇後中，前幾行選擇用随機法放置皇後，剩下的選擇用回溯法解決。

這個程式不是很好了解，有的地方我特别說明了是了解程式的關鍵，大家看時一定要認真了，另外，王曉東的書上先是用單純的随機法解決，大家可以先去了解書上這個例子。然後再來分析我這個程式。不過那本書上關于這一塊錯誤比較多，大家看時要注意哪些地方他寫錯了。

拉斯維加斯算法解決N皇後代碼：

依然用到了RandomNumber.h頭檔案，大家可以去看下

頭檔案 RandomNumber.h：
const unsigned long maxshort = 65535L;
const unsigned long multiplier = 1194211693L;
const unsigned long adder = 12345L;
#ifndef RANDOMNUMBER_H
#define RANDOMNUMBER_H
class RandomNumber{
private:
    // 目前種子
    unsigned long randSeed;
public:
    // 構造函數,預設值0表示由系統自動産生種子
    RandomNumber(unsigned long s = 0);
    // 産生0 ~ n-1之間的随機整數
    unsigned short Random(unsigned long n);
    // 産生[0, 1) 之間的随機實數
    double fRandom();
};
#endif      

剩下部分的代碼：

注意QueensLV()函數是這個程式的精髓所在。

Queen.h頭檔案

#ifndef QUEEN_H
#define QUEEN_H
 
class Queen
{
    friend bool nQueen(int);
private:
    bool Place(int k);             // 測試皇後k置于第x[k]列的合法性
    bool Backtrack(int t);         // 解n後問題的回溯法
    bool QueensLV(int stopVegas);  // 随機放置n個皇後拉斯維加斯算法
    int n, *x, *y;
};
 
#endif

Queen.cpp檔案(算法的關鍵位置)

#include <iostream>
#include "Queen.h"
#include "RandomNumber.h"
using namespace std;
bool Queen::Place(int k){
    // 測試皇後k置于第x[k]列的合法性
    for(int j = 1; j < k; ++ j)
        if((abs(k-j) == abs(x[j]-x[k])) || (x[j]==x[k]))
            return false;
    return true;
}
 
bool Queen::Backtrack(int t){
     // 解n後問題的回溯法
    if(t > n){
        for(int i=1; i<=n; ++i)
            y[i] = x[i];
        return true;
    }else
       for(int i=1; i<=n; ++i){
           x[t] = i;
           if(Place(t) && Backtrack(t+1))
                return true;
       }
    return false;
}
/*
* QueensLV是整個Las Vegas解n皇後的精髓。而且這個函數不好了解，我在這裡具體分析下。
* k是第k行，x[k]表示第k行的皇後放在x[k]列
* 下面這兩點解析請認真看了，我個人就是卡在這裡半天了，但是了解後很簡單。
* 标号①處：這裡是周遊第k行所有可以放置的列号，用y儲存下來，并用count記錄有多少個位置可以放置
* 标号②處：這裡利用上面儲存的可以放置的列，然後随機取其中一列來放置第k行的皇後。這就是Las Vegas的精髓！
*/
bool Queen::QueensLV(int stopVegas){
     // 随機放置n個皇後的拉斯維加斯算法
     RandomNumber rnd;    // 随機數産生器
     int k = 1;           // 下一個放置的皇後編号
     int count = 1;
     // 1 <= stopVegas <= n 表示允許随機放置的皇後數
     while((k <= stopVegas) && (count > 0)){
         count = 0;
         for(int i = 1; i<=n; ++i)      // ----------- ①
         {
             x[k] = i;
             if(Place(k))
                y[count++] = i;
         }
         if(count > 0)                   // -------------②
             x[k++] = y[rnd.Random(count)];   // 随機位置
     }
     return (count > 0);   // count > 0表示放置位置成功
}      

Main.cpp主檔案：

#include "Queen.h"
#include "RandomNumber.h"
#include <iostream>
using namespace std;
bool nQueen(int n){
     // 與回溯法結合的解n後問題的拉斯維加斯算法
     Queen X;
    // 初始化X
    X.n = n;
    int *p = new int[n+1];
    int *q = new int[n+1];
    for(int i=0; i<=n; ++i){
       p[i] = 0;
       q[i] = 0;
    }
    X.y = q;
    X.x = p;
   // 設定随機放置皇後的個數
    int stop = 8;
    if(n > 15)
      stop = n-15;
    bool found = false;
    while(! X.QueensLV(stop));
     // 算法的回溯搜尋部分
   if(X.Backtrack(stop+1)){
       for(int i=1; i<=n; ++i)
       cout << p[i] << " ";
       found = true;
    }
    cout << endl;
    delete [] p;
    delete [] q;
    return found;
}
int main()
{
    nQueen(8);
}      

在8皇後問題中：

1.stopVegas=0表示完全使用回溯法解決問題。是以一定可以得到一組解。

2.stopVegas=8表示完全實用随機法解決問題。是以一定可以得到一組解。

注意書上說解決8皇後問題時，列出了一個不同stopVegas值時，所對應的算法成功率，在stopVegas=8時，他寫着是0.1293，我個人認為是錯的。接下來我說下自己這麼了解的原因：

首先，這個程式為何會造成有失敗的情況，那就是因為在随機求出前stopVegas行成立時，不代表後面N-stopVegas行用回溯就可以成立，因為這不是一個徹底的回溯。它是從stopVegas+1行開始計算，回溯不成立最後傳回時，也隻停留在stopVegas。