使用拉斯维加斯算法求解八后问题,并编程实现;随机放置0-8个后,每种情况至少运行100次,并统计成功求出解的概率(记为p),成功求出解时需要访问的结点数的平均值(记为s),未能成功求出解时需要访问的结点数的平均值(记为f)
时间: 2024-02-16 11:01:19 浏览: 92
好的,我可以给您提供一个基本的八后问题求解代码,使用拉斯维加斯算法:
```python
import random
def conflict(state, nextX):
nextY = len(state)
for i in range(nextY):
if abs(state[i] - nextX) in (0, nextY - i):
return True
return False
def queens(num = 8, state = ()):
for pos in range(num):
if not conflict(state, pos):
if len(state) == num - 1:
yield (pos,)
else:
for result in queens(num, state + (pos,)):
yield (pos,) + result
def las_vegas_queens(num = 8):
tries = 0
successes = 0
visited_nodes_s = 0
visited_nodes_f = 0
for i in range(100):
state = ()
visited_nodes = 0
# 随机放置皇后,最多放置 num 个
for j in range(random.randint(0, num)):
state += (random.randint(0, num-1),)
# 求解
while True:
visited_nodes += 1
try:
queen = next(queens(num, state))
successes += 1
visited_nodes_s += visited_nodes
break
except StopIteration:
tries += 1
visited_nodes_f += visited_nodes
break
print("成功求解概率:", successes/100)
print("成功求解时访问的结点数平均值:", visited_nodes_s/successes)
print("未能成功求解时访问的结点数平均值:", visited_nodes_f/(100-successes))
las_vegas_queens(8)
```
这段代码中,`queens()`函数是用来求解八后问题的基础函数,它返回一个生成器,每次生成一个元组,表示一组合法的放置方案。`conflict()`函数用来检查当前放置方案是否合法。`las_vegas_queens()`函数则是使用拉斯维加斯算法求解八后问题的具体实现,它使用`queens()`函数来求解,直到找到一组合法的放置方案为止。在`las_vegas_queens()`函数中,我们进行了 100 次随机放置和求解,统计成功求解的概率以及成功求解时和未能成功求解时访问的结点数的平均值。
您可以通过调用`las_vegas_queens()`函数来进行测试。
阅读全文