基于状态空间表示法的搜索算法解决八数码难题

本文的pdf文件链接：link

一、问题重述

1.1 背景介绍

       如今处于人工智能和大数据时代，每天都有成千上万的数据产生，而我们在获取数据的时候需要用到搜索引擎，而互联网中的数据就相当于一颗巨大的树的结点，我们搜索信息的过程实际上就是遍历树的过程，那么搜索算法的好坏将直接决定了我们获取信息的快慢。搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。现阶段一般有枚举算法、深度优先搜索、广度优先搜索、A*算法、回溯算法、蒙特卡洛树搜索、散列函数等算法。在大规模实验环境中，通常通过在搜索前，根据条件降低搜索规模；根据问题的约束条件进行剪枝；利用搜索过程中的中间解，避免重复计算这几种方法进行优化。
       而八数码难题的求解就是一个搜索的过程，所以我们首先根据求解八数码难题的过程来体会搜索算法的应用。

1.2 实验目的

       考察和培养对图搜索知识点的综合理解和应用。体验搜索的具体实现过程以及各种搜索算法的实现及算法之间的优缺点和差异，从而为以后可以运用搜索算法打下基础。

二、实验原理

2.1 状态空间表示法

       人工智能的多个研究领域从求解现实问题的过程来看，都可以抽象为一个：问题求解“过程，问题求解实际上就是一个搜索过程。在搜索过程开始之前，必须先用某种方法或某几种方法的混合来表示问题。问题的求解技术主要涉及两个方面：问题的表示和求解的方法。
       状态空间表示法法：用来表示问题及其搜索过程的一种方法。基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的。主要包括：状态，算符，状态空间。
1，状态
       表示问题求解过程中每一步问题状况的数据结构，一般用一组数据表示：
$$S_k=[Sk{]}_0,[Sk{]}_1,\dots \dots$$
       式中每个元素为集合的分量，称为状态变量：每一个分量给予确定的值时，得到了一个具体的状态；任何一种类型的数据结构都可以用来描述状态，只要它有利于问题求解；在程序中用字符，数字，记录，数组，结构，对象等表示状态。
2，算符
       当对一个问题状态使用某个可用操作时，他将引起该状态中某些分量值的变化，从而使问题从一个具体状态变为另一个具体状态。
       算符可以理解为状态集合上的一个函数，它描述了状态之间的关系，算符可以是某种操作，规则，行为，变换，算子，函数，过程等，算符也称为操作，问题的状态也只能经定义在其上的这种操作而改变。
3，状态空间
       用来描述一个问题的全部状态以及这些状态之间的相互关系，状态空间常用一个三元组表示：（S，F，G），其中S为问题的所有初始状态的集合，F为算符的集合，G为目标状态的集合。

2.2 八数码难题

       八数码难题：又称九宫格问题。

       首先给定一个九宫格的初始状态，只能将其中的空格进行移动，直到外面的八个数字达到目标状态。

2.3 图搜索算法

2.3.1 盲目式搜索

1、宽度优先
       对上图进行宽度优先搜索，并列出其Open表和Close表。

       其结点的先后访问顺序为：A->B->C->D->E->F->G->H->I->J->K
2，深度优先
       对上图进行深度优先搜索，并列出其Open表和Close表。
       其结点的先后访问顺序为：A->B->D->H->K->E->C->F->I->G->J

2.3.2启发式搜索

       启发式搜索：启发性信息是指那种与具体问题求解过程有关的，并可指导搜索过程朝着最优希望方向前进的控制信息。
       启发式搜索是利用与问题有关的启发性信息，并以这些启发性信息指导的搜索的问题求解过程。
       $A^{\ast }$算法：启发式搜索，是一种尽可能基于现有信息的搜索策略，也就是说搜索过程中尽量利用目前已知的诸如迭代步数，以及从初始状态和当前状态到目标状态估计所需的费用等信息。
       $A^{\ast }$算法可以选择下一个被检查的节点时引入了已知的全局信息，对当前结点距离终点的距离作出估计，作为评价该节点处于最优路线上的可能性的量度，这样可以首先搜索可能性大的节点，从而提高了搜索过程的效率。
       $A^{\ast }$算法的基本思想如下：引入当前节点j的估计函数f*,当前节点j的估计函数定义为：
$$f(j)=g(j)+h(j)$$
       其中g(j)是从起点到当前节点j的实际费用的量度，h*(j)是从节点j到终点的最小费用的估计，可以依据实际情况，选择h*(j)的具体形式，h*(j)要满足一个要求：不能高于节点j到终点的实际最小费用。从起始节点点向目的节点搜索时，每次都搜索f*(j)最小的节点，直到发现目的节点。
       A*算法的核心是设计估价函数，设计估价函数h(j)有很多方法，例如欧几里得距离和曼哈顿距离等。
算法步骤：
       1：生成空的Open表、Close表，将起点S放入Open表
       2：如果Open表为空，则失败退出。
       3：从Open表中，找出头节点U,作为当前节点,将它从OPEN表中移除。
       4：判断U是否为终点，如果是，则通过节点U的父指针，一直遍历到起点，找到到最优路径，算法结束。否则，转步5.
       5：扩展当前节点U,找到其扩展的后继节点集合V,遍历集合V中的节点，如果节点即不在Open表也不在Close表，计算该节点的估计值，将节点加入到OPEN表，设置父节点为U.如果节点在Open表、Close表，比较当前节点的代价g(v)和Open表、Close表中代价，如果当前节点的代价g(v)小，更新表中的代价和父节点指针。
       6：按估价值递增的顺序，对Open表中所有节点进行排序。
       7：转步2.

三、实验步骤

1，首先给定任一初始状态和目标状态；
2，分别使用宽度优先搜索，广度优先搜索和A算法求解问题；
3，分析使用不同方法求解问题所需要的步骤。

       宽度优先：A->B->C->D->E->F->G->H->I->J->K->L->M
       深度优先：A->B->F->G->C->H->I->D->J->K->E->L->M

       如上图所示，不同算法的搜索过程不同，对于宽度和广度优先搜索两种盲目式搜索算法来说，不同的起始状态和终止状态在两种搜索策略下的结果差异可能非常大，而A算法作为启发式搜索，可以根据每一步的结果来决定下一步的走向，所以在通常情况下更容易找到目标结果。

四、实验结果

4.1 宽度优先

4.2 广度优先

4.3 A*算法

       根据三种不同的算法，选择相同的起始状态和目标状态，三种算法都得到了最终答案，但是发现，宽度优先搜索和A算法都只用了5步就得到了结果，但是广度优先搜索却用了1579步才得到了结果，而宽度优先和A算法的路径则完全相同。

五、实验分析

       经过实验可得，如果所给八数码问题可解，那么深度，广度和A*搜索算法都可以得到解，只是不同的算法收敛的速度不尽相同，因此针对深度优先和广度优先两种盲目式搜素算法做一些改进得到了有界深度优先搜索算法，但是其不一定可以得到结果，所以在一些复杂的网页搜索中大多数采用的是启发式搜索，而在一些数据库的搜素算法中则采用跳表，B+树，红黑树等数据结构来升高数据的维度达到减少搜索时间的目的。

六、心得体会

       针对不同的问题，各种算法的表现不尽相同，所以明白各种算法的特点及适用条件才可以正确的选择可用的算法。

七、python代码

7.1 宽度深度优先搜索

G = {}
g_dict_shifts = {0: [1, 3], 1: [0, 2, 4], 2: [1, 5], 3: [0,4,6], 4: [1,3,5,7], 5: [2,4,8], 6: [3,7],  7: [4,6,8], 8: [5,7]}
def swap_chr(a, i, j):
    if i > j:
        i, j = j, i
    b = a[:i] + a[j] + a[i+1:j] + a[i] + a[j+1:]
    return b
def solvePuzzle_depth(start, des):
    src = 0
    dest = 0
    for i in range(1,9):
        fist=0
        for j in range(0,i):
          if start[j]>start[i] and start[i]!='0':
              fist = fist+1
        src = src+fist
    for i in range(1, 9):
        fist=0
        for j in range(0, i):
          if des[j] > des[i] and des[i] != '0':
              fist = fist+1
        dest = dest+fist
    if (src%2)!=(dest%2):
        return -1, None
    G[start] = -1
    stack_layouts = []
    stack_layouts.append(start)
    bFound = False
    while len(stack_layouts) > 0:
        #curLayout = stack_layouts.pop()  # 出栈，深度优先
        curLayout = stack_layouts.pop(0)  # 把栈改成队列，广度优先
        if curLayout == des:
            break
        ind_slide = curLayout.index("0")
        lst_shifts = g_dict_shifts[ind_slide]
        for nShift in lst_shifts:
            newLayout = swap_chr(curLayout, nShift, ind_slide)
            if G.get(newLayout) == None:
                G[newLayout] = curLayout
                stack_layouts.append(newLayout)
    lst_steps = []
    lst_steps.append(curLayout)
    while G[curLayout] != -1:
        curLayout = G[curLayout]
        lst_steps.append(curLayout)
    lst_steps.reverse()
    return 0, lst_steps

if __name__ == "__main__":
    start = "283104765"
    des = "123804765"
    retCode, lst_steps = solvePuzzle_depth(start, des)
    if retCode != 0:
        print("目标布局不可达")
    else:
        for nIndex in range(len(lst_steps)):
            print("step #" + str(nIndex + 1))
            print(lst_steps[nIndex][:3])
            print(lst_steps[nIndex][3:6])
            print(lst_steps[nIndex][6:])

7.3 A*算法

g_dict_layouts = {}
g_dict_layouts_deep = {}
g_dict_layouts_fn = {}
# 每个位置可交换的位置集合
g_dict_shifts = {0:[1, 3], 1:[0, 2, 4], 2:[1, 5],3:[0,4,6], 4:[1,3,5,7], 5:[2,4,8],6:[3,7],  7:[4,6,8], 8:[5,7]}
def swap_chr(a, i, j, deep, destLayout):
    if i > j:
        i, j = j, i
    b = a[:i] + a[j] + a[i+1:j] + a[i] + a[j+1:]
    fn = cal_dislocation_sum(b, destLayout)+deep
    return b, fn

def cal_dislocation_sum(srcLayout,destLayout):
    sum = 0
    a= srcLayout.index("0")
    for i in range(0,9):
        if i != a:
            sum = sum+abs(i-destLayout.index(srcLayout[i]))
    return sum
def solvePuzzle_A(srcLayout, destLayout):
    src = 0
    dest = 0
    for i in range(1, 9):
        fist = 0
        for j in range(0, i):
          if srcLayout[j] > srcLayout[i] and srcLayout[i]!='0':
              fist = fist+1
        src = src+fist
    for i in range(1,9):
        fist=0
        for j in range(0,i):
          if destLayout[j]>destLayout[i] and destLayout[i]!='0':
              fist = fist+1
        dest = dest+fist
    if (src%2)!=(dest%2):
        return -1, None
    g_dict_layouts[srcLayout] = -1
    g_dict_layouts_deep[srcLayout]= 1
    g_dict_layouts_fn[srcLayout] = 1 + cal_dislocation_sum(srcLayout, destLayout)
    stack_layouts = []
    gn = 0
    stack_layouts.append(srcLayout)
    while len(stack_layouts) > 0:
        curLayout = min(g_dict_layouts_fn, key=g_dict_layouts_fn.get)
        del g_dict_layouts_fn[curLayout]
        stack_layouts.remove(curLayout)
        # curLayout = stack_layouts.pop()
        if curLayout == destLayout:
            break
        # 寻找0 的位置。
        ind_slide = curLayout.index("0")
        lst_shifts = g_dict_shifts[ind_slide]
        for nShift in lst_shifts:
            newLayout, fn = swap_chr(curLayout, nShift, ind_slide, g_dict_layouts_deep[curLayout] + 1, destLayout)
            if g_dict_layouts.get(newLayout) == None:
                g_dict_layouts_deep[newLayout] = g_dict_layouts_deep[curLayout] + 1
                g_dict_layouts_fn[newLayout] = fn
                g_dict_layouts[newLayout] = curLayout
                stack_layouts.append(newLayout)
    lst_steps = []
    lst_steps.append(curLayout)
    while g_dict_layouts[curLayout] != -1:
        curLayout = g_dict_layouts[curLayout]
        lst_steps.append(curLayout)
    lst_steps.reverse()
    return 0, lst_steps
if __name__ == "__main__":
    srcLayout = "283104765"
    destLayout = "123804765"
    retCode, lst_steps = solvePuzzle_A(srcLayout, destLayout)
    if retCode != 0:
        print("目标布局不可达")
    else:
        for nIndex in range(len(lst_steps)):
            print("step #" + str(nIndex + 1))
            print(lst_steps[nIndex][:3])
            print(lst_steps[nIndex][3:6])
            print(lst_steps[nIndex][6:])