A星算法算力优化实战：从原理到性能提升的关键技巧

1次阅读

共计 2139 个字符，预计需要花费 6 分钟才能阅读完成。

A 星算法（A*）本质上是 Dijkstra 算法的改进版，通过引入启发式评估函数来优先探索更有可能的路径。但新手实现时常常遇到这两个典型问题：

开放列表的频繁插入 / 删除操作导致 O(n)时间消耗
不合理的启发函数会使算法退化为广度优先搜索

通过 time 模块测试一个 100×100 网格的基准实现，平均耗时达到 2.3 秒，这显然无法满足实时路径规划的需求。

启发函数 h(n)的选取直接影响算法效率，以下是常见距离公式的实测对比：

启发函数类型	计算方式	扩展节点数	耗时(ms)
曼哈顿距离		x1-x2	+
欧几里得距离	sqrt((x1-x2)²+(y1-y2)²)	1653	520
切比雪夫距离	max(	x1-x2	,

注意：在允许对角移动的场景中，欧几里得距离更准确但计算开销较大。

标准 Python 的 heapq 模块虽能实现优先队列，但无法直接更新节点权重。这里给出改进版的二叉堆实现：

class PriorityQueue:
    def __init__(self):
        self.nodes = []
        self.entry_finder = {}  # 节点快速查找表

    def push(self, node, priority):
        if node in self.entry_finder:
            self.remove(node)
        entry = [priority, node]
        heapq.heappush(self.nodes, entry)
        self.entry_finder[node] = entry

    def remove(self, node):
        entry = self.entry_finder.pop(node)
        entry[-1] = REMOVED  # 标记为已移除

    def pop(self):
        while self.nodes:
            priority, node = heapq.heappop(self.nodes)
            if node is not REMOVED:
                del self.entry_finder[node]
                return node
        raise KeyError('pop from empty queue')

跳跃点预处理：识别地图中的关键转折点，减少搜索节点
分层路径规划：先粗粒度规划再局部细化
缓存常用路径：建立 LRU 缓存存储高频路径

引入权重系数 ω 实现动态调整：

def heuristic(a, b, ω=1.0):
    dx, dy = abs(a.x - b.x), abs(a.y - b.y)
    return ω * (dx + dy)  # 曼哈顿距离基础

在算法初期使用较大 ω(如 1.5)加速探索，接近目标时减小 ω 提高精度。

import heapq
from collections import defaultdict

class OptimizedAStar:
    def __init__(self, grid):
        self.grid = grid
        self.width = len(grid[0])
        self.height = len(grid)
        self.cache = defaultdict(dict)  # 路径缓存

    def find_path(self, start, end):
        # 优先检查缓存
        if end in self.cache[start]:
            return self.cache[start][end]

        open_set = PriorityQueue()
        open_set.push(start, 0)
        came_from = {}
        g_score = {start: 0}

        while open_set:
            current = open_set.pop()

            if current == end:
                path = self.reconstruct_path(came_from, end)
                self.cache[start][end] = path  # 写入缓存
                return path

            for neighbor in self.get_neighbors(current):
                tentative_g = g_score[current] + 1
                if neighbor not in g_score or tentative_g < g_score[neighbor]:
                    came_from[neighbor] = current
                    g_score[neighbor] = tentative_g
                    # 动态调整启发函数权重
                    weight = 1.5 if tentative_g < 20 else 1.0
                    f_score = tentative_g + weight * self.heuristic(neighbor, end)
                    open_set.push(neighbor, f_score)

        return None  # 无路径