人工智能导论实验——汉诺塔&八皇后问题
目录
实验目的及要求：
本项目要求能够理解人工智能的基本原理，理解问题归约法的原理和方法，掌握用问题归约表示问题的步骤，并能够实际问题给出具体的实现。
实验内容：
1.问题归约法的原理和方法
2.与或树表示问题的步骤
3.问题归约法的实现
一、汉诺塔问题
实验项目1：
实验要求：
1．形式化表示Hanoi问题，画出其规约图（即，与/或图）
2. 根据问题的形式化结果，结合prolog语言的特点，Prolog实现该问题求解；
实验步骤：
题目分析：
实现这个算法可以简单分为三个步骤：
①把n-1个盘子由柱1移到柱3；
②把第n个盘子由柱1移到柱2；
③把n-1个盘子由柱3移到柱2；
例如：
当n == 1时，
1.柱1—->柱2
sum = 1 次
当n == 2时，
2.柱1—->柱3
2. 柱1—->柱2
3. 4. 柱3—->柱2
sum = 3 次
当n == 3时，
4. 柱1—->柱2
5. 柱1—->柱3
6. 柱2—->柱3
7. 柱1—->柱2
8. 柱3—->柱1
9. 柱3—->柱2
10. 柱1—->柱2
sum = 7 次
其状态图如下：
prolog代码如下：
hanoi(N) :- move(N,left,center,right).
move(0,_,_,_) :- !.
move(N,A,B,C) :-
M is N-1,
move(M,A,C,B),
inform(A,B),
move(M,C,B,A).
inform(X,Y) :- write('Move from '), write(X), write(' to '), write(Y), write('.'), nl.
运行结果如下：
二、八皇后问题
实验项目2：
如何能在88 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇
后？为了到达此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。
通过实验，基本掌握逻辑编程的思想，了解逻辑编程与命令式编程的区别。
能够依据给定的事实以及规则编写代码，解决逻辑约束问题(CLP)。
实验要求：*
- 画出求解8皇后问题的递归回溯算法和迭代算法流程图。
- 画出状态树（任意解均可）。
- 参考华为《人工智能导论》实验手册，在华为云的ModelArts中用Python实现该问题的求解。
实验步骤：
算法介绍：
回溯算法：回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就”回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为”回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有”通用解题方法”的美称。
对于八皇后问题求解的递归算法，N-S图如下：
解题思路：
可以将 m 皇后问题的 m ×m 棋盘看成是矩阵，设皇后 a 和皇后 b 的摆放位置分别是( a，ya ) 和( b，yb ) ，那么，斜率为－1 的棋盘上的同一条斜线上，满足条件 a－ya = b－yb，斜率为 1 的棋盘上的同一条斜线上，满足条件 a+ya = b+yb，综合上述两种情况，m 皇后问题的解必须满足约束条件 | a－ b |≠| ya－yb |。
由于八皇后必须满足不在同一排，所以我们可以用一维数组存放皇后位置，如果啊a[i]，其中，i表示行，a[i]的值表示列。
首先，基本思路就是先摆第一个，再摆第二个，依此类推，如果第二个不符合条件，则调整第一个的位置（回溯）。简而言之，我们将8 * 8的棋盘看成是一个二维数组，首先将第一个棋子摆在[0][0]的位置。再将第二个摆在[1][0]的位置（因为第二个位置一定不能再摆在0开头的位置，否则一定在同一行），如果不合适再放在[1][1]的位置，依次类推，如果摆到[1][7]的位置还有冲突，则需要调整第一个棋子的位置至[0][1]，再依次尝试，这就是递归的基本原理。
另外一个需要解决的问题就是冲突检测，如何检查是否有冲突呢？我们的基本思路就是，每排只放一个，这样保证了不会有任意2个棋子在同一行（即第i个棋子摆在弟i行）。其次，每摆一个棋子后，我们用一个数组将其列数记下来，如column[i]表示第i个棋子摆放的列数，因此当我们摆放第i+1个棋子时就需要判断这个棋子是否和column这个数组中的0~i个元素有冲突，若没有则将column[i + 1]置为当前棋子摆放的列数。
流程图如下：（以N=4为例，一个可行解）
其状态树如下：
由以上算法归纳出第i行开始摆放皇后的流程图如下：
八皇后问题的状态空间树的实际大小：
举例：
例如，对于路径(1,3,0,2,4)，状态空间树上第2层的结点数（即x0的取值）为8；
因为x0=1，所以xl可取（相互不冲突）的列号只有5个；
因为xl=3，故x2可取的列号有4个……
所以，选择这条路径，状态空间树上实际生成的问题状态数目为：
1+8+8×5+8×5×4+8×5×4×3+8×5×4×3×2=1649
8-皇后问题解空间树的结点总数为
因此，需要实际生成的结点数目大约占结点总数的1.55%。
python实现如下：
def checkConflict(state,length,nextY):
nextX = length
for i in range(nextX):
if abs(nextY - state[i]) in (0, nextX-i):
return True
else:
pass
return False
def printState(state,num):
print("===============================================")
for i in range(num):
print(" ."*(state[i]) + " Q" + " ."*(num - 1 -state[i]))
return 0
def findState(state,length,num):
nextX = length
count = 0
for y in range(num):
if not checkConflict(state,length,y):
state[nextX] = y
if length == num-1:
printState(state,num)
count += 1
else:
findState(state,length+1,num)
else:
pass
return count
num = 10
state = [0]*num
findState(state,0,num)
思考题：
请简要描述下递归搜索的主要核心思想？
①递归
递归的主要思想是将一个给定的很大的问题，经过递归函数层层转化为与自己类型相似的小 问题，然后小问题十分好解决。递归的定义就是把问题向边界的转化的规则，递归一定会使 问题越来越简单，最后终止条件是题目给出，或直接简单算出。
递归算法解题通常有三个步骤：
1）分析问题、寻找递归：找出大规模问题与小规模问题的关系，这样通过递归使问题的规模逐渐变小。
2）设置边界、控制递归：找出停止条件，即算法可解的最小规模问题。
3）设计函数、确定参数：设计函数体中的操作及相关参数。
②搜索
搜索算法是利用计算机的高性能来有目的地穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。
相比于单纯的枚举算法有了一定的方向性和目标性。算法是在解的空间里，从一个状态转移（按照要求拓展）到其他状态，这样进行下去，将解的空间中的状态遍历，找到答案（目标的状态）。
状态(state)是对问题在某一时刻进展情况的数学描述，或者是数学抽象。
每一个状态都会是答案的一个”可能的”解。状态的转移就是问题从一个状态转移到另一个状态，这样就可以进行搜索的一步步延伸，最后要得到的解也是其中的一个状态。
搜索分为广度优先搜索和深度优先搜索：
广度优先搜索：
基本思想：从初始状态S 开始，利用规则，生成所有可能的状态。构成的下一层节点，检查是否出现目标状态G，若未出现，就对该层所有状态节点，分别顺序利用规则。
生成再下一层的所有状态节点，对这一层的所有状态节点检查是否出现G，若未出现，继续按上面思想生成再下一层的所有状态节点，这样一层一层往下展开。直到出现目标状态为止。
——在路径的寻找问题上用得比较多
具体过程：
1 每次取出队列首元素（初始状态），进行拓展
2 然后把拓展所得到的可行状态都放到队列里面
3 将初始状态删除
4 一直进行以上三步直到队列为空。
深度优先搜索：
基本思想：从初始状态，利用规则生成搜索树下一层任一个结点，检查是否出现目标状态，若未出现，以此状态利用规则生成再下一层任一个结点，再检查，重复过程一直到叶节点（即不能再生成新状态节点），当它仍不是目标状态时，回溯到上一层结果，取另一可能扩展搜索的分支。采用相同办法一直进行下去，直到找到目标状态为止。
具体实现过程
1 每次取出栈顶元素，对其进行拓展。
2 若栈顶元素无法继续拓展，则将其从栈中弹出。继续1过程。
3 不断重复直到获得目标状态（取得可行解）或栈为空（无解）。
Original: https://blog.csdn.net/weixin_47686861/article/details/123846438
Author: 来杯橙汁压惊
Title: 人工智能导论实验3——汉诺塔&八皇后问题
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/651812/
转载文章受原作者版权保护。转载请注明原作者出处！