实验一 八数码问题
一、 实验目的
该课程的教学应贯彻理论与实践相结合的原则，为学生所学到的理论提供实践的场所，通过实验课程中具体问题的求解达到深入了解并掌握的目的。
二、 实验环境
微型计算机，操作系统为windows7或Windows10系统，编程工具学生可以自由选择Visual Studio、Java、Python（建议Anconda发行版）和Matlab等。
三、 实验内容
基于图搜索技术的八数码问题求解
问题描述：八数码，在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。
内容提要：分别用广度优先搜索策略、深度优先搜索策略和启发式搜索算法（至少两种）求解八数码问题；分析估价函数对启发式搜索算法的影响；探究讨论各个搜索算法的特点。
实验步骤：
- 随机生成一个八数码问题分布，设计一个可解的目标状态（要求棋盘9个位置都不同）。
- 分别用广度优先搜索策略、深度优先搜索策略和至少两种启发式搜索算法求解八数码问题
- 分析估价函数对启发式搜索算法的影响。
- 探究讨论各个搜索算法的特点。
- *扩展选做题：从初始状态到目标状态的变换，符合什么规律才可解（提示参考：逆序数）
四、 实验原理
宽度度优先搜索：
如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索。这种搜索是逐层进行的，在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。
深度优先搜索：
属于图算法的一种，是一个针对图和树的遍历算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次
有序搜索算法1：
令f(n) 表示节点n的估价函数值，估算节点希望程度的量度。本次实验选择的f(n)的函数形式为：
其中, g(n)为初始节点到当前节点的路径长度(深度), h(n)为当前节点”不在位”的将牌数。
有序搜索（ordered search），即最好优先搜索, 选择Open表中具有最小f值的节点作为下一个要扩展的节点。
有序搜索算法2:
其中g(n)为初始节点到当前节点的路径长度(深度), h(n)为当前状态数字所在位置和目标状态该数字所在位置进行相减取绝对值，依次获得8个数（’ ‘表示空位，不进行计算）的差值，相加所得即为h(n)的值。
五、 实验步骤
宽度优先搜索：
①初始化八数码的初始状态和目标状态
②实例化State类对象s1
类State的构造函数为：
③用对象s1调用类State内的函数solve()
solve()函数代码如下：
其实现的流程图如下：
其中generateSubStates()函数的定义如下：
④输出该搜索算法所访问的结点以及结点总数：
⑤输出找到的路径所经过的结点以及结点数：
深度优先搜索：
深度优先搜索的主要执行步骤与宽度优先搜索的大致相同
除了类State的构造函数和solve()函数和宽度优先搜索的有所区别：
①类State的构造函数
多了个属性depth,用来记录结点的深度值
②类State的solve()函数：
该函数的实现流程图如下：
有序搜索算法1：
主要步骤也与前面的算法大致相同：
该算法的启发函数：
其中, g(n)为初始节点到当前节点的路径长度(深度), h(n)为当前节点”不在位”的将牌数。
除了类State的构造函数和solve()函数有所区别：
①类State的构造函数
多了三个属性depth,num,cost.初始化数值都为0
②类State的solve()函数：
该函数的实现流程图如下：
其中函数calCost()的定义如下：
有序搜索算法2：
有序搜索算法2与有序搜索算法1除了函数calCost()有所不同，其他处代码一致
calCost()函数定义如下：
六、 实验结果分析
实验结果：（只截取结点个数的结果，不一一展示每个节点是什么）
宽度优先算法：
深度优先算法（由于访问的结点太多，就不一一截取访问的结点，直接给出结点数）
有序搜索算法1：
有序搜索算法2：
分析：（不同算法的区别）
①深度优先搜索算法找到的路径经过的结点数为9，其他算法找到的路径所经过的结点数都为5； 由于DFS算法是对每一个可能的分支路径深入到不能再深入为止，所以找到的路径不一定是最短的路线。在我们固定了最大能深入的深度为10的情况下，结点数为9。固定最大深度为100时，路径结点数变为了95
②A算法在盲目搜索（DFS,BFS）的基础上，会对结点表进行一个排序，使用估价函数去评价。目标明确，迅速找出一个尽可能最优的局部最优解。从实验结果中两个有序搜索算法访问的结点数分别为19和15，以及BFS算法访问的结点数26和DFS算法访问的结点数301进行比较，可以发现带启发策略的算法要比盲目搜索算法的访问结点数少，搜索效率更高
③A算法效率高于DFS算法和BFS算法，但是A*算法（有序搜索）也有缺点，不能搜索所有解，当需要搜索所有能到达终点的路径时，往往只能使用DFS与递归来实现
不同启发策略对实验效果的影响
g(n)默认为当前结点的深度
可以看到，当h(n)=0时，A算法等价于宽度优先搜索，此搜索得到的路径必定最优，消耗时间最多；当h(n)!=0、g(n)!=0时，h(n)的选择决定了搜索到的路线是否最优，效率是否更高
七、 实验源代码
eightNum.py （BFS算法）
import numpy as np
class State:
def __init__(self,state,directionFlag=None,parent=None):
self.state=state
self.direction=['up','down','right','left']
if directionFlag:
self.direction.remove(directionFlag)
self.parent=parent
self.symbol=' '
def getDirection(self):
return self.direction
def getEmptyPos(self):
position=np.where(self.state==self.symbol)
return position
def generateSubStates(self):
if not self.direction:
return []
subStates=[]
boarder=len(self.state)-1
row,col=self.getEmptyPos()
if 'left' in self.direction and col > 0:
s = self.state.copy()
temp = s.copy()
s[row, col] = s[row, col - 1]
s[row, col - 1] = temp[row, col]
news = State(s, directionFlag='right', parent=self)
subStates.append(news)
if 'up' in self.direction and row > 0:
s = self.state.copy()
temp = s.copy()
s[row, col] = s[row-1, col]
s[row-1, col] = temp[row, col]
news = State(s, directionFlag='down', parent=self)
subStates.append(news)
if 'right' in self.direction and col < boarder:
s = self.state.copy()
temp = s.copy()
s[row, col] = s[row, col +1]
s[row, col + 1] = temp[row, col]
news = State(s, directionFlag='left', parent=self)
subStates.append(news)
if 'down' in self.direction and row <boarder:
s = self.state.copy()
temp = s.copy()
s[row, col] = s[row+1, col]
s[row+1, col] = temp[row, col]
news = State(s, directionFlag='up', parent=self)
subStates.append(news)
return subStates
def solve(self):
openTable=[]
closeTable=[]
openTable.append(self)
while len(openTable)>0:
n=openTable.pop(0)
closeTable.append(n)
subStates=n.generateSubStates()
path=[]
for s in subStates:
if(s.state==s.answer).all():
path.append(s)
while s.parent and s.parent!=originState:
path.append(s.parent)
s=s.parent
path.reverse()
closeTable.extend(openTable)
return path,closeTable
openTable.extend(subStates)
else:
return None,None
if __name__=='__main__':
originState=State(np.array([[2,8,3],[1,' ',4],[7,6,5]]))
State.answer=np.array([[1,2,3],[8,' ',4],[7,6,5]])
s1=State(state=originState.state)
path,closeTable=s1.solve()
print('访问的结点有：')
for node in closeTable:
print(node.state)
print('')
print(State.answer)
print('访问结点总数为：', len(closeTable) + 1)
if path:
print('\n路径：')
for node in path:
print('')
print(node.state)
print('找到的路径所经过的结点数为：' , len(path))
else:
print('无法找到路径')
eightNum2.py （有序搜索算法1）
import numpy as np
import random
class State:
def __init__(self,state,directionFlag=None,parent=None,depth=0,num=0):
self.state=state
self.direction=['up','down','left','right']
self.parent=parent
if directionFlag:
self.direction.remove(directionFlag)
self.symbol=' '
self.depth = depth
self.num = num
self.cost = 0
def getEmptyPos(self):
position=np.where(self.state==self.symbol)
return position
def generateSubStates(self):
border=len(self.state)-1
row,col=self.getEmptyPos()
subStates=[]
if not self.direction:
return []
if 'up' in self.direction and row>0:
s=self.state.copy()
temp=s.copy()
s[row,col]=s[row-1,col]
s[row-1,col]=temp[row,col]
news=State(s,directionFlag='down',parent=self,depth=self.depth+1)
subStates.append(news)
if 'down' in self.direction and row<border:
s=self.state.copy()
temp=s.copy()
s[row,col]=s[row+1,col]
s[row+1,col]=temp[row,col]
news=State(s,directionFlag='up',parent=self,depth=self.depth+1)
subStates.append(news)
if 'left' in self.direction and col>0:
s=self.state.copy()
temp=s.copy()
s[row,col]=s[row,col-1]
s[row,col-1]=temp[row,col]
news=State(s,directionFlag='right',parent=self,depth=self.depth+1)
subStates.append(news)
if 'right' in self.direction and col<border:
s=self.state.copy()
temp=s.copy()
s[row,col]=s[row,col+1]
s[row,col+1]=temp[row,col]
news=State(s,directionFlag='left',parent=self,depth=self.depth+1)
subStates.append(news)
return subStates
def calCost(self):
self.answer=np.array([[1,2,3],[8,' ',4],[7,6,5]])
for i in range(len(self.state)):
for j in range(len(self.state)):
if(self.state[i,j]!=' ' and self.state[i,j]!=self.answer[i,j]):
self.num=self.num+1
self.cost=self.num+self.depth
def solve(self):
openTable=[]
closeTable=[]
path=[]
openTable.append(self)
while len(openTable)>0:
n = openTable.pop(0)
closeTable.append(n)
subStates = n.generateSubStates()
for s in subStates:
s.calCost()
if (s.state == s.answer).all():
path.append(s)
while s.parent and s.parent != originState:
path.append(s.parent)
s = s.parent
path.reverse()
return path, closeTable
openTable.extend(subStates)
openTable.sort(key=lambda x:x.cost)
else:
return None,None
if __name__=='__main__':
originState = State(np.array([[2, 8, 3], [1, ' ', 4], [7, 6, 5]]))
State.answer = np.array([[1, 2, 3], [8, ' ', 4], [7, 6, 5]])
s1 = State(state=originState.state)
path, closeTable = s1.solve()
print('访问的结点有：')
for node in closeTable:
print(node.state)
print('')
print(State.answer)
print('访问结点总数为：', len(closeTable) + 1)
if path:
print('\n路径：')
for node in path:
print('')
print(node.state)
print('找到的路径所经过的结点数为：', len(path))
else:
print('无法找到路径')
eightNum3.py （DFS算法）
import numpy as np
class State:
def __init__(self,state,directionFlag=None,parent=None,depth=1):
self.state = state
self.direction = ['up', 'down', 'right', 'left']
if directionFlag:
self.direction.remove(directionFlag)
self.parent = parent
self.symbol = ' '
self.depth=depth
def getDirection(self):
return self.direction
def showInfo(self):
for i in range(3):
for j in range(3):
print(self.state[i,j],end=' ')
print('\n')
print('->')
return
def getEmptyPos(self):
position=np.where(self.state==self.symbol)
return position
def generateSubStates(self):
if not self.direction:
return []
subStates=[]
border=len(self.state)-1
row, col = self.getEmptyPos()
if 'up' in self.direction and row > 0:
s = self.state.copy()
temp = s.copy()
s[row, col] = s[row - 1, col]
s[row - 1, col] = temp[row, col]
news = State(s, directionFlag='down', parent=self, depth=self.depth + 1)
subStates.append(news)
if 'down' in self.direction and row < border:
s = self.state.copy()
temp = s.copy()
s[row, col] = s[row + 1, col]
s[row + 1, col] = temp[row, col]
news = State(s, directionFlag='up', parent=self, depth=self.depth + 1)
subStates.append(news)
if 'left' in self.direction and col > 0:
s = self.state.copy()
temp = s.copy()
s[row, col] = s[row, col - 1]
s[row, col - 1] = temp[row, col]
news = State(s, directionFlag='right', parent=self, depth=self.depth + 1)
subStates.append(news)
if 'right' in self.direction and col < border:
s = self.state.copy()
temp = s.copy()
s[row, col] = s[row, col + 1]
s[row, col + 1] = temp[row, col]
news = State(s, directionFlag='left', parent=self, depth=self.depth + 1)
subStates.append(news)
return subStates
def solve(self):
openTable=[]
closeTable=[]
path = []
openTable.append(self)
if (openTable[0].state == openTable[0].answer).all():
path.append(openTable[0])
return path, closeTable
while len(openTable)>0:
n=openTable.pop()
closeTable.append(n)
if n.depth==10:
continue
subStates = n.generateSubStates()
for s in subStates:
if (s.state == s.answer).all():
path.append(s)
while s.parent and s.parent != originState:
path.append(s.parent)
s = s.parent
path.reverse()
return path, closeTable
openTable.extend(subStates)
return None,None
if __name__=='__main__':
originState=State(np.array([[2,8,3],[1,' ',4],[7,6,5]]))
State.answer=np.array([[1,2,3],[8,' ',4],[7,6,5]])
s1=State(state=originState.state)
path,closeTable=s1.solve()
print('访问的结点有：')
for node in closeTable:
print(node.state)
print('')
print(State.answer)
print('访问结点总数为：', len(closeTable) + 1)
if path:
print('\n路径：')
for node in path:
print('')
print(node.state)
print('找到的路径所经过的结点数为：', len(path))
else:
print('无法找到路径')
eightNum4.py （有序搜索算法2）
import numpy as np
import random
class State:
def __init__(self,state,directionFlag=None,parent=None,depth=0,num=0):
self.state=state
self.direction=['up','down','left','right']
self.parent=parent
self.depth=depth
self.num=num
self.cost=0
if directionFlag:
self.direction.remove(directionFlag)
self.symbol=' '
def showInfo(self):
for i in range(3):
for j in range(3):
print(self.state[i,j],end=' ')
print('\n')
print('->')
def getEmptyPos(self):
position=np.where(self.state==self.symbol)
return position
def generateSubStates(self):
border=len(self.state)-1
row,col=self.getEmptyPos()
subStates=[]
if not self.direction:
return []
if 'up' in self.direction and row>0:
s=self.state.copy()
temp=s.copy()
s[row,col]=s[row-1,col]
s[row-1,col]=temp[row,col]
news=State(s,directionFlag='down',parent=self,depth=self.depth+1)
subStates.append(news)
if 'down' in self.direction and row<border:
s=self.state.copy()
temp=s.copy()
s[row,col]=s[row+1,col]
s[row+1,col]=temp[row,col]
news=State(s,directionFlag='up',parent=self,depth=self.depth+1)
subStates.append(news)
if 'left' in self.direction and col>0:
s=self.state.copy()
temp=s.copy()
s[row,col]=s[row,col-1]
s[row,col-1]=temp[row,col]
news=State(s,directionFlag='right',parent=self,depth=self.depth+1)
subStates.append(news)
if 'right' in self.direction and col<border:
s=self.state.copy()
temp=s.copy()
s[row,col]=s[row,col+1]
s[row,col+1]=temp[row,col]
news=State(s,directionFlag='left',parent=self,depth=self.depth+1)
subStates.append(news)
return subStates
def calCost(self):
row,col=self.getEmptyPos()
self.answer=np.array([[1,2,3],[8,' ',4],[7,6,5]])
for i in range(3):
for j in range(3):
if(i!=row[0] or j!=col[0]):
row_des,col_des=np.where(self.answer==self.state[i][j])
self.num=self.num+abs(i-row_des)+abs(j-col_des)
self.cost=self.num+self.depth
def solve(self):
openTable = []
closeTable = []
path = []
openTable.append(self)
while len(openTable) > 0:
n = openTable.pop(0)
closeTable.append(n)
subStates = n.generateSubStates()
for s in subStates:
s.calCost()
if (s.state == s.answer).all():
path.append(s)
while s.parent and s.parent != originState:
path.append(s.parent)
s = s.parent
path.reverse()
return path, closeTable
openTable.extend(subStates)
openTable.sort(key=lambda x: x.cost)
else:
return None, None
if __name__ == '__main__':
originState = State(np.array([[2, 8, 3], [1, ' ', 4], [7, 6, 5]]))
State.answer = np.array([[1, 2, 3], [8, ' ', 4], [7, 6, 5]])
s1 = State(state=originState.state)
path, closeTable = s1.solve()
print('访问的结点有：')
for node in closeTable:
print(node.state)
print('')
print(State.answer)
print('访问结点总数为：', len(closeTable) + 1)
if path:
print('\n路径：')
for node in path:
print('')
print(node.state)
print('找到的路径所经过的结点数为：', len(path))
else:
print('无法找到路径')
Original: https://blog.csdn.net/faith312/article/details/122578105
Author: faith312
Title: 广州大学人工智能导论实验一（八数码问题）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/646493/
转载文章受原作者版权保护。转载请注明原作者出处！