文档介绍：皇后也疯狂:如何在 1 分钟内摆放 300 万个皇后我们知道, 在国际象棋中, 皇后可以在行、列和对角线上行走。那么考虑一下: 如何在一个 N*N 的棋盘上放置 N 个皇后, 使得每行、每列和每条对角线上不存在 2 个或 2 个以上的皇后。这实际上就是经典的 N- 皇后问题。 N- 皇后问题是人工智能领域中一个经典的组合问题,在包括 VLSI 和交通控制等问题上具有广泛的应用。图 1 给出了包含 4 个皇后的 4- 皇后问题的例子。图1 (a) 给出了一个违反了约束的解的例子。可以发现, 每一行、每一列上均只有 1 个皇后, 但是第 1 列和第 2 列的两个皇后在正对角线方向上违反了约束。而图 1 (b) 给出了一个合法解,在每一行、每一列均只有 1 个皇后,而且在正对角线、负对角线方向上最多只有一个皇后。 N- 皇后问题是我们在数据结构和算法类的课程上经常遇到的一个问题,它的经典求解方法是采用回溯的方法, 可以产生所有的可行解, 但是实际上运行时间非常长, 能够解决的问题规模相对非常小。有没有一种方法, 可以在极短的时间内求解上百万个皇后的 N- 皇后问题? 答案是可以,用局部搜索! Rok Sosic 和 Jun Gu (顾钧)在 20 余年前提出的系列快速局部搜索算法可以在极短的时间内,求解百万量级的 N- 皇后问题。(a) 违反约束的解(b) 一个合法解图 1. 4- 皇后的例子在该系列快速局部搜索算法中,每个解编码为整数(1, 2, 3, ..., N) 上的一个排列 pi(1), pi(2), pi(3),...,pi(N) , 表示在第 i 行上面的皇后的列号是 pi(i) 。在这种解的表示方法下, 每个解能确保在每行、每列上恰好只有一个皇后。因此, 在快速局部搜索算法中仅需考虑如何避免在正对角线、负对角线方向上出现 2 个或者 2 个以上的皇后。算法 1 Local Search for N-Queens 输入: N- 皇后实例输出:解 Begin Do (1) 产生一个随机解 pi (2) for all i, j: where 皇后 pi(i) 或 pi(j) 有冲突 do () If 交换 pi(i) 与 pi(j) 能减少冲突() Then 交换 pi(i) 与 pi(j) Until 解无冲突 End 在这里, 我们介绍 Rok Sosic 和 Jun Gu 提出的一种快速局部搜索算法框架( 见算法 1) [1][2] 。算法由一系列循环构成。在每个循环体内, 首先生成一个随机排列作为初始解。该初始解一般会存在很多冲突。由于采用了排列结构来存储解, 因此在行、列上不存在冲突, 只需考虑如何减少在正对角线、负对角线方向上的冲突数。若该冲突数降到 0, 则表明得到了一个可行的合法解。在算法步骤( 2 )中,不断地检测是否存在有冲突的皇后,如果有则尝试将其与另外的皇后交换, 如果交换后能降低冲突数, 则执行该交换工作。注意到在同一条负对角线上所有的皇后满足行号与列号之和为常数, 而正对角线上的所有皇后满足其行号与列号之差为常数。故此,每一条正对角线(或负对角线)可以维护对应的冲突数,总计 2N-1 个数据。由于每次交换两个皇后会涉及到 8 条对角线( 交换前每个皇后有 2条, 交换后新位置上的每个皇后也有 2条), 因