Skip to content
TheChatArchiveThe Chat Archive
Qwenqwen3-235b-a22b· Alibaba (Qwen)Hugging Face LMArena Human Preference 140K

请介绍下A*算法

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Metallama-4-maverick-17b-128e-instruct’s answer.
  1. User

    请介绍下A*算法

  2. Qwen Assistant

    A*(A-Star)算法是一种广泛应用于路径搜索的启发式搜索算法,能够高效地在复杂图或网格中找到从起点到终点的最短路径。它结合了Dijkstra算法(保证最优性)和贪心最佳优先搜索(提高效率)的优点,广泛用于游戏开发、机器人导航、地图导航等领域。


    核心思想

    A*算法通过评估函数 f(n)=g(n)+h(n)f(n) = g(n) + h(n) 来选择下一步扩展的节点:

    • g(n)g(n): 从起点到当前节点的实际代价。
    • h(n)h(n): 从当前节点到终点的启发式估计代价(需满足“不可高估”的条件,即可接受启发式)。
    • f(n)f(n): 总代价估计,用于决定搜索的优先级。

    算法步骤

    1. 初始化:

      • 开放列表(Open List):存放待探索的节点,初始时仅包含起点。
      • 关闭列表(Closed List):存放已探索的节点,初始为空。
      • 为每个节点记录 g(n)g(n)、h(n)h(n)、f(n)f(n),以及父节点(用于回溯路径)。
    2. 循环过程:

      • 从开放列表中取出 f(n)f(n) 最小的节点 nn(称为当前节点)。
      • 如果 nn 是终点,回溯父节点构建路径,算法结束。
      • 否则,将 nn 移入关闭列表,并遍历其所有相邻节点 n′n':
        • 如果 n′n' 在关闭列表中,跳过。
        • 如果 n′n' 是新节点或找到更短的路径(即 g(n′)>g(n)+cost(n→n′)g(n') > g(n) + \text{cost}(n \to n')),更新其 g(n′)g(n')、f(n′)f(n') 和父节点。
        • 将 n′n' 加入开放列表。
    3. 终止条件:开放列表为空(无路径可达)或找到终点。


    关键特性

    1. 启发函数 h(n)h(n) 的选择:

      • 可接受性:h(n)h(n) 必须小于等于实际剩余代价(不会高估)。
      • 一致性(单调性):若图中边的权重非负,且 h(n)h(n) 满足三角不等式,则A*无需重复访问节点。
      • 常见启发函数:
        • 曼哈顿距离(适合4方向网格移动):h(n)=∣x−xgoal∣+∣y−ygoal∣h(n) = |x - x_{\text{goal}}| + |y - y_{\text{goal}}|
        • 欧几里得距离(适合自由移动空间):h(n)=(x−xgoal)2+(y−ygoal)2h(n) = \sqrt{(x - x_{\text{goal}})^2 + (y - y_{\text{goal}})^2}
        • 切比雪夫距离(适合8方向移动):h(n)=max⁡(∣x−xgoal∣,∣y−ygoal∣)h(n) = \max(|x - x_{\text{goal}}|, |y - y_{\text{goal}}|)
    2. 效率与最优性:

      • 若 h(n)h(n) 是可接受的,A*保证找到最短路径。
      • 若 h(n)h(n) 估计值越大(但仍可接受),搜索效率越高(探索节点更少)。
    3. 与其他算法对比:

      • Dijkstra算法:h(n)=0h(n) = 0,仅按 g(n)g(n) 排序,保证最优但效率低。
      • 贪心最佳优先搜索:g(n)=0g(n) = 0,仅按 h(n)h(n) 排序,可能不最优。
      • A*:平衡效率与正确性,是两者的扩展。

    示例场景

    假设在2D网格地图中寻找路径:

    1. 起点为 SS,终点为 GG。
    2. 每个格子是节点,可上下左右移动(曼哈顿距离为启发函数)。
    3. A*会优先探索靠近终点且路径代价低的节点,逐步扩展搜索范围,最终找到最优路径。

    伪代码

    function A_Star(start, goal):
        open_list = [start]
        came_from = {}  # 记录路径
        g_score = {node: ∞ for node in all_nodes}
        g_score[start] = 0
        f_score = {node: ∞ for node in all_nodes}
        f_score[start] = h(start)
    
        while open_list is not empty:
            current = node in open_list with minimal f_score
            if current == goal:
                return reconstruct_path(came_from, current)
            
            remove current from open_list
            add current to closed_list
    
            for neighbor in neighbors(current):
                if neighbor in closed_list:
                    continue
                tentative_g = g_score[current] + cost(current, neighbor)
                if tentative_g < g_score[neighbor]:
                    came_from[neighbor] = current
                    g_score[neighbor] = tentative_g
                    f_score[neighbor] = tentative_g + h(neighbor)
                    if neighbor not in open_list:
                        add neighbor to open_list
    
        return failure  # 无路径
    

    优缺点

    • 优点:
      • 保证找到最优路径(若启发函数可接受)。
      • 比Dijkstra更高效,尤其在大地图中。
    • 缺点:
      • 内存消耗较大(需保存开放列表和关闭列表)。
      • 启发函数设计影响性能(若 h(n)h(n) 估计不准,效率下降)。

    应用场景

    • 游戏开发:NPC自动寻路、策略游戏单位移动。
    • 机器人路径规划:室内导航、避障路径生成。
    • 地图导航:GPS系统中的路线规划(结合交通数据优化启发函数)。

    通过合理设计启发函数,A*算法能够在复杂环境中高效找到最优路径,是路径搜索领域的经典算法。

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.