实验一 八数码问题

一、 实验目的
该课程的教学应贯彻理论与实践相结合的原则，为学生所学到的理论提供实践的场所，通过实验课程中具体问题的求解达到深入了解并掌握的目的。

二、 实验环境
微型计算机，操作系统为windows7或Windows10系统，编程工具学生可以自由选择Visual Studio、Java、Python（建议Anconda发行版）和Matlab等。

三、 实验内容
基于图搜索技术的八数码问题求解
问题描述：八数码，在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。

内容提要：分别用广度优先搜索策略、深度优先搜索策略和启发式搜索算法（至少两种）求解八数码问题；分析估价函数对启发式搜索算法的影响；探究讨论各个搜索算法的特点。
实验步骤：

1. 随机生成一个八数码问题分布，设计一个可解的目标状态（要求棋盘9个位置都不同）。
2. 分别用广度优先搜索策略、深度优先搜索策略和至少两种启发式搜索算法求解八数码问题
3. 分析估价函数对启发式搜索算法的影响。
4. 探究讨论各个搜索算法的特点。
5. *扩展选做题：从初始状态到目标状态的变换，符合什么规律才可解（提示参考：逆序数）

四、 实验原理
宽度度优先搜索：
如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索。这种搜索是逐层进行的，在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。

深度优先搜索：
属于图算法的一种，是一个针对图和树的遍历算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次

有序搜索算法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
# BFS算法

class State:
    def __init__(self,state,directionFlag=None,parent=None):
        # state是State类的属性，是八数码矩阵3*3
        self.state=state
        self.direction=['up','down','right','left']
        #当directionFlag有值时，从direction数组变量中移除directionFlag的值，这在生成子节点时派上用场
        if directionFlag:
            self.direction.remove(directionFlag)
        #存放当前结点的父节点
        self.parent=parent
        #表示八数码中的空格
        self.symbol=' '

    def getDirection(self):
        return self.direction

    def getEmptyPos(self):
        # 找到' '在八数码矩阵中的位置
        # position=(array([2], dtype=int64), array([1], dtype=int64))
        position=np.where(self.state==self.symbol)
        return position

    def generateSubStates(self):
        #进行移动后生成新的矩阵，存储在SubStates数组中
        if not self.direction:
            return []
        subStates=[]
        boarder=len(self.state)-1

        #得到' '的坐标赋值给row,col
        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]
            #关键，这里parent设置为self，即生成该news矩阵的父矩阵，为后续查找path铺垫
            news = State(s, directionFlag='up', parent=self)
            subStates.append(news)

        return subStates

    def solve(self):
        openTable=[]
        closeTable=[]
        #将State类对象self加入到openTable数组中
        openTable.append(self)
          #当openTable不为空表时
        while len(openTable)>0:
            n=openTable.pop(0)
            #将结点n移入closeTable表中
            closeTable.append(n)
            #调用了generateSubStates()函数，扩展n结点，subStates装的都是State类对象
            subStates=n.generateSubStates()
            path=[]
            for s in subStates:
                # 当扩展子节点中有目标状态时，根据其父节点一步一步往回寻找到根结点（初始状态），并将结点存放在path中
                if(s.state==s.answer).all():
                    path.append(s)
                    while s.parent and s.parent!=originState:
                        path.append(s.parent)
                        s=s.parent
                    #path数组翻转，得到从根节点到目标结点的路径
                    path.reverse()
                    # closeTable装有从初始状态到目标状态的父节点的搜索过程中所访问过的结点
                    # 再加上openTable中的结点，才算装有从初始状态到目标状态访问的所有结点
                    closeTable.extend(openTable)
                    return path,closeTable
            #将扩展的子节点都放入openTable表中
            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]])

    #实例化State类对象s1，状态为初始状态
    s1=State(state=originState.state)
    #用对象s1调用类State内的函数solve()，进行八数码问题的求解
    path,closeTable=s1.solve()

    print('访问的结点有：')
    for node in closeTable:
        print(node.state)
        print('')
    print(State.answer)
    print('访问结点总数为：', len(closeTable) + 1)

    #只显示在path数组中的矩阵
    if path:
        print('\n路径：')
        for node in path:
            print('')
            print(node.state)
        print('找到的路径所经过的结点数为：' , len(path))
    else:
        print('无法找到路径')
 # 因为在generateSubStates函数中空格移动的上下左右方向顺序排列不同，所以最后steps大小会有一点点差异

eightNum2.py （有序搜索算法1）

import numpy as np
import random

# 有序搜索（最佳优先搜索）  A* 有序搜索算法1

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=' '
        #depth=g(n)
        self.depth = depth
        #num=h(n)
        self.num = num
        #cost=f(n)=g(n)+h(n)
        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):
        # g(x)=depth     h(x)=num
        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=[]

        # 将State类对象self加入到openTable数组中
        openTable.append(self)
        # 当openTable不为空表时
        while len(openTable)>0:
            n = openTable.pop(0)
            # 将openTable的首结点n移入closeTable表中，即为选中openTable表中f值最小的结点n
            closeTable.append(n)
            # 调用了generateSubStates()函数，扩展n结点，subStates装的都是State类对象
            subStates = n.generateSubStates()
            for s in subStates:
                #计算当前子节点的f(n)值
                s.calCost()
                # 当扩展子节点中有目标状态时，根据其父节点一步一步往回寻找到根结点（初始状态），并将结点存放在path中
                if (s.state == s.answer).all():
                    path.append(s)
                    while s.parent and s.parent != originState:
                        path.append(s.parent)
                        s = s.parent
                    # path数组翻转，得到从根节点到目标结点的路径
                    path.reverse()
                    # closeTable装有从初始状态到目标状态的搜索过程中所访问过的结点，
                    return path, closeTable
                # 将扩展的子节点都放入openTable表中
                openTable.extend(subStates)
            # 对openTable进行排序，根据State.cost的大小从小到大排序
            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]])
    # 实例化State类对象s1，状态为初始状态
    s1 = State(state=originState.state)
    # 用对象s1调用类State内的函数solve()，进行八数码问题的求解
    path, closeTable = s1.solve()

    print('访问的结点有：')
    for node in closeTable:
        print(node.state)
        print('')
    print(State.answer)
    print('访问结点总数为：', len(closeTable) + 1)

    # 只显示在path数组中的矩阵
    if path:
        print('\n路径：')
        for node in path:
            print('')
            print(node.state)
        print('找到的路径所经过的结点数为：', len(path))
    else:
        print('无法找到路径')

eightNum3.py （DFS算法）

import numpy as np

# DFS算法  深度优先算法
#设置深度上限 为10

class State:
    def __init__(self,state,directionFlag=None,parent=None,depth=1):
        # state是State类的属性，是八数码矩阵3*3
        self.state = state
        self.direction = ['up', 'down', 'right', 'left']
        # 当directionFlag有值时，从direction数组变量中移除directionFlag的值，这在生成子节点时派上用场
        if directionFlag:
            self.direction.remove(directionFlag)
        # 存放当前结点的父节点
        self.parent = parent
        # 表示八数码中的空格
        self.symbol = ' '
        #表示该节点的深度，初始结点深度为1
        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 = []

          # 将State类对象self加入到openTable数组中
          openTable.append(self)
          # 判断首结点是否为目标结点
          if (openTable[0].state == openTable[0].answer).all():
              path.append(openTable[0])
              return path, closeTable
          #当openTable表不为空时
          while len(openTable)>0:
              #取openTable表中的最后一节点为节点n
              n=openTable.pop()
              # 将结点n移入closeTable表中
              closeTable.append(n)
              if n.depth==10:
                  continue

              # 调用了generateSubStates()函数，扩展n结点，subStates装的都是State类对象
              subStates = n.generateSubStates()

              for s in subStates:
                  # 当扩展子节点中有目标状态时，根据其父节点一步一步往回寻找到根结点（初始状态），并将结点存放在path中
                  if (s.state == s.answer).all():
                      path.append(s)
                      while s.parent and s.parent != originState:
                          path.append(s.parent)
                          s = s.parent
                      # path数组翻转，得到从根节点到目标结点的路径
                      path.reverse()
                      # closeTable装有从初始状态到目标状态的搜索过程中所访问过的结点，
                      return path, closeTable
              #将扩展的子节点放入openTable表的末端
              openTable.extend(subStates)
          return None,None




if __name__=='__main__':

    # 初始化originState   State类对象
    originState=State(np.array([[2,8,3],[1,' ',4],[7,6,5]]))
    #确定目标的state 这是又新生成了State类的answer属性？
    State.answer=np.array([[1,2,3],[8,' ',4],[7,6,5]])

    #State类对象s1
    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)

    # 只显示在path数组中的矩阵
    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

# 不同启发函数  A* 有序搜索算法2

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):
        # g(x)=depth   h(x)=num  当前状态数字所在位置和目标状态所在位置进行相减取绝对值依次获得八个数（空位不进行计算）的差值
        # h(x)=num  当前状态数字所在位置和目标状态所在位置进行相减取绝对值依次获得八个数（空位不进行计算）的差值,相加所得即为h(x)的值
        #获得空值' '的坐标
        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):
                #当所定位的位置(i,j)不是空值' '时，
                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 = []

        # 将State类对象self加入到openTable数组中
        openTable.append(self)
        # 当openTable不为空表时
        while len(openTable) > 0:
            n = openTable.pop(0)
            # 将openTable的首结点n移入closeTable表中，即为选中openTable表中f值最小的结点n
            closeTable.append(n)
            # 调用了generateSubStates()函数，扩展n结点，subStates装的都是State类对象
            subStates = n.generateSubStates()
            for s in subStates:
                # 计算当前子节点的f(n)值
                s.calCost()
                # 当扩展子节点中有目标状态时，根据其父节点一步一步往回寻找到根结点（初始状态），并将结点存放在path中
                if (s.state == s.answer).all():
                    path.append(s)
                    while s.parent and s.parent != originState:
                        path.append(s.parent)
                        s = s.parent
                    # path数组翻转，得到从根节点到目标结点的路径
                    path.reverse()
                    # closeTable装有从初始状态到目标状态的搜索过程中所访问过的结点，
                    return path, closeTable
                # 将扩展的子节点都放入openTable表中
                openTable.extend(subStates)
            # 对openTable进行排序，根据State.cost的大小从小到大排序
            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]])
    # 实例化State类对象s1，状态为初始状态
    s1 = State(state=originState.state)
    # 用对象s1调用类State内的函数solve()，进行八数码问题的求解
    path, closeTable = s1.solve()
    print('访问的结点有：')
    for node in closeTable:
        print(node.state)
        print('')
    print(State.answer)
    print('访问结点总数为：', len(closeTable) + 1)
    # 只显示在path数组中的矩阵
    if path:
        print('\n路径：')
        for node in path:
            print('')
            print(node.state)
        print('找到的路径所经过的结点数为：', len(path))
    else:
        print('无法找到路径')