from random import random
import numpy as np
from random import randint
import time
class SimulatedAnnealing:
"""
Find an optimal solution by decreasing the probability of selecting a random neighbour
as the temperature T decreases
"""
def __init__(self, queens, n):
self.queens = queens
self.n = n
# print initial board state
self.printBoard(self.queens, n)
# start timer
start = time.time()
self.anneal(n)
end = time.time()
# print board and runtime after solution is found
self.printBoard(self.queens, n)
print("Runtime:", end - start, "(seconds)")
def anneal(self, n):
currentCost = self.cost(self.queens, n)
# Continue to search until a goal node is reached
while self.cost(self.queens, n) != 0:
T = 1.0
#T0 = 1.0
T_min = 0.0001
alpha = 0.9
# Reduce the temperature until the threshold is reached
while T > T_min:
i = 1
# print the goal node cost and its queen locations
if currentCost == 0 and T <= T_min:
print('\r', "Cost:", currentCost, self.queens, end='\n', flush=True)
else:
print('\r', "Cost:", currentCost, self.queens, "queens:", n, end='', flush=True)
# Choose 100 random neighbours and apply the acceptance probability
while i <= 100:
# Find random neighbour
nextState = self.randomNeighbour(self.queens, n)
# Evaluate Cost of random neighbour
nextCost = self.cost(nextState, n)
# Determine acceptance probabiltiy for given current state and random neighbour
a = np.exp(-(nextCost - currentCost)/T)
# Select random neighbour if acceptance probability is greater than random value
if a > random():
self.queens = nextState
currentCost = nextCost
if currentCost == 0:
break
i += 1
if currentCost == 0:
break
# Decrease temperature
T = T*alpha
def randomNeighbour(self, queens, n):
queensTemp = queens[:]
# Select a random row and column for the random neighbour
i = randint(0, n-1)
j = randint(0, n-1)
queensTemp[i] = j
return queensTemp[:]
def cost(self, queens, n):
"""
Calculates the cost by counting the number of queen conflicts
"""
conflicts = 0
for i in range(n):
for j in range(i + 1, n):
if i != j:
# Horizontal axis
if queens[i] == queens[j]:
conflicts = conflicts + 1
# Diagonal Axis Positive
if abs(queens[i] - queens[j]) == abs(i - j):
conflicts = conflicts + 1
return int(conflicts)
https://blog.csdn.net/qq_20793791/article/details/106455546
看看这个流程图
您好，我是有问必答小助手，您的问题已经有小伙伴解答了，您看下是否解决，可以追评进行沟通哦~
如果有您比较满意的答案 / 帮您提供解决思路的答案，可以点击【采纳】按钮，给回答的小伙伴一些鼓励哦～～
ps:问答VIP仅需29元，即可享受5次/月 有问必答服务，了解详情>>>https://vip.csdn.net/askvip?utm_source=1146287632
非常感谢您使用有问必答服务，为了后续更快速的帮您解决问题，现诚邀您参与有问必答体验反馈。您的建议将会运用到我们的产品优化中，希望能得到您的支持与协助！
速戳参与调研>>>https://t.csdnimg.cn/Kf0y