Astar算法求解迷宫最短路 | Python实现

实验内容

给定一个二维数组模拟迷宫，0表示允许通过，1表示有障碍无法通过。

给定一个起点(x0, y0)和终点(x1, y1)，设计两种不同估价函数的A*算法，找到从起点走到终点的路径。

输入

Problem2.txt

• 第一行给入口坐标x0, y0
• 第二行给出口坐标x1, y1
• 下面n行给一个n*m的0-1矩阵，表示迷宫

1,1

5,5

0 0 0 0 0

1 0 1 0 1

0 0 1 1 1

0 1 0 0 0

0 0 0 1 0

输出

Astar.txt

• 共需要多少步
• 路径坐标序列

共需13步

(1,1)-(1,2)-(2,2)-(3,2)-(3,1)-(4,1)-(5,1)-(5,2)-(5,3)-(4,3)-(4,4)-(4,5)-(5,5)

Astar算法

原理简介

A*算法是一种求解最短路径的直接搜索方法，是许多其他问题的常用启发式算法。

算法的核心公式$f(n) = g(n) + h(n)$

• f(n)是从初始状态经由状态n到目标状态的代价估计，简写为F
• g(n)是在状态空间中从初始状态到状态n的实际代价，简写为G
• h(n)是从状态n到目标状态的最佳路径的估计代价，简写为H

通过计算这三个值，我们可以找到更具有更高尝试价值的路径。

会有两个数组来存储一些结点

• open list：待检查的结点列表，路径可能经过，也可能不经过
• close list：已经检查完毕的结点列表

搜索过程

1. 把起点加入open list
2. 循环
   • 遍历open list，查找F值最小的结点，把它作为当前要处理的结点
   • 把这个结点移到close list
   • 遍历当前这个结点四周的八个结点
     • 如果结点不可达或者它已经在close list中，就忽略
     • 如果它不在open list中，就加入open list中，并且把当前的结点设置成它的父节点，记录该结点的F, G, H值
     • 如果它已经在open list中，检查这条路径是否更好，以G值作为参考。G值越小表示路径越好。如果更好，就把它的父结点设置成当前的方格，并且重新计算G和F值。
   • 退出循环的情况
     • 终点已经在open list中，说明已经找到了路径
     • open list为空，表示已经没有路可以走了
3. 保存路径

数据结构

为了方便记录每个点的父节点以及计算F, G, H值，需要自己定义一个结点类

class Node:

1. 定义结点类的构造方法

   1 2 3 4 5

   def __init__(self, x, y): self.pre = None self.x = x self.y = y self.update()

2. 更新启发函数的值

   • 首先计算H的值，有两种方式

     1. 当前结点到目标结点的曼哈顿距离

        abs(node.x - target[0])+abs(node.y - target[1])

     2. 当前结点到目标结点的欧式距离

        (node.x - target[0])**2+(node.y - target[1])**2

   • 再计算G的值，即深度，这里指当前走的步数

   • 最后计算启发函数的值，F = G + H

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

   # 更新启发函数的值 def update(self): self.update_H() self.update_G() self.update_F() # H值是和目标状态的距离之和 def update_H(self): # 用曼哈顿距离表示和目标的距离之和 x, y = self.x, self.y self.H = abs(x - target[0]) + abs(y - target[1]) # G值表示深度，即当前走的步数 def update_G(self): if self.pre: self.G = self.pre.G + 1 else: self.G = 0 # F是启发函数 F = G + H def update_F(self): self.F = self.G + self.H

3. 输出路径

   1 2 3 4 5 6 7 8 9 10 11

   # 输出路径 def get_path(self): nodes = [] node = self while node: nodes.append(node) node = node.pre res = [] for i in nodes[::-1]: res.append("(" + str(i.x) + "," + str(i.y) + ")") return res

4. 返回下一步可能所在的位置坐标

   • directions是我们自己定义的一个数组，用来快速向四个方向扩散

     directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

   1 2 3 4 5 6 7 8 9 10

   # 找到下一步可能所在的位置 def get_next_positions(self): next_positions = [] for i, j in directions: next_x = i + self.x next_y = j + self.y if next_x >= 0 and next_x < len(maze) and next_y >= 0 and next_y < len(maze[0]): if maze[next_x][next_y] == 0: next_positions.append([next_x, next_y]) return next_positions

I/O相关

1. 从文件中读取文本

   1 2 3 4 5

   def read_file(file_name): lines = [] with open(file_name, encoding="utf-8") as f: lines = f.readlines() return lines

2. 根据读取的文本生成迷宫

   1 2 3 4 5 6 7

   def get_maze(lines): matrix = [] for line in lines[2:]: line = line.strip() tmp = [int(i) for i in line.split(" ")] matrix.append(tmp) return matrix

3. 写文件

   1 2 3 4

   def write_file(file_name, lines): with open(file_name, 'w', encoding="utf-8") as f: for line in lines: f.write(str(line))

Astar搜索函数

根据算法描述转换成代码实现即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

def a_star(x0, y0):
    open_list, close_list = [], []
    # 初始化起点结点
    node = Node(x0, y0)
    open_list.append(node)
    while open_list:
        # 按照启发函数的值升序进行排列
        open_list.sort(key = lambda x: x.F)
        # 找到F值最小的结点，尝试扩展
        cur_node = open_list[0]
        # 确认是否是终点
        if cur_node.H == 0:
            print("wow, we find the path!")
            return cur_node.get_path()
        # 对当前这个F值最小的结点尝试搜索
        open_list.pop(0)
        close_list.append(cur_node)
        # 获取下一步可能的位置
        next_positions = cur_node.get_next_positions()
        for next_position in next_positions:
            x, y = next_position
            # 把下一个位置初始化为一个结点next_node
            next_node = Node(x, y)
            # 把cur_node设置成next_node结点的父节点
            next_node.pre = cur_node
            # 更新一下F G H值
            cur_node.update()
            # 判断next_node在close_list和open_list中的情况
            open_res = in_list(next_node, open_list)
            close_res = in_list(next_node, close_list)
            open_idx = open_res[1]
            # 如果在close_list中说明已经检查完毕，跳过即可
            if close_res[0]:
                continue
            # 如果在open_list中，需要判断是否更优
            if open_res[0] and next_node.F < (open_list[open_idx]).F:
                open_list[open_idx] = next_node
            # next_node不在open_list也不在close_list中
            if not open_res[0] and not close_res[0]:
                open_list.append(next_node)

• main函数

1
2
3
4
5
6
7
8
9
10
11
12
13

if __name__ == "__main__":
    lines = read_file("Problem2.txt")
    maze = get_maze(lines)
    start, end = lines[0].rstrip(), lines[1].rstrip()
    start = start.split(",")
    end = end.split(",")
    x0, y0, x1, y1 = int(start[0])-1, int(start[1])-1, int(end[0])-1, int(end[1])-1
    target[0], target[1] = x1, y1
    path = a_star(x0, y0)
    lines = []
    lines.append("共需" + str(len(path)) + "步\n")
    lines.append("-".join(path))
    write_file("Astar.txt", lines)

运行结果

为了明显对比出两个启发函数的区别，我自己构造了一个2640*10的迷宫（没使用并查集，只是随便复制的）

• 起点1，1
• 终点2639，10，图中圈出来的那个

1. 以曼哈顿距离作为启发函数

   

   

2. 以欧式距离的平方作为启发函数

   

   

多次实验发现，在当前迷宫中，曼哈顿距离的启发函数花的时间远超欧氏距离的启发函数。

当然，这并不能直接的出哪个函数更优秀的结论，由于我本身只自定义了一个迷宫