【人工智能】实验报告及A*搜索方法走迷宫（基于曼哈顿距离）

2020-06-07 22:41 作者:Aiello筱郁 0人读过 | 我要投稿

编译器：Pycharm+Anaconda虚拟环境

Python版本：3.7

采用启发函数：曼哈顿距离

一、关于理解八数码问题

参考文章：https://blog.csdn.net/qq_41417335/article/details/86359831

https://www.runoob.com/python/python-att-dictionary-pop.html

https://blog.csdn.net/yangysc/article/details/50710439

在正式开展A*算法的话题前我们或许需要花点时间来稍微捋一捋搜索算法在实现过程中的一些问题（笔记形式）。

解决八数码经典问题主要采取的三种方法：宽度优先、深度优先、A*算法

1. 宽度优先同深度优先

在参考给出的例代码中宽度优先和深度优先都属于遍历类型的盲目搜索算法，唯一的区别就是书本上提到的：宽度优先法是将n其余的子状态按生成的顺序加入到open表的后端，而深度优先算法则是前端。对应代码的编写的不同之处就是对代码中的“open”表（即“stack_layouts”）

正如参考文章中所说，只需将curLayout = stack_layouts.pop(0) 改作curLayout = stack_layouts.pop()，即可对应实现深度优先搜索算法。原因就是pop和append两个函数的性质。

由于append和pop函数均是默认添加集合到列表末尾/移出列表最后一个集合，而curLayout = stack_layouts.pop(0)则是移除“stack_layouts”中首位集合，就实现了同一种open表存储，不同的优先展开（考察节点）的方式（前端优先或后端优先），同专业书（王万良《人工智能及其应用》第3版·高等教育出版社，2016.2）上的改变添加方式是本质相同的。

2. A*算法的理解

启发函数h(x)同专业书上相同，是八数码表中当前位置同目标位置相比较，处于不同位置的数字到达目标位所需移动的距离之和。在swap_chr函数（定义的交换数码的函数）中，b是以一个数列的形式存储的（对应九宫格的数），运用的组合方法则是切片再组合（分5个部分）。其中fn就是f(x)，deep就是g(x)，destLayout就是目标状态。

3. 程序本身的实现

程序主要以以下三个字典来定义当前九宫格状态（以数组表示的排列形式，搜索深度，当前状态的fn值）：

    g_dict_layouts = {}
    g_dict_layouts_deep = {}
    g_dict_layouts_fn = {}

g_dict_shifts则是以字典形式定义了整个九宫格内每个位置可以实现的移动交换方式：

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]}

一、关于走迷宫中的A*算法的实现

参考八数码中的代码格式，我在网上找寻了经典的走迷宫问题，其中不乏有各种遍历式的盲目算法，但运用启发式的并且明确实现的很少，我便准备仿照建立字典表定义移动交换方式和具体状态的方法以A*算法的方式实现最优走迷宫。

参考文章：https://blog.csdn.net/qq_29681777/article/details/83719680

https://blog.csdn.net/diamonjoy_zone/article/details/65630144

首先，我们需要有一个可解的迷宫maze（用1代表不可走的墙，用0代表可走的路），并且需要定义走迷宫的方法（上下左右四个方向，由于对于迷宫内任何一个点我们都可以四个方向转，于是就不用字典的表达方式而另加一个函数passable来判断是否转向是可行的）。之后我们仿照八数码的形式建立我们的字典表格架构，修改原有的递归函数find_path并加入我们定义的启发函数判断方法，编写find_path_A。

/修改前通过递归的方法实现的遍历搜索可视化路径（代码中的find_path函数）

其中S代表开始位置，E代表目标终点，*为寻找到的路径，#代表寻路中走过的无用路径/

1. 最终代码如下：

import math
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 当前位置四个方向的偏移量,即可以转动的四个方向
path = [] # 存找到的路径
#仿照八数码解决方法中的表结构
g_dict_layouts = {}
g_dict_layouts_deep = {} #深度
g_dict_layouts_fn = {} #启发函数值

def mark(maze, pos): # 给迷宫maze的位置pos标"2"表示“倒过了”
    maze[pos[0]][pos[1]] = 2

def passable(maze, pos): # 检查迷宫maze的位置pos是否可通行
    return maze[pos[0]][pos[1]] == 0

#启发函数
def get_dist(pos, end):
        return math.sqrt((end[0]-pos[0])*(end[0]-pos[0]))+ math.sqrt((end[1]-pos[1])*(end[1]-pos[1]))
        #曼哈顿距离

def turn_best(pos, i, deep, end):
    nextp = pos[0] + i[0], pos[1] + i[1] ##注意修改后的维度##
    #存储fn启发函数值,A*算法
    fn = get_dist(nextp, end) + deep
    return nextp, fn

#修改后的A*解决法
def find_path_A(maze,pos,end):
    # 构建开始节点和表格
    g_dict_layouts[pos] = -1
    g_dict_layouts_deep[pos] = 1
    g_dict_layouts_fn[pos] = 1 + get_dist(pos, end)
    stack_layouts = []
    stack_layouts.append(pos) # 当前状态存入列表

    while len(stack_layouts) > 0:
        mark(maze, pos)#标记走到的位置
        curLayout = min(g_dict_layouts_fn, key=g_dict_layouts_fn.get)
        print(curLayout)
        del g_dict_layouts_fn[curLayout]
        stack_layouts.remove(curLayout) #找到最小fn，并移除,扩展节点向下搜寻

        if curLayout == end: # 判断当前状态是否为目标状态
            break
        lst_shifts = dirs # 当前可进行移动的四个方向，接下来对每个方向进行可行性判断
        for nShift in lst_shifts:
            newLayout, fn = turn_best(curLayout, nShift, g_dict_layouts_deep[curLayout] + 1, end)
            if g_dict_layouts.get(newLayout) == None: # 判断交换后的状态是否已经查询过
                if passable(maze, newLayout): # 不可行的相邻位置不管
                    g_dict_layouts_deep[newLayout] = g_dict_layouts_deep[curLayout] + 1 # 存入深度
                    g_dict_layouts_fn[newLayout] = fn # 存入fn
                    g_dict_layouts[newLayout] = curLayout # 定义前驱结点
                stack_layouts.append(newLayout) # 存入集合

    path.append(curLayout) #存入每次找到的最优解决，之后可以不用g_dict_layouts表直接调用path
    while g_dict_layouts[curLayout] != -1: # 存入路径
        curLayout = g_dict_layouts[curLayout]
        path.append(curLayout)
    path.reverse()
    return 0

#修改前的递归解决法
def find_path(maze, pos, end):
    mark(maze, pos)
    if pos == end:
        print(pos, end=" ") # 已到达出口，输出这个位置。成功结束
        path.append(pos)
        return True
    for i in range(4): # 否则按四个方向顺序检查
        nextp = pos[0] + dirs[i][0], pos[1] + dirs[i][1]
        # 考虑下一个可能方向
        if passable(maze, nextp): # 不可行的相邻位置不管
            if find_path(maze, nextp, end): # 如果从nextp可达出口，输出这个位置，成功结束
                print(pos, end=" ")
                path.append(pos)
                return True
    return False

# 使寻找到的路径可视化
def see_path(maze, path):
    for i, p in enumerate(path):
        if i == 0:
            maze[p[0]][p[1]] = "E"
        elif i == len(path) - 1:
            maze[p[0]][p[1]] = "S"
        else:
            maze[p[0]][p[1]] = 3
    print("\n")
    for r in maze:
        for c in r:
            if c == 3:
                print('\033[0;31m' + "*" + " " + '\033[0m', end="")
            elif c == "S" or c == "E":
                print('\033[0;34m' + c + " " + '\033[0m', end="")
            elif c == 2:
                print('\033[0;32m' + "#" + " " + '\033[0m', end="")
            elif c == 1:
                print('\033[0;;40m' + " " * 2 + '\033[0m', end="")
            else:
                print(" " * 2, end="")
        print()

if __name__ == '__main__':
    maze=[[1,1,1,1,1,1,1,1,1,1,1,1,1,1],\
          [1,0,0,0,1,1,0,0,0,1,0,0,0,1],\
          [1,0,1,0,0,0,0,1,0,1,0,1,0,1],\
          [1,0,1,0,1,1,1,1,0,1,0,1,0,1],\
          [1,0,1,0,0,0,0,0,0,1,1,1,0,1],\
          [1,0,1,1,1,1,1,1,1,1,0,0,0,1],\
          [1,0,1,0,0,0,0,0,0,0,0,1,0,1],\
          [1,0,0,0,1,1,1,0,1,0,1,1,0,1],\
          [1,0,1,0,1,0,1,0,1,0,1,0,0,1],\
          [1,0,1,0,1,0,1,0,1,1,1,1,0,1],\
          [1,0,1,0,0,0,1,0,0,1,0,0,0,1],\
          [1,1,1,1,1,1,1,1,1,1,1,1,1,1]]
    start=(1,1)
    end=(10,12)
    #find_path(maze,start,end)
    find_path_A(maze, start, end)
    see_path(maze,path)