文档介绍：算法分析与复杂性理论
用拉斯维加斯算法解决n皇后问题
s20130791
王晓星
随机化算法的基本特征是对所求解问题的同一实例用同一随机化算法求解两次可能得到完全不同的效果。这两次求解所需的时间甚至所得到的结果可能会有相当大的差别。
一般情况下,可将随机化算法大致分为4类:
数值随机化算法
蒙特卡罗算法
拉斯维加斯算法
舍伍德算法
随机化算法
定义:不返回错误答案的概率算法
算法可能承认失败也没什么关系,只需在在输入上不断尝试,直到成功为止。
算法偶尔会有失败,但存在一个策略,它比失败时重新启动整个计算这种做法更好。
拉斯维加斯算法
利用随机来指导解的搜索,即使做了个不宜的选择,也可以保证正确的解,因为这样会导致算法进入绝境,这样就会报告在这一次运行中无法得到解,然后重新启动算法,直到得到正确的结果。
得到正确解的概率随着计算时间增加而提高。对于所求解问题的任一实例,用同一LV算法反复对其求解足够多次,可使求解失效的概率任意小。
LV算法基本思路
1、八皇后问题
①完全回溯法
用回溯法解n皇后问题时,用完全n叉树表示解空间。可行性约束place剪去不满足行、列和斜线约束的子树。
如右图(四皇后):
LV算法具体应用分析
②完全LV算法
对于八皇后问题的任何一个解而言,每一个皇后在棋盘上的位置无任何规律,不具有系统性,而更像是随机放置的.
由此想到可采用LV算法,满足新放置的皇后与已放置的皇后互不攻击前提下,在棋盘上相继的各行中随机地放置皇后,直至8个皇后均已相容地放置好,或已没有下一皇后可放置位置时为止.
7
③回溯算法与lv算法混合使用
先在棋盘的前若干行中随机地放置皇后,(即设定stopvegas的值)然后在后继行中用回溯法继续搜索,直至找到一个解或宣告失败.
随机放置的皇后越多,后继回溯搜索所需的时间就越少,但失败的概率就越大.
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
stopvegas = 3
random
backtrack
运行算法
8
运行结果
stopVegas p s e t
0
1
2
3
4
5
6
7
8
完全回溯法
LV和回溯混合效
率最高的情况
完全LV算法
9
分析:
①完全回溯法比LV算法在解八皇后问题时效率低得多; ②LV算法和回溯的混合使用有利于提高解八皇后的效率。
10
LV算法具体应用分析
2、N皇后问题
下面是n取不同值时效率对比情况:
随着n值的增加,与回溯法相比,使用LV算法的高效率性逐渐明显。