人工智能实验——八数码难题

八数码难题简介

八数码问题指的是定义一个3$\times$3的格子，然后把1-8八个数字随机放入这些格子中，然后排列成规则的格子。就像下面图所示：

在这里插入图片描述

而本文所要解决的是，如何设计一个程序解决八数码问题。解决八数码问题其实算是一个搜索问题。

八数码难题所用到的算法简介

BFS广度优先搜索算法以接近起始节点的程度依次扩展节点的搜索方法宽度优先搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。
DFS深度优先搜索算法优先扩展最新产生的(即最深的)节点的搜索方法深度优先搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。状态空间搜索树的深度可能为无限深，往往给出一个节点扩展的最大深度—深度界限…
贪婪算法（本文未利用）贪婪算法的话，它是一种特殊的DFS算法，若设计得不好得话就会直接退化为DFS算法。在这里得话可以利用每个元素到目标点的曼哈顿距离来作为贪婪算法的引导元素。也可以利用在正确位置的元素的个数作为引导。
代价优先算法（本文未利用）代价算法的话，一般以当前深度作为代价。优先搜索深度小的。
A*算法A*算法结合了贪婪算法与代价优先算法，利用两者的和作为代价利用广度优先的数据结构为基础来进行搜索。

在这里插入图片描述

代码实现解释

1.定义八数码类

首先定义了一个八数码类，此类生成的对象是用来存储八数码数据的。八数码类的对象相当于状态空间。此类中包含了四类数据，分别为八数码的排列顺序、父节点、深度、A*算法对应的代价。下面为八数码类。

# 八数码矩阵classEf:def__init__(self, value, parent=0, depth=1, hscore=0):
        self.value = value
        self.parent = parent  # 定义父节点 若不输入父节点 则自定义其为根 也就是说当parent为0时为根
        self.depth = depth #深度 默认为1
        self.fscore = depth + hscore #A*算法的代价

2.定义操作类

在完成八数码类的编写后，接着的是后继函数即操作。对于后继函数，我的做法是再次定义一个Op类。此类中的函数只有两个，分别为初始化类与空白移动类。在初始化类中，我对传入的八数码对象进行了复制赋值（之所以怎么做是因为Python中的对象类似于指针而不是真正实体）。然后设置了遍历寻找八数码对象中0的位置索引。最后设置了方向参数字典，这样做可以缩减代码量。

在对函数初始化完后，开始编写移动函数，这个函数才是操作类中的主体，这个类的功能主要就是将0与某个方向的数进行替换。一开始编写这个函数时其实分成了四个函数来写的，即上下左右。但是后面发现这些函数的重复性大，于是将不同方向的特定参数整理成了字。将四段代码整理成了一段只要传入字典中的某个值即可移动0。最后返回的是移动成功后的嵌套列表。补充：函数内部拥有一定的边界判别语句，若超界了会返回0。下图为操作类的功能图。

在这里插入图片描述

# 包含所有操作的类 注意python赋值后的对象还是同一个对象 所以要用copyclassOp:def__init__(self, ef):
        self.ef_value = copy.deepcopy(ef.value)for i inrange(0,3):# 获取空位置的索引for j inrange(0,3):if self.ef_value[i][j]==0:
                    self.j, self.i = j, i
                    break
        self.direction ={'left':[self.j ==0,0,-1],'right':[self.j ==2,0,1], \
                          'up':[self.i ==0,-1,0],'down':[self.i ==2,1,0]}# 方向配置字典defmove(self, direc='left'):# 交换操作
        op = self.direction[direc]if op[0]:# 如果在第一列则无法交换 返回0return0else:# 否则交换
            temp = self.ef_value[self.i + op[1]][self.j + op[2]]
            self.ef_value[self.i + op[1]][self.j + op[2]]= self.ef_value[self.i][self.j]
            self.ef_value[self.i][self.j]= temp
            return self.ef_value

3.编写Solution类

完成以上的类的编写后，开始编写程序的主体代码。对于主体，我也还是写了一个Solution类。这个类中的数据主要包含Open表、Closed表、开始状态、目标状态。下图为Solution类各项数据的图解。

在这里插入图片描述

classSolution:def__init__(self, ef):
        self.openT =[]# 定义open表  注意需要用到python自带的队列库
        self.openT.append(ef)# 一开始将其添加进open表
        self.closeT =[]# 定义close表
        self.start_state = ef  # 定义开始状态
        self.des_state =[[1,2,3],[8,0,4],[7,6,5]]# 定义最终状态
        self.des_state_dict ={1:[0,0],2:[0,1],3:[0,2],8:[1,0],0:[1,1],4:[1,2],7:[2,0],6:[2,1],5:[2,2]}#字典格式

初始化完Solution类后，我定义了多个基础的函数，这些函数基本上都是判断函数。包括状态是否到达目标状态判断函数、状态是否重复判断函数、是否可解函数。对于前两个，函数本体基本上都是用推导式一句完成的。而对于是否可解函数相对复杂。此判断首先是把八数码矩阵变成一维的形式，然后从第一个位置开始（除0外）记录每个元素前面比此元素大的个数，并把这些个数相加。如果最后得到的是偶数则有解否则无解。下图为判断函数的代码截图。参考：**http://t.csdn.cn/0vyzV

defiSolve(self,ef):#八数码是否有解判断 有解则返回1#转一维列表
        onedi =[ef.value[0][i]for i inrange(3)]+[ef.value[1][2]]+ \
                [ef.value[2][i]for i inrange(2,-1,-1)]+[ef.value[1][i]for i inrange(2)]
        oxe =0#计算逆序for i inrange(1,9):if onedi[i]!=0:for j inrange(i):
                    oxe +=1if onedi[j]> onedi[i]else0return1if oxe %2==0else0

4.extend函数.

除了以上的基础函数外，还有一个十分重要的基础函数。此函数是用来拓展的。此函数内部包含过滤机制，如果拓展生成的嵌套列表在closed表的话就丢弃，如果不在的话就计算深度并把父节点、深度、代价、嵌套列表传入一个新的八数码对象中，然后添加到open表中。

defextend(self, ef):# 拓展节点
        ex_direct =['up','down','left','right']for d in ex_direct:
            temp = Op(ef).move(d)# 由于这里用到了 copy深度复制  所以就要用一下方法阻止循环if temp:# 如果可以上移则执行并且上行的结果不在closeTfor i in self.closeT:# 这里还可以重构if i == temp:breakelse:
                    ef_d = Ef(temp, ef, ef.depth+1, self.h(temp))# 定义一个新对象 值为返回的上行结果 父节点为ef#若要改h(n)在上面改
                    self.openT.append(ef_d)

在这里插入图片描述

5.BFS算法

在一切都铺垫好后开始编写搜索算法，首先写的是BFS算法函数。进入函数后首先开始记录当前时间并把它命定义为start_time。然后判断传入的八数码对象是否有解，若无解则放回“No Solution!”，否则进入下面操作。判断Open表是否为空，若为空则放回”Failure”否则进入下面操作。检测Open表队首是否为目标状态，若不为目标状态则对队首元素进行拓展，并把队首纳入closed表中然后弹出。若已经是目标则遍历目标的父节点直到无父节点。然后打印这些父节点与程序运行时间与节点深度。以下为流程图

在这里插入图片描述

defBFS(self):# 广度搜索
        start_time = time.time()if self.iSolve(self.openT[0]):while self.openT:# 判断openT是否空表if self.isDes(self.openT[0]):
                    result =[]
                    pointer = self.openT[0]
                    result.append(pointer.value)while pointer.parent:
                        pointer = pointer.parent
                        result.append(pointer.value)print(f'当前深度:{self.openT[0].depth}\n程序运行时间:{time.time() - start_time}s'
                          f'\n以下为推导过程（BFS）')while result:print(result.pop())# 逆序打印return"Success"else:
                    self.closeT.append(self.openT[0].value)# 给closeT添加值
                    self.extend(self.openT[0])# 若不是结果的话则拓展ef
                    self.openT.pop(0)# 出队else:return"Failure"else:return'No Solution!'

6.DFS算法

对于DFS其代码与BFS的类似，不同的地方在于其利用的数据结构是栈而不是队列，所以它首先检测的是最后一个元素是否是目标，并且也是首先对最后一个元素进行拓展。除此之外，DFS还对此进行了深度的限制。下图为我制作的程序在DFS上的流程图。

在这里插入图片描述

defDFS(self,depth=20):#深度搜索 需要传入深度参数 默认为100
        start_time = time.time()if self.iSolve(self.openT[0]):while self.openT:# 判断openT是否空表且是否超过深度if self.isDes(self.openT[-1]):#检测倒数第一个
                    result =[]
                    pointer = self.openT[-1]
                    result.append(pointer.value)while pointer.parent:
                        pointer = pointer.parent
                        result.append(pointer.value)print(f'当前深度:{self.openT[-1].depth}\n程序运行时间:{time.time() - start_time}s'
                          f'\n以下为推导过程（DFS）')while result:print(result.pop())# 逆序打印return"Success"else:
                    self.closeT.append(self.openT[-1].value)# 给closeT添加值if self.openT[-1].depth < depth:#深度限制
                        self.extend(self.openT.pop())# 若不是结果的话则拓展efelse:
                        self.openT.pop()else:return"Failure"else:return'No Solution!'

7.A*算法

而A算法大体上的程序结构和DFS与BFS是一致的，但是其利用的是优先队列。每一次拓展后都会根据代价的值对OPEN表进行排序，取代价最小的到队首然后对队首进行判断是否为目标，若为目标则打印结果否则进行拓展并排序。而这里的代价有g(n)与h(n)组成，g(n)是当前状态的深度利用的是DFS中的深度接口，而h(n)则是自己设计的。我设计了两种h(n)，第一种是八数码九宫格里面各个元素与目标元素的差异个数。另外一种是各个元素到目标元素的最短距离的距离之和。附件中提供的程序利用的是第一种，第二种在代码中也有但是需要更改下接口。下图为A算法的流程图。

在这里插入图片描述

defastar(self):
        start_time = time.time()if self.iSolve(self.openT[0]):while self.openT:# 判断openT是否空表且是否超过深度if self.isDes(self.openT[0]):#检测倒数第一个
                    result =[]
                    pointer = self.openT[0]
                    result.append(pointer.value)while pointer.parent:
                        pointer = pointer.parent
                        result.append(pointer.value)print(f'当前深度:{self.openT[0].depth}\n程序运行时间:{time.time() - start_time}s'
                          f'\n以下为推导过程（A*）')while result:print(result.pop())# 逆序打印return"Success"else:
                    self.closeT.append(self.openT[0].value)# 给closeT添加值
                    self.extend(self.openT[0])# 若不是结果的话则拓展ef
                    self.openT.pop(0)# 出队
                    self.openT.sort(key=lambda x:x.fscore)#排序 根据fscore排序else:return"Failure"else:return'No Solution!'