A-star_Search

Marcus

2023-07-28

computer

A*寻路算法的基本思想和基本代码实现：

关于寻路算法有许多不同的答案，像广度搜索，深度搜索、跳点搜索算法、弗洛伊德等等算法，但今天我们主要讲一个常用的算法A*(A-star)算法。

A*算法是建立在曼哈顿度量（又名出租车度量或者出租车几何）他有个非常好的性质，相比欧几里得度量来说，出租车度量更适合现实的空间。所以，我们首先来介绍一下曼哈顿度量

度量空间和曼哈顿距离

一个度量空间指的是具备距离的集合，它的元素是点。而其中距离也叫距离函数，在接下来的代码里面我们会给出一个简单的空间例子，但最主要的还是关注这个度量空间的距离函数。

度量具备四个良好性质

非负性
三角不等式
对称性
对于任意的都有

在算法中我们一般会想无视障碍物获取与终点的最短路径，这个时候就考虑使用欧几里得度量（或者欧几里得距离）

欧几里得距离（距离）

定义：距离被定义为映射，它由函数：

定义，实际上就是我们一般说的向量的点积。

而现在我们定义出租车度量(度量)由函数

定义的。

我们如此定义这个函数，是因为当出租车从一点驶向另一点的时候，如果只能沿着坐标方向（北、南、东、西）而不允许走对角线，那么出租车驶过的距离就可以用曼哈顿距离计算。

算法的简单介绍

广度优先搜索算法

广度优先搜索算法（Breadth-first search，缩写为BFS） BFS是从根节点开始，沿着树的宽度遍历树的结点，当我们遍历完树的全部节点或者遍历到我们想要的节点，则算法终止。

举个例子，我们假设有一个迷宫，迷宫由一个起点和一些格子，格子上有的标记为障碍物。当我们走到岔路口的时候，会放弃继续进入岔路口，而是回头继续探索别的路直到碰到岔路口，然后重复这个过程直到遍历到终点，这个算法的好处就是他找到的第一条路就是最短路径。但是耗费的时间会很多。

A-star算法的简单描述和场景设置

为了算法的实现，我们首先把空间抽象成一个由二维格子组成的二维平面，为了描述我们要做的东西，

估价函数

为了不像广度搜索算法一样盲目乱走，如何选择格子去走就成了第一个问题，这也就是为什么要对格子进行估价的原因，那么我们定义一个比较简单的东西。

我们给每个格子都定义一些代价，即从起点到格子的之间格子的数量，记为，再定义
格子到终点之间隔了多少个格子的数量，记为

那么定义估价函数为

现在看个例子：

橙色格子要移动到1号格子，那么它只需移动一步，因此，但1号格子它离红色格子的直线距离为个格子
进一步的，对于2，3格子，格子的估阶函数是，则

+对于4号格子，我们可以得到

因此，根据估阶函数给出的值我们大概知道

所以我们优先考虑格子3。现在我们发现两个问题

计算的过程中伴随开方和根号运算，需要使用浮点数。
实际的过程我们并不能平滑的移动到红色格子，需要水平+对角移动相结合，例如格子3到终点的距离实际上是：，因为要翻跃障碍物。

所以，这就是为什么我一开始就侧重讲曼哈顿度量的原因，它更符合我们的想法。

因此，曼哈顿度量是小于等于欧拉度量的。

对选择的影响

我们假设有一个棋盘，设起点为，终点为代表第4行的第六个格子。再任取两个格子和。

障碍物为如下四个格子：

不妨计算一下它们的估阶函数，，因为是朝上边和右边走两格就到了。然后我们计算的曼哈顿度量。，这出现了一个问题，我们不知道如何选择最优路径。因为它们的估阶函数一样。现在，让我们计算它们的对角线距离

所以，我们更应该选择格子为最优路径，实际上这也确实是对的。因为格子D的实际距离为稍微比对角线距离大点。所以我们得到

曼哈顿距离>实际距离>对角线距离

现在该总结一下了

若到终点的实际距离，那么A*可以找到最短路径，但随着搜索的点越多，范围就越大效率也越低
若到终点的实际距离，则搜索的点少，搜索范围小，效率高，但不一定是最优解。
实际距离，那么算法越完美。
若，这说明，那么会发生一种情况，算法会毫无目的的在四周搜索。
若，那么的大头主要看，这就变成了广度优先算法。

具体的寻路过程

还是那个例子：

它们的估阶函数如下：

1：
2：
3：
4：
5：

若在相同的时候，我们考虑的值。根据，那么实际上我们选择格子，然后我们进行下一步，

第二步：我们走到第三个格子后，又产生了新的路径选择，如下图所示：

于是，我们再次计算格子的估阶函数，这次注意的是，是障碍，所以不需要考虑这两个格子。格子实际上就是起点，所以也不需要考虑，我们只需要考虑三个格子就行了，它们的估阶函数为：

正如我们刚才所说，我们计算的是起点到格子的距离，是终点的，但现在情况不一样，我们已经走了一格，所以到起点的路也必须经过我们走过的格子，所以，实际上应该在上加,也是一样的道理，但不用，因为它本身就包含了走过的格子的距离，那么更新后的为
。所以我们这次选择号格子。

然后我们不断的重复这个步骤直到遍历到终点。

然后只需要根据格子一路前进即可得到最优路线。当然，如果使用曼哈顿距离，我们可以得到更简单的表达方法。但是不能走斜线。

代码编写环节

初始化

我们先初始化一些参数，定义一个类Node

class Node:
    def __init__(self,x,y):
        self.x = x #纵坐标
        self.y=y #横坐标
        self.g =0 #代价g
        self.h=0 #代价h
        self.parent = None #初始化父节点

然后我们定义一个估阶函数

1 2	def f(self): return self.g+self.h

并使用曼哈顿度量作为标准度量

def heuristic(node,goal): 
#node 是当前节点的坐标信息
#goal 指的是目标节点的坐标信息
 return abs(node.x - goal.x) + abs(node.y - goal.y)
#它返回目标和当前节点的距离

最后我们定义估阶函数的对比函数

1
2
3

def __lt__(self, other):
    # 实现节点的比较方法，使用 f() 函数值进行比较
    return self.f() < other.f()

初始化到这里就差不多了，接下来让我们进入到下一个部分

准备

我们需要判断当前节点的临近节点状态，看看是否有超过地图的，那么定义函数

def get_neighbors(node,grid):
    neighbors = []
    for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
        x,y = node.x+dx, node.y+dy
        if 0<= x <len(grid) and 0 <= len(grid[0]) and not grid[x][y]:
            neighbors.append(Node(x, y))
    return neighbors

这里重点解释一下这个if语句，前面两个是检测是否超过边界，而我们的重点在最后一个条件。由于我们是用一个二维矩阵（二维数组）表示的地图，而每个点表示数组上的一个数字（1表示障碍物，0表示通道）因此在这里我们用not 符号检测点是否为障碍物，若为1，not后是0（等价于布尔值的 false，不满足条件，因此不会计入neighbors组中）

如果我们已经遍历完成且找到终点了呢？那么现在我们定义回溯函数，它被用来从终点找到返回起点的最短路径。

def reconstruct_path(node);
    path = []
    while node:
        path.append((node.x, node.y))
        node = node.parent
    return path[::-1]

它被设定用来接收每一个路径上的节点并反向的打印。

A-star 搜索实现

最后，我们来定义搜索函数

def a_star_search(grid,start,goal): #把地图，起点，终点当成参数
    open_list = [] #储存待探索的节点
    closed_list = []#储存已探索的节点

    start_node = Node(start[0],start[1]) #start是一个包含两个元素的一维数组，这里是传入第一个和第二个元素作为点的坐标 
    goal_node = Node(goal[0],goal[1])
    heapq.heappush(open_list, (start_node.f(), start_node))  # 将起始节点加入 open_list

    while open_list:
        _, current_node = heapq.heappop(open_list)
        if(current_node.x,current_node.y) == (goal_node.x,goal_node.y) #判断是否为终点
            return reconstruct_path(current_node)
         closed_set.add((current_node.x, current_node.y))  # 将当前节点加入已探索集合
        for neighbor in get_neighbors(current_node, grid):
            if (neighbor.x, neighbor.y) in closed_set:
                continue  # 如果邻居节点已探索过，跳过本次循环

            tentative_g = current_node.g + 1  # 这里假设每一步的代价都是 1

            if (neighbor.f(), neighbor) in open_list:
                # 如果邻居节点已经在 open_list 中，更新代价和父节点
                if neighbor.g > tentative_g:
                    neighbor.g = tentative_g
                    neighbor.parent = current_node
            else:
                # 否则，将邻居节点加入 open_list，并设置代价和父节点
                neighbor.g = tentative_g
                neighbor.h = heuristic(neighbor, goal_node)
                neighbor.parent = current_node
                heapq.heappush(open_list, (neighbor.f(), neighbor))

    return None  # 如果 open_list 为空，则无法找到路径，返回 None

最后，我们需要将三个参数传入搜索函数，我们定义

grid = [
    [0, 0, 0, 0, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 1, 0, 0]
]

start = (0, 2)
goal = (4, 1)

第一个是地图，第二个是起点，第三个是终点。
最后调用函数

1 2	path = a_star_search(grid, start, goal) print(path)

那么理论上它输出

1 2	[(0, 2), (0, 1), (1, 1), (2, 1), (3, 1), (4, 1)]