改进A星算法路径规划 1.删去离障碍物太近的节点 2.引入启发函数动态权重 3.冗余点处理 以及接5*5邻域(16邻域)，7*7邻域（32邻域)等改进A星

在路径规划领域，A星算法堪称经典，但随着实际应用场景复杂度的提升，对其进行改进显得尤为必要。今天咱们就来唠唠几种对A星算法的优化思路，包括节点筛选、启发函数调整、冗余点处理，以及不同邻域设置带来的改进。

一、删去离障碍物太近的节点

在实际场景中，靠近障碍物的节点往往不是最优路径的选择，甚至可能把算法引入死胡同。通过提前筛除这些节点，可以大大减少算法的搜索空间，提升效率。

假设我们有一个表示地图的二维数组map，值为1表示障碍物，0表示可通行区域。以下是简单的Python代码示例，用于判断节点是否离障碍物太近：

def is_close_to_obstacle(node, map, threshold):
    x, y = node
    rows, cols = len(map), len(map[0])
    for i in range(max(0, x - threshold), min(rows, x + threshold + 1)):
        for j in range(max(0, y - threshold), min(cols, y + threshold + 1)):
            if map[i][j] == 1:
                return True
    return False

在A星算法搜索节点时，就可以调用这个函数：

# 在A星算法的节点生成过程中
new_node = (x, y)
if not is_close_to_obstacle(new_node, map, 2): # 这里阈值设为2
    # 将new_node加入待扩展节点列表
    open_list.append(new_node)

分析：上述代码通过双重循环遍历以当前节点为中心，边长为2 * threshold + 1的方形区域，检查是否存在障碍物。如果存在，说明该节点离障碍物太近，应被舍弃。

二、引入启发函数动态权重

启发函数在A星算法中用于引导搜索方向，传统的启发函数权重往往是固定的。但在一些复杂环境中，固定权重无法灵活适应不同的地形或需求。引入动态权重可以让启发函数根据实际情况调整。

假设我们有一个简单的启发函数heuristic，通常使用曼哈顿距离或欧几里得距离。现在，我们让权重weight根据节点与目标点的距离动态变化：

import math

def heuristic(node, goal, weight):
    x1, y1 = node
    x2, y2 = goal
    return weight * math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2) # 这里用欧几里得距离举例

在A星算法中，我们根据节点与目标点的距离动态调整权重：

# 在A星算法计算节点代价时
distance_to_goal = heuristic(current_node, goal, 1)
if distance_to_goal > some_threshold:
    weight = 1.5
else:
    weight = 1
f_value = g_value + heuristic(current_node, goal, weight)

分析：上述代码中，当节点离目标点较远时，增加启发函数的权重，让算法更倾向于朝着目标点快速搜索；当节点离目标点较近时，减小权重，使算法更注重局部最优解，避免错过最优路径。

三、冗余点处理

在A星算法生成的路径中，可能存在一些冗余点，这些点对于路径的连通性没有实质影响，但会增加路径长度和计算量。

一种简单的冗余点处理方法是使用“直线检测”。假设我们有一条路径path，由一系列节点组成：

def remove_redundant_points(path):
    new_path = [path[0]]
    for i in range(2, len(path)):
        p1 = path[i - 2]
        p2 = path[i - 1]
        p3 = path[i]
        if (p3[1] - p1[1]) * (p2[0] - p1[0])!= (p2[1] - p1[1]) * (p3[0] - p1[0]):
            new_path.append(path[i - 1])
    new_path.append(path[-1])
    return new_path

分析：这段代码通过判断三个连续节点是否共线来决定是否删除中间节点。如果不共线，则保留中间节点，否则说明该节点是冗余的，可被删除。这样可以在不改变路径连通性的前提下，简化路径。

四、5*5邻域(16邻域)，7*7邻域（32邻域)等改进A星

传统A星算法通常使用4邻域（上下左右）或8邻域（包括对角线）进行节点扩展。而增加邻域范围，如55邻域（16邻域，除去中心节点本身）或77邻域（32邻域，除去中心节点本身），可以让算法在搜索时拥有更多选择，可能找到更优路径。

以5*5邻域为例，生成邻域节点的代码如下：

def get_5x5_neighbors(node):
    x, y = node
    neighbors = []
    for i in range(x - 2, x + 3):
        for j in range(y - 2, y + 3):
            if (i, j)!= node and 0 <= i < rows and 0 <= j < cols:
                neighbors.append((i, j))
    return neighbors

在A星算法扩展节点时，使用这个函数替换原来的邻域获取函数：

# 在A星算法扩展节点步骤
current_node = open_list.pop(0)
neighbors = get_5x5_neighbors(current_node)
for neighbor in neighbors:
    if neighbor not in closed_set:
        # 计算邻居节点的g、h、f值，并加入open_list

分析：通过扩大邻域范围，算法在每一步搜索时有更多的节点可供选择，增加了找到更优路径的可能性。但同时，由于需要处理更多的节点，计算量也会相应增加，所以在实际应用中需要权衡计算资源和路径优化程度。

通过以上几种改进，A星算法在复杂环境下的路径规划能力得到显著提升，无论是搜索效率还是路径质量都有可观的改善。希望这些思路能给大家在相关领域的应用开发带来一些启发。