一、问题背景
多皇后问题是一个经典的问题,在一个 N x N 的棋盘上放置 N 个皇后,使其不能互相攻击 (每行、每列、每一斜线上分别只能放置一个皇后) ,求解 N 皇后问题的复杂度随 N 呈指数级增加;
传统的求解方法采用基于回溯算法的策略,当 N 过大时不再适用,转而使用启发式算法求解,目前常见的启发式算法包括模拟退火法、遗产算法、蚁群算法等,这些算法引入了随机因素,一般能快速地找到满意解;
二、模拟退火法
2.1 模拟退火的原理
模拟退火法的原理和金属退火类似,在温度较高时更容易改变金属结构,在温度变低后结构趋于稳定,模拟退火的基本思想:
(1)初始化产生一个新解 S S S,以及温度 T T T;
(2)在 S S S 的邻域搜索,得到一个新解 S ′ S' S′;
(3)使用评估函数 f f f,得到 Δ t ′ = f ( S ) − f ( S ′ ) \Delta t' = f(S) - f(S') Δt′=f(S)−f(S′), f ( S ′ ) f(S') f(S′) 越低表示 S ′ S' S′ 距离最优解越接近;
(4)若 Δ t ′ > 0 \Delta t' > 0 Δt′>0,说明 S ′ S' S′ 要优于 S S S,我们接受该解, S ← S ′ S \leftarrow S' S←S′;
(5)若 Δ t ′ < 0 \Delta t' < 0 Δ