博文
皇后也疯狂：如何在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-皇后问题。
在该系列快速局部搜索算法中，每个解编码为整数(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
(2.1) If 交换 pi(i) 与 pi(j) 能减少冲突
(2.2) Then 交换 pi(i) 与 pi(j)
Until 解无冲突
End
在这里，我们介绍Rok Sosic和Jun Gu提出的一种快速局部搜索算法框架（见算法1） [1][2]。算法由一系列循环构成。在每个循环体内，首先生成一个随机排列作为初始解。该初始解一般会存在很多冲突。由于采用了排列结构来存储解，因此在行、列上不存在冲突，只需考虑如何减少在正对角线、负对角线方向上的冲突数。若该冲突数降到0，则表明得到了一个可行的合法解。在算法步骤（2）中，不断地检测是否存在有冲突的皇后，如果有则尝试将其与另外的皇后交换，如果交换后能降低冲突数，则执行该交换工作。注意到在同一条负对角线上所有的皇后满足行号与列号之和为常数，而正对角线上的所有皇后满足其行号与列号之差为常数。故此，每一条正对角线（或负对角线）可以维护对应的冲突数，总计2N-1个数据。由于每次交换两个皇后会涉及到8条对角线（交换前每个皇后有2条，交换后新位置上的每个皇后也有2条），因此算法步骤（2.1）中每次判断交换能否减少冲突的运行时间是常数级别的。N-皇后问题的最大冲突数为N-1，而步骤（2）每次运行时间复杂度为O(N2)且其成功运行至少能减少1次冲突，故此算法在一个随机解上的优化的最坏复杂度为O（N3）。当一个随机解不能优化且未能消除冲突时，算法将重新生成一个随机解，并进行消除冲突的局部搜索。有趣的是，在实际的运行中，随着皇后数的增加，需要使用的随机解数量却相应减少，当皇后数超过一定数量（比如10000），几乎每次只需要生成一个随机解就可以优化得到可行解。在算法1中，一个解的邻域中的解与当前解的差别只是有两个皇后的位置进行了交换。
在HP Pavilion dv1000笔记本电脑（Intel Celeron 1.6G, 2G内存）上，用VC6实现的算法1（代码见附件），在Windows XP环境下，可以在200秒左右的时间求解10万个皇后。通过分析可以发现，实际上该算法还有进一步改进的空间。在算法的步骤（2）中，采用了循环的方式来检查是否存在冲突。该步骤是相对低效的，如果能够把存在冲突的皇后记录下来，则该步骤可以显著加速。在后续的工作中，Rok Sosic和Jun Gu等人进一步作了改进，在1分钟的时间内可以求解300万个皇后的问题[3,4]。
算法1是反映局部搜索性能的一个生动例子。从该算法中，我们可以得到以下启示：
（1）解的结构是决定局部搜索性能的重要因素
在算法1中采用了排列的方式来定义解，从而可以保证在同一行、同一列上不存在冲突，而只需考虑对角线上的冲突。而若采用一个二维数组来表示解的话，则可能在同一行或者同一列上有冲突，问题的求解难度会相应增加。
（2）局部搜索可能陷入局部最优解陷阱
在算法1中，当一个随机解不能通过局部搜索消除所有的冲突时，采取了一种随机重启的解决办法，即重新生成一个随机解并优化。需要注意到的是，N-皇后问题实际上是一个比较特殊的例子，它的可行解的个数非常多，因此通过随机解的局部搜索比较容易求解。对于全局最优解个数很少的例子（比如大多数的旅行商问题），随机重启的效率并不高。这个时候则需要与一些全局搜索策略相结合，比如与遗传算法相结合，得到所谓的Memetic算法。或者，可以采取搜索空间切换的技术，在不同的算法之间切换，以跳出局部最优解陷阱。
--------------------------------------------------------------------------------------------
相关阅读：局部搜索算法
局部搜索是启发式算法中最简单的一种类型，具有实现简单，求解迅速等优点。在有些场合下，局部搜索也被成为“爬山”法。形象地说，是从山上某点开始，每次选择走向周围更低的点，直到周围点都更高为止（以最小化问题为例）。
算法2 给出了局部搜索的算法框架。从算法框架中可以发现，局部搜索算法包含两个基本操作：初始解生成，解的邻域定义。在初始解X生成后，算法将把其作为当前解X*，并在其邻域中寻找更好的解X'。在算法步骤（3），当邻域中有多个更好解时，局部搜索可以有不同的实现方法，比较常见的是选择邻域中遇到第一个更好解作为当前解，或者选择邻域中最好的更好解。
算法2 Local Search
输入: 实例
输出: 解X*
Begin
(1) 按照某种方法生成一个初始解X
(2) X* = X
(3) While X* 的邻域中有更好的解 X'
X* = X'
Endwhile
(4) 输出 X*
End
下面针对局部搜索算法的两个基本操作（初始解生成及邻域定义）进一步讨论。
（1）初始解生成
在局部搜索算法中，初始解是搜索的起点。常见的初始解生成方法包括随机解或者采用某种构造算法来获得初始解。比如在旅行商问题中，可以采用贪心法来构造初始解：从某个城市出发，每次都挑选最近的未访问过的城市，并将其标注为已访问，重复该过程知道完整的城市环路构造成功。
（2）解的邻域定义
解的邻域定义是局部搜索算法中的关键，也是需要算法设计人员精心研究的范畴。邻域的规模大小决定了局部搜索的收敛速度：当邻域规模较小时，局部搜索很快就可以达到收敛状态（即求得局部最优解）；当邻域规模较大时，局部搜索在邻域中的遍历时间将显著增长。极端的情形下，当邻域选择为整个解空间且采用的是邻域中最好解时，局部搜索就退化为一般的全局优化了。
参考文献
[1]Sosic, R.; Gu, J. A polynomial time algorithm for the N-Queens problem. ACM SIGART Bulletin, 1(3).
[2]Sosic, R.; Gu, J. Fast search algorithms for the n-queens problem. IEEE Transactions on Systems, Man and Cybernetics, 1991, 21(6): 1572 - 1576.
[3]Sosic, R.; Gu, J. 3,000,000 Queens in less than one minute. ACM SIGART Bulletin, 1991, 2(2).
[4]Sosic, R.; Gu, J. Efficient local search with conflict minimization: a case study of the n-queens problem. IEEE Transactions on Knowledge and Data Engineering, 1994, 6(5):661 - 668
附件：NQueens.zip （调用命令：NQueens xxx ,此处xxx为皇后个数）
[部分内容摘自即将出版的图书：《基于骨架的启发式算法理论及应用》]
https://blog.sciencenet.cn/blog-267533-535185.html
上一篇：超启发式算法：一种跨领域的问题求解模式
下一篇：IEEE Intelligence and Security Informatics (ISI) 2013
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
(2.1) If 交换 pi(i) 与 pi(j) 能减少冲突
(2.2) Then 交换 pi(i) 与 pi(j)
Until 解无冲突
End
在这里，我们介绍Rok Sosic和Jun Gu提出的一种快速局部搜索算法框架（见算法1） [1][2]。算法由一系列循环构成。在每个循环体内，首先生成一个随机排列作为初始解。该初始解一般会存在很多冲突。由于采用了排列结构来存储解，因此在行、列上不存在冲突，只需考虑如何减少在正对角线、负对角线方向上的冲突数。若该冲突数降到0，则表明得到了一个可行的合法解。在算法步骤（2）中，不断地检测是否存在有冲突的皇后，如果有则尝试将其与另外的皇后交换，如果交换后能降低冲突数，则执行该交换工作。注意到在同一条负对角线上所有的皇后满足行号与列号之和为常数，而正对角线上的所有皇后满足其行号与列号之差为常数。故此，每一条正对角线（或负对角线）可以维护对应的冲突数，总计2N-1个数据。由于每次交换两个皇后会涉及到8条对角线（交换前每个皇后有2条，交换后新位置上的每个皇后也有2条），因此算法步骤（2.1）中每次判断交换能否减少冲突的运行时间是常数级别的。N-皇后问题的最大冲突数为N-1，而步骤（2）每次运行时间复杂度为O(N2)且其成功运行至少能减少1次冲突，故此算法在一个随机解上的优化的最坏复杂度为O（N3）。当一个随机解不能优化且未能消除冲突时，算法将重新生成一个随机解，并进行消除冲突的局部搜索。有趣的是，在实际的运行中，随着皇后数的增加，需要使用的随机解数量却相应减少，当皇后数超过一定数量（比如10000），几乎每次只需要生成一个随机解就可以优化得到可行解。在算法1中，一个解的邻域中的解与当前解的差别只是有两个皇后的位置进行了交换。
在HP Pavilion dv1000笔记本电脑（Intel Celeron 1.6G, 2G内存）上，用VC6实现的算法1（代码见附件），在Windows XP环境下，可以在200秒左右的时间求解10万个皇后。通过分析可以发现，实际上该算法还有进一步改进的空间。在算法的步骤（2）中，采用了循环的方式来检查是否存在冲突。该步骤是相对低效的，如果能够把存在冲突的皇后记录下来，则该步骤可以显著加速。在后续的工作中，Rok Sosic和Jun Gu等人进一步作了改进，在1分钟的时间内可以求解300万个皇后的问题[3,4]。
算法1是反映局部搜索性能的一个生动例子。从该算法中，我们可以得到以下启示：
（1）解的结构是决定局部搜索性能的重要因素
在算法1中采用了排列的方式来定义解，从而可以保证在同一行、同一列上不存在冲突，而只需考虑对角线上的冲突。而若采用一个二维数组来表示解的话，则可能在同一行或者同一列上有冲突，问题的求解难度会相应增加。
（2）局部搜索可能陷入局部最优解陷阱
在算法1中，当一个随机解不能通过局部搜索消除所有的冲突时，采取了一种随机重启的解决办法，即重新生成一个随机解并优化。需要注意到的是，N-皇后问题实际上是一个比较特殊的例子，它的可行解的个数非常多，因此通过随机解的局部搜索比较容易求解。对于全局最优解个数很少的例子（比如大多数的旅行商问题），随机重启的效率并不高。这个时候则需要与一些全局搜索策略相结合，比如与遗传算法相结合，得到所谓的Memetic算法。或者，可以采取搜索空间切换的技术，在不同的算法之间切换，以跳出局部最优解陷阱。
--------------------------------------------------------------------------------------------
相关阅读：局部搜索算法
局部搜索是启发式算法中最简单的一种类型，具有实现简单，求解迅速等优点。在有些场合下，局部搜索也被成为“爬山”法。形象地说，是从山上某点开始，每次选择走向周围更低的点，直到周围点都更高为止（以最小化问题为例）。
算法2 给出了局部搜索的算法框架。从算法框架中可以发现，局部搜索算法包含两个基本操作：初始解生成，解的邻域定义。在初始解X生成后，算法将把其作为当前解X*，并在其邻域中寻找更好的解X'。在算法步骤（3），当邻域中有多个更好解时，局部搜索可以有不同的实现方法，比较常见的是选择邻域中遇到第一个更好解作为当前解，或者选择邻域中最好的更好解。
算法2 Local Search
输入: 实例
输出: 解X*
Begin
(1) 按照某种方法生成一个初始解X
(2) X* = X
(3) While X* 的邻域中有更好的解 X'
X* = X'
Endwhile
(4) 输出 X*
End
下面针对局部搜索算法的两个基本操作（初始解生成及邻域定义）进一步讨论。
（1）初始解生成
在局部搜索算法中，初始解是搜索的起点。常见的初始解生成方法包括随机解或者采用某种构造算法来获得初始解。比如在旅行商问题中，可以采用贪心法来构造初始解：从某个城市出发，每次都挑选最近的未访问过的城市，并将其标注为已访问，重复该过程知道完整的城市环路构造成功。
（2）解的邻域定义
解的邻域定义是局部搜索算法中的关键，也是需要算法设计人员精心研究的范畴。邻域的规模大小决定了局部搜索的收敛速度：当邻域规模较小时，局部搜索很快就可以达到收敛状态（即求得局部最优解）；当邻域规模较大时，局部搜索在邻域中的遍历时间将显著增长。极端的情形下，当邻域选择为整个解空间且采用的是邻域中最好解时，局部搜索就退化为一般的全局优化了。
参考文献
[1]Sosic, R.; Gu, J. A polynomial time algorithm for the N-Queens problem. ACM SIGART Bulletin, 1(3).
[2]Sosic, R.; Gu, J. Fast search algorithms for the n-queens problem. IEEE Transactions on Systems, Man and Cybernetics, 1991, 21(6): 1572 - 1576.
[3]Sosic, R.; Gu, J. 3,000,000 Queens in less than one minute. ACM SIGART Bulletin, 1991, 2(2).
[4]Sosic, R.; Gu, J. Efficient local search with conflict minimization: a case study of the n-queens problem. IEEE Transactions on Knowledge and Data Engineering, 1994, 6(5):661 - 668
附件：NQueens.zip （调用命令：NQueens xxx ,此处xxx为皇后个数）
[部分内容摘自即将出版的图书：《基于骨架的启发式算法理论及应用》]
https://blog.sciencenet.cn/blog-267533-535185.html
上一篇：超启发式算法：一种跨领域的问题求解模式
下一篇：IEEE Intelligence and Security Informatics (ISI) 2013
