人工智能常见知识点④

(一) 什么是N皇后问题？

答：N皇后是指在一个N*N的棋盘上放置N个皇后，使得每一个皇后都不能互相攻击，即任意两个皇后都不能处于同一行，同一列或同一斜线上。

(二) 给出七皇后的一个解

(三) 什么是爬山法？爬山法存在的哪些问题？

答：爬山算法是指每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。实际是深度优先搜索算法的改进，爬山法能很快朝着解的方法进展。爬山算法通常在最佳后继的集合中随机选择一个进行扩展。也就是说一直向增加的方向持续移动，将会在到达一个“峰顶”时终止，并且在相邻状态中没有比他更高的值。爬山法不需要维护搜索树，因此当前节点的数据结构只需要记录当前状态和它的目标函数的值。

存在问题：不会预测与当前状态不直接相邻的那些状态的值。并且会陷入局部最优解，而不一定能找到全局最优解。

(四) 启发式耗散函数h 是可以彼此攻击的皇后对的数量，不管中间是否有障碍，计算下图八皇后的耗散函数值h,并列出互相冲突的皇后对。

解：

互相冲突的皇后对如下：

第一列：（5，1）--- （6，2）（7，3）（5，5）

第二列：（6，2）--- （7，3）（4，4）（6，6）（6，8）

第三列：（7，3）--- （5，5）（7，7）

第四列：（4，4）--- （5，5）（6，6）（7，7）

第五列：（5，5）--- （6，6）（7，7）

第六列：（6，6）--- （7，7）（6，8）

第七列：（7，7）--- （6，8）

因此 h = 3 4 2 3 2 2 1 = 17

(五) 爬山法算法通常在最佳后继的集合中随机选择一个进行扩展。给出上图最佳后继之一扩展后的耗散函数值h和八皇后的图。

解：观察上图可以知道，最佳后继之一扩展后的耗散函数值h = 12;

因此我们将第二列的Q移动到第二列第一行，如下图：

下面是上图互相冲突的皇后对：

第一列：（5，1）--- （7，3）（5，5）

第二列：（6，1）---

第三列：（7，3）--- （5，5）（7，7）

第四列：（4，4）--- （5，5）（6，6）（7，7）

第五列：（5，5）--- （6，6）（7，7）

第六列：（6，6）--- （7，7）（6，8）

第七列：（7，7）--- （6，8）

因此 h = 2 0 2 3 2 2 1 = 12

(六) 如果想找到全局最大值，怎么改进爬山法？

答：继续前进—侧向移动，设置允许连续侧向移动的次数限制。最终把每一个局部最优解作对比，即可获得全局最优解。

我正在参与2024腾讯技术创作特训营第五期有奖征文，快来和我瓜分大奖！