在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问一共有多少种摆法。
分别用递归回溯算法与遗传算法实现，代码如下
递归回溯解八皇后问题
import numpy
def findQueen(column):
if column > 7:
global count
count+=1
print(matrix)
return
else:
for row in range(8):
if check(row,column):
matrix[row][column]=1
arr[column]=row
findQueen(column+1)
matrix[row][column]=0
arr[column]=0
def check(row,column):
for k in range(len(arr)):
if k >= column:
return True
if arr[k] == row or abs(arr[k] - row) == abs(k - column):
return False
if __name__ == '__main__':
count = 0
matrix = numpy.zeros((8,8),dtype=int)
arr = numpy.zeros(8,dtype=int)
findQueen(0)
print(count)
遗传算法解八皇后问题
import copy
import random
import math
种群大小
population_size = 8
父种群的编码列表
parent = []
子种群的编码列表
children = []
父种群每个个体的适应度
parent_fitness = []
子种群每个个体的适应度
children_fitness = []
初始化个体
def initial_individual():
# 个体的编码
individual = []
# 8个编码
for i in range(8):
a = random.randint(0, 7)
individual.append(a)
# 计算生成的个体的适应度
fit_score = update_fitness_score(individual)
# 加入到种群中
parent_fitness.append(fit_score)
parent.append(individual)
return
更新适应度函数
def update_fitness_score(individual):
value = 0
for i in range(8):
for j in range(i + 1, 8):
if individual[i] != individual[j]:
x = j - i
y = abs(individual[i] - individual[j])
if x != y:
value += 1
return value
初始化1个种群,种群大小为population_size
def initial_population():
for i in range(population_size):
initial_individual()
return
选择出一个父本
def select():
# 所有个体的适应度之和
total_score = 0
for fit in parent_fitness:
total_score += fit
# 轮盘赌中的数
num = random.randint(0, total_score)
# 前面的适应度之和
front_score = 0
for i in range(population_size):
front_score += parent_fitness[i]
# 如果此时前面的适应度之和大于生成的随机数，那么该数必定落在编号为 i 的个体上
if front_score >= num:
return i
变异
def mutation(change_individual):
# 第pos个基因发生变异
pos = random.randint(0, 7)
# 改变的值
change = random.randint(0, 7)
change_individual[pos] = change
return change_individual
交叉产生后代
def hybridization():
# 选择两个父本
first = select()
second = select()
selected_parents = copy.deepcopy([parent[first], parent[second]])
# 交换从pos1到pos2的基因
pos1 = random.randint(0, 6)
pos2 = random.randint(0, 6)
# 保证pos1 pos2:
pos1, pos2 = pos2, pos1
# 交叉
tmp = selected_parents[0][pos1:pos2]
selected_parents[0][pos1:pos2] = selected_parents[1][pos1:pos2]
selected_parents[1][pos1:pos2] = tmp
# 一定的概率发生变异,假设概率为0.5
may = random.random()
if may > 0.5:
selected_parents[0] = mutation(selected_parents[0])
may = random.random()
if may > 0.5:
selected_parents[1] = mutation(selected_parents[1])
# 更新适应度
first_fit = update_fitness_score(selected_parents[0])
second_fit = update_fitness_score(selected_parents[1])
# 加入到子代中
children.append(selected_parents[0])
children.append(selected_parents[1])
children_fitness.append(first_fit)
children_fitness.append(second_fit)
return
初始化种群
initial_population()
计算迭代次数
count = 0
not a number
find = float('nan')
while True:
count += 1
if count % 1000 == 0:
print('第%d' % count + '次迭代')
# 杂交population_size/2次产生population_size个后代
for k in range(population_size // 2):
hybridization()
# 如果某个个体适应度达到28，说明此时找到了一个解
for k in range(population_size):
if children_fitness[k] == 28:
# 记录解的位置
find = k
break
if not math.isnan(find):
break
# 将子代种群放入父代中作为新的父代，子代清空
parent[0:population_size] = children[0:population_size]
parent_fitness[0:population_size] = children_fitness[0:population_size]
children = []
children_fitness = []
此时找到满足要求的子代个体
res = children[find]
print(res)
构造棋盘
res_queen = [[0 for i in range(8)] for j in range(8)]
for t in range(8):
res_queen[res[t]][t] = 1
将棋盘打印
print("找到结果：")
for t in range(8):
print(res_queen[t])
Original: https://www.cnblogs.com/left23333/p/16347767.html
Author: Left23333
Title: Python实现经典算法八皇后问题
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/582412/
转载文章受原作者版权保护。转载请注明原作者出处！