《拉斯维加斯算法&蒙特卡罗算法_杨劲松》由会员分享，可在线阅读，更多相关《拉斯维加斯算法&蒙特卡罗算法_杨劲松（23页珍藏版）》请在金锄头文库上搜索。
1、华南师范大学计算机学院 计算机算法作者：杨劲松2013-6-21拉斯维加斯算法拉斯维加斯算法拉斯维加斯算法拉斯维加斯算法 Behavior can vary even on a fixed input;ALGORITHMINPUTOUTPUTRANDOM NUMBERS4/232013-6-21Probabilistic AlgorithmProbabilistic AlgorithmProbabilistic AlgorithmProbabilistic Algorithm5/232013-6-21Las VegasLas VegasLas VegasLas Vegas Algorithm
2、Algorithm Algorithm Algorithmvoid obstinateobstinateobstinateobstinate(Object x, Object y) bool success= false; while (!success) success=LV(x,y); Randomized algorithm Correct results6/232013-6-21N-Queens N-Queens N-Queens N-Queens Placing n queens on an nn chessboard. No two queens attack each other
3、.7/232013-6-21N-Queens N-Queens N-Queens N-Queens Solution vectorSolution vectorSolution vectorSolution vector：Xi represents the positions of the i-th queen in the xi-th column ，so，the solution vector is（X1,X2,X3,， Xn）Solution spaceSolution spaceSolution spaceSolution space：（：（：（：（n n n nn n n n）（1，
4、1，1，1，1），（1，1，1，1，2） ，（1，1，1，2，2），（n，n，n ，n，n）。8/232013-6-21N-Queens N-Queens N-Queens N-Queens The solution space treeThe solution space treeThe solution space treeThe solution space tree：rootrootrootroot1 1 1 12 2 2 22 2 2 21 1 1 12 2 2 22 2 2 21 1 1 12 2 2 22 2 2 23 3 3 33 3 3 3a11a11a11a11a12a12
5、a12a12a13a13a13a133 3 3 3.2 2 2 22 2 2 22 2 2 2a21a21a21a219/232013-6-21Las Vegas Does N-Queens Las Vegas Does N-Queens Las Vegas Does N-Queens Las Vegas Does N-Queens Solution1Solution1Solution1Solution1：Poor efficiencydo LV(x,y) try to place the queen in random column while(LV(x,y)is success)10/23
6、2013-6-21Las Vegas Does N-Queens Las Vegas Does N-Queens Las Vegas Does N-Queens Las Vegas Does N-Queens Solution2Solution2Solution2Solution2： combine the trace-back and Las Vegas algorithmdo /Placeing the part of queens with random raw LV(x,y,stopVegas); Backtracking(n- stopVegas) while(LV(x,y)is s
7、uccess)11/232013-6-21Las Vegas Does N-Queens Las Vegas Does N-Queens Las Vegas Does N-Queens Las Vegas Does N-Queens step: the number of randomly placed queen p: success probability s: the average number of nodes search access for a successfulSolution2Solution2Solution2Solution2： combine the trace-b
8、ack and Las Vegas algorithmthe the the the efficiency efficiency efficiency efficiency with with with with different step different step different step different step 12/232013-6-21Las Vegas Does N-Queens Las Vegas Does N-Queens Las Vegas Does N-Queens Las Vegas Does N-Queens Solution3Solution3Solut
9、ion3Solution3： backtrack n steps according failtimes do LV(x,y,stopVegas); Backtracking(n-stopVegas) .if(fail) failtimes+;trace-back(failtimes) while(LV(x,y)is success)13/232013-6-21Las Vegas Does N-Queens Las Vegas Does N-Queens Las Vegas Does N-Queens Las Vegas Does N-Queens Solution3Solution3Solu
10、tion3Solution3： backtrack n steps according failtimes do LV(x,y,stopVegas); Backtracking(n-stopVegas) .if(fail) failtimes+;trace-back(failtimes) while(LV(x,y)is success)failtimes =1failtimes =1failtimes =1failtimes =114/232013-6-21Las Vegas Does N-Queens Las Vegas Does N-Queens Las Vegas Does N-Quee
11、ns Las Vegas Does N-Queens Solution3Solution3Solution3Solution3： backtrack n steps according failtimes do LV(x,y,stopVegas); Backtracking(n-stopVegas) .if(fail) failtimes+;trace-back(failtimes) while(LV(x,y)is success)failtimes =2failtimes =2failtimes =2failtimes =215/232013-6-21Las Vegas Does N-Que
12、ens Las Vegas Does N-Queens Las Vegas Does N-Queens Las Vegas Does N-Queens Solution3Solution3Solution3Solution3： backtrack n steps according failtime do LV(x,y,stopVegas); Backtracking(n-stopVegas) .if(fail) failtimes+;trace-back(failtimes) while(LV(x,y)is success)failtimes =2failtimes =2failtimes
13、=2failtimes =216/232013-6-21Las Vegas Does N-Queens Las Vegas Does N-Queens Las Vegas Does N-Queens Las Vegas Does N-Queens step: the number of randomly placed queen p: success probability s: the average number of nodes search access for a successfulThe efficiency with different step solution2soluti
14、on2solution2solution2solution3solution3solution3solution317/232013-6-21Las Vegas Does N-Queens Las Vegas Does N-Queens Las Vegas Does N-Queens Las Vegas Does N-Queens Solution4Solution4Solution4Solution4： random permutation vectors8 8 8 81 1 1 12 2 2 23 3 3 37 7 7 74 4 4 46 6 6 6 a random permutatio
15、n vectors two vector flags for diagonal attacks18/232013-6-21Las Vegas Does N-Queens Las Vegas Does N-Queens Las Vegas Does N-Queens Las Vegas Does N-Queens Solution5Solution5Solution5Solution5： GridSearch Retain information about cell1 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1
