这两天在写AI的课程实验，趁刚刚完结实验代码，脑海中还有些思路，在此简单总结一下。
目录
问题描述
2N皇后问题：给定一个n*n的棋盘。现要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。请尽量快地给出一组可行解。
关于N皇后问题
N皇后问题是一个很经典的问题，在大家最初学习算法的时候都有讨论过。回溯法是经典的解法，但是随着N的增大，其复杂度的增加呈指数增长。哪怕N只是为100，使用回溯解法的话，运行也要相当久的时间。
简单分析
对于2N皇后问题，很多同学的第一想法可能是两次求解N皇后问题，且第二次求解时为摆放位置设限。然而，这种做法不免显得过于繁琐。
我们在这里，不妨先简单地分析了一下几种情况：
1. 当N为偶数时：其实只要求得一组可行解即可，另外一组可行解可以由当前解沿N*N矩阵的中轴线作对称变换得到。因为N为偶数，所以不会存在黑白皇后位置冲突的情况。
例如：N=4时，求得一组可行解为：3 1 4 2，按着这个思路，变换得到另一组可行解为：2 4 1 3。可以判断，这样的两组解合并起来是符合题目要求的。
2. 当N为奇数时：沿中轴线对称的方式不再可行，因为肯定有一个皇后会落在中轴线上。此时，可以考虑通过中心点作点对称的情况。
这里要注意，如果求得的可行解存在关于中心点对称的皇后摆放(或有皇后位于中心点)，那么此解不合要求，需要重新再求；直到没有两个皇后的位置是关于中心点对称的，另一组解可以通过对当前解关于中心点作点对称变换得到。
例如，N=5时，求得一组可行解为：2 4 1 3 5，按着这个思路，变换得到另一组可行解为：1 3 5 2 4。可以判断，这样的两组解合并起来是符合题目要求的。
从上可以看出，其实2N皇后问题并不需要二次求解N皇后，在大多数情况下只需求得一组可行解即可。
爬山算法
在介绍爬山算法之前，我觉得很有必要先弄清楚什么是局部搜索。
局部搜索
从数学层面来理解，局部搜索是一种解决最优化问题的启发式算法。
对于某些计算起来非常复杂的最优化问题，比如各种 NP 完全问题，要找到最优解所需要的时间会随问题规模的增大呈指数增长，因此诞生了各种启发式算法来退而求次地寻找局部最优解，而局部搜索算法就是其中的一种算法。
局部搜索算法从某一状态(而不是多条路径)出发，通常只移动到与当前状态相邻的状态。而在典型情况下，搜索的路径是不保留的。尽管局部搜索算法不是系统化的求解方法，但是它有几个关键的优点：
1. 占用很少的内存，通常情况下容量是常数级别的。
2. 经常能在不适合系统化算法的很大或者无限的（连续的）状态空间中快速找出合理的解。
爬山算法简介
爬山算法属于局部搜索算法的一份子，因此是一种解决最优化问题的启发式算法。
在实际运用中，爬山算法不会前瞻与当前状态不直接相邻的状态，只会选择比当前状态价值更好的相邻状态，所以简单来说，爬山算法是向价值增长方向持续移动的循环过程。
由于它的贪婪特性，使得在解决问题中容易陷入局部极大值(Local maxima，指一个比所有邻居状态价值要高但是比全局最大值要低的状态)，我们能采取随机重启(Random restart)以及模拟退火(Simulated annealing)的方法来改进。本文的主要涉及的就是这两种算法。
先在这里简单地说一下它们之间的区别，主要在于如何选择下一状态以及如何有效地得到全局最优解：
1. 随机重启爬山算法：
求解过程中，当得到了局部极大值时，如果不是全局最优解，则随机生成初始状态，重新求解，直到得到全局最优解。
2. 模拟退火爬山算法：
基于随机爬山算法，允许在随机选择相邻状态的时候有概率地选择价值更小的状态。在初期，向低价值状态移动的概率高，随着时间流逝该概率会越来越低。(温度逐渐降低，即"退火"。)
算法实现与关键优化
初始化
不同于一般的随机初始化。我实现时采用的初始化方式为：先依次为每一行的对应列摆上皇后，如第i 行，那么皇后就摆在第i 列，之后再随机选择交换皇后所在列。
这样做的优点是可以保证在任一时刻，每一行每一列都只有一个皇后，大大缩小了搜索范围，节省了程序运行时间。(从我的程序运行耗时可以明显看出这一策略的优越性。)
具体的实验代码如下：
/*初始化函数：在每行每列放置一个皇后*/
void generate_status(int* status) {
for (int i = 0; i < N; i++) {
status[i] = i;
}
/*随机交换*/
srand((unsigned)time(NULL));
for (int i = 0; i < N; i++) {
int r = rand();
r = r % N;
swap(status[r], status[N - r - 1]);
}
}
评价函数
对于每一个状态，需要有一个评价函数对其进行估值评价。在此，我选用冲突数作为评价指标，存在冲突数越多的状态，其评价就越差。显然，最优解的评价结果为0，即不存在冲突。
为了进一步优化实验运行效果，此函数我设置为内联函数。
具体的实验代码如下：
/*评价函数：返回摆放状态的冲突数*/
inline int evaluate(int* status, CollisionList& collision_list) {
collision_list.clear();
int num = 0;
for (int i = 0; i < N; i++) {
for (int j = i+1; j < N; j++) {
int offset = j - i;
if (abs(status[i] - status[j]) == offset) {
collision_list.push_back(j);
num += 1;
}
}
}
return num;
}
尝试交换函数
对传入的状态进行交换尝试，如果交换后的状态评价结果小于当前传入状态，就进行交换，将新状态返回；否则，不交换，直接返回原先的状态。
对于模拟退火算法，这里就需要加上一个temperature变量，当邻居状态不是更优，但是温度够高,达到了振荡指标时，也可以进行状态转换。同时，temperature值是在不断减小的。
寻找下一个更优状态的函数
对于传入的状态，不断调用尝试交换函数，直到获得了冲突数更小的新状态，即为一个更优状态，将此状态的冲突数作为返回值返回。
N皇后解法的主函数
这个函数的主要实现的就是调用初始化函数进行初始化，然后持续迭代调用寻找下一个更优状态函数，直到返回的冲突数指标为0时，可以将此状态作为求得的一组可行解再交还给main函数。
算法效率比较
下面就是见证奇迹的时刻啦~~~
笔者特意写了一份回溯法求解N皇后问题的程序，作为对比参照。
N=10时：
回溯法求解10皇后问题
爬山算法求解10皇后问题
额，好像N设的有点小了。。。。来个大点的。。。。
N=20吧：
爬山算法求解20皇后问题
什么？回溯法？这。尴尬了。。等了好久都没跑出来结果。。。
退而求其次，我跑了个N=16的回溯法给大家瞧瞧，不过也是让我足足等了5分多钟：
回溯法求解16皇后问题
可见当N>10以后，爬山算法的优越性尽显无疑，我于是又给它上了几个更大的数，具体的运行效果如下：
爬山算法求解100皇后问题
爬山算法求解300皇后问题
爬山算法求解1000皇后问题
爬山算法 N=1000的耗时也不过是回溯法 N=16情况运行耗时的一半！
AI的强大之处可以略窥一二了吧~
网友评论