已出連載：
1.《隨機(jī)化算法(1) — 隨機(jī)數(shù)》
2.《隨機(jī)化算法(2) — 數(shù)值概率算法》
3.《隨機(jī)化算法(3) — 舍伍德(Sherwood)算法》
正文：
悟性不夠，這一章看代碼看了快一個(gè)上午，才理解。
上一章講過《概率算法(3) — 舍伍德(Sherwood)算法》，但是他的有點(diǎn)是計(jì)算時(shí)間復(fù)雜性對(duì)所有實(shí)例而言相對(duì)均勻，而其平均時(shí)間復(fù)雜性沒有改變。而拉斯維加斯算法怎么顯著改進(jìn)了算法的有效性。
拉斯維加斯算法的一個(gè)顯著特征是它所作的隨機(jī)性決策有可能導(dǎo)致算法找不到所需的解。因此通常用一個(gè)bool型函數(shù)表示拉斯維加斯算法。
void Obstinate(InputType x, OutputType &y)
{
// 反復(fù)調(diào)用拉斯維加斯算法LV(x, y)，直到找到問題的一個(gè)解
bool success= false;
while (!success)
success = LV(x,y);
}
考慮用拉斯維加斯算法解決N皇后問題：
對(duì)于n后問題的任何一個(gè)解而言，每一個(gè)皇后在棋盤上的位置無任何規(guī)律，不具有系統(tǒng)性，而更象是隨機(jī)放置的。由此容易想到下面的拉斯維加斯算法。
在棋盤上相繼的各行中隨機(jī)地放置皇后，并注意使新放置的皇后與已放置的皇后互不攻擊，直至n個(gè)皇后已相容地放置好，或已沒有下一個(gè)皇后的可放置位置時(shí)為止。注意這里解決的是找到其中一個(gè)方法，求不是求出N皇后的全部解。
這里提前說明一下，否則不好理解。
接下來的這個(gè)用Las Vegas算法解決N皇后問題，我們采用的是隨機(jī)放置位置策略和回溯法相結(jié)合，具體就是比如八皇后中，前幾行選擇用隨機(jī)法放置皇后，剩下的選擇用回溯法解決。
這個(gè)程序不是很好理解，有的地方我特別說明了是理解程序的關(guān)鍵，大家看時(shí)一定要認(rèn)真了，另外，王曉東的書上先是用單純的隨機(jī)法解決，大家可以先去理解書上這個(gè)例子。然后再來分析我這個(gè)程序。不過那本書上關(guān)于這一塊錯(cuò)誤比較多，大家看時(shí)要注意哪些地方他寫錯(cuò)了。
拉斯維加斯算法解決N皇后代碼：
依然用到了RandomNumber.h頭文件，大家可以去看下第一章，我就不貼出來了。
剩下部分的代碼：
注意QueensLV()函數(shù)是這個(gè)程序的精髓所在。
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); // 隨機(jī)放置n個(gè)皇后拉斯維加斯算法
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是整個(gè)Las Vegas解n皇后的精髓。而且這個(gè)函數(shù)不好理解，我在這里具體分析下。
* k是第k行，x[k]表示第k行的皇后放在x[k]列
* 下面這兩點(diǎn)解析請(qǐng)認(rèn)真看了，我個(gè)人就是卡在這里半天了，但是理解后很簡單。
* 標(biāo)號(hào)①處：這里是遍歷第k行所有可以放置的列號(hào)，用y保存下來，并用count記錄有多少個(gè)位置可以放置
* 標(biāo)號(hào)②處：這里利用上面保存的可以放置的列，然后隨機(jī)取其中一列來放置第k行的皇后。這就是Las Vegas的精髓！
*/
// Author: Tanky Woo
// Blog: www.WuTianQi.com
bool Queen::QueensLV(int stopVegas)
{
// 隨機(jī)放置n個(gè)皇后的拉斯維加斯算法
RandomNumber rnd; // 隨機(jī)數(shù)產(chǎn)生器
int k = 1; // 下一個(gè)放置的皇后編號(hào)
int count = 1;
// 1 <= stopVegas <= n 表示允許隨機(jī)放置的皇后數(shù)
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)]; // 隨機(jī)位置
}
return (count > 0); // count > 0表示放置位置成功
}
Main.cpp主文件：
/*
* Author: Tanky woo
* Blog: www.WuTianQi.com
* Date: 2010.12.9
* 拉斯維加斯(Las Vegas)算法解決N皇后問題
* 代碼來至王曉東《計(jì)算機(jī)算法設(shè)計(jì)與分析》
*/
#include "Queen.h"
#include "RandomNumber.h"
#include <iostream>
using namespace std;
bool nQueen(int n)
{
// 與回溯法結(jié)合的解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;
// 設(shè)置隨機(jī)放置皇后的個(gè)數(shù)
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表示完全實(shí)用隨機(jī)法解決問題。因此一定可以得到一組解。
注意書上說解決8皇后問題時(shí)，列出了一個(gè)不同stopVegas值時(shí)，所對(duì)應(yīng)的算法成功率，在stopVegas=8時(shí)，他寫著是0.1293，我個(gè)人認(rèn)為是錯(cuò)的。接下來我說下自己這么理解的原因：
首先，這個(gè)程序?yàn)楹螘?huì)造成有失敗的情況，那就是因?yàn)樵陔S機(jī)求出前stopVegas行成立時(shí)，不代表后面N-stopVegas行用回溯就可以成立，因?yàn)檫@不是一個(gè)徹底的回溯。它是從stopVegas+1行開始計(jì)算，回溯不成立最后返回時(shí)，也只停留在stopVegas。
而我們?cè)谕耆S機(jī)時(shí)，那么它就是反復(fù)調(diào)用隨機(jī)位置放置n個(gè)皇后的Las Vegas算法，直至放置成功。所以當(dāng)stopVegas=8時(shí)，他的成功率也應(yīng)該是100%。
另外在stopVegas=3時(shí)，成功率等于0.49，趨近于0.5，大家可以試試，基本上每運(yùn)行兩次會(huì)有一次回來結(jié)果。
如果上面我的理解有錯(cuò)，歡迎大家指出，我的博客(http://www.wutianqi.com/)。
下一篇我會(huì)寫《隨機(jī)化算法(5) — 蒙特卡羅(Monte Carlo)算法》。
Tanky Woo原創(chuàng)，歡迎轉(zhuǎn)載，轉(zhuǎn)載請(qǐng)附上鏈接，請(qǐng)不要私自刪除文章內(nèi)任何關(guān)于本博客的鏈接。
posted on 2010-12-15 14:28
Tanky Woo 閱讀(3281)
評(píng)論(0) 編輯 收藏 引用