A*算法

发表于 2023-02-08 更新于 2024-04-12 分类于算法阅读次数：本文字数： 649 阅读时长 ≈ 2 分钟

概述

基本过程可描述为：每次寻找f(n)最小的点探索。

核心为： f(n) = g(n) + h(n)

其中: - f(n): 表示从起点到任意顶点n的分值、权重 - g(n): 表示从起点到任意顶点n的实际距离 - h(n): 表示任意顶点n到目标顶点的估算距离（根据所采用的评估函数的不同而变化）

这个公式遵循以下特性： - 如果g(n)为0: 即不计算起点到n点的实际距离，只考虑n到终点的预估距离，算法变为贪心算法，快，但是不一定能找到结果 - 如果h(n)为0: 即不计算n到终点的估算距离，转化为Dijkstra算法

伪码

def aStar(graph, start, end):
  def heuristic_cost_estimate(s, d):
    pass
  openSet = set()  # 待访问的节点
  openSet.add(start)
  closeSet = set() # 已经访问过的节点

  gScore = {} # 保存g(n)的分数
  gScore[start] = 0 # 起点实际花费=0

  fScore = {} # 保存f(n)的分数
  fScore[start] = heuristic_cost_estimate(start, end) # 因为g(start) = 0, 所以 f(start) = h(start)

  cameFrom = {} # 记录每个点的父节点

  while openSet:
    current = extract_minCost_of_openSet(openSet)  # 从openset中获取开销最小的节点(从源点到当前点n的距离最短的)
    if current == end:  # 成功找到最短路径
      return reconstruct_path(cameFrom, current)
    openSet.remove(current)
    closeSet.add(current)

    for neighbor in get_all_neighbors(graph, current):
      if neighbor in closeSet:
        continue
      if neighbor_can_pass(neighbor):
        gScore[neighbor] = gScore[current] + distance(current, neighbor)
        
        cameFrom[neighbor] = current
        # f(n) = g(n) + h(n)
        fScore[neighbor] = gScore[neighbor] + heuristic_cost_estimate(neighbor, end)
        openSet.add(neighbor)

python实现


from typing import Tuple, List

NodeT = Tuple[int, int]

def aStar(graph: List[List[int]], start: NodeT, end: NodeT):
  def heuristic_cost_estimate(s, d):
    # 这里可以有多种不同预估方法
    return abs()
  openSet = set()  # 待访问的节点
  openSet.add(start)
  closeSet = set() # 已经访问过的节点

  gScore = {} # 保存g(n)的分数
  gScore[start] = 0 # 起点实际花费=0

  fScore = {} # 保存f(n)的分数
  fScore[start] = heuristic_cost_estimate(start, end) # 因为g(start) = 0, 所以 f(start) = h(start)

  cameFrom = {} # 记录每个点的父节点

  while openSet:
    current = extract_minCost_of_openSet(openSet)  # 从openset中获取开销最小的节点(从源点到当前点n的距离最短的)
    if current == end:  # 成功找到最短路径
      return reconstruct_path(cameFrom, current)
    openSet.remove(current)
    closeSet.add(current)

    for neighbor in get_all_neighbors(graph, current):
      if neighbor in closeSet:
        continue
      if neighbor_can_pass(neighbor):
        gScore[neighbor] = gScore[current] + distance(current, neighbor)
        
        cameFrom[neighbor] = current
        # f(n) = g(n) + h(n)
        fScore[neighbor] = gScore[neighbor] + heuristic_cost_estimate(neighbor, end)
        openSet.add(neighbor)

`A*`算法与`Dijkstra`算法的区别

Dijkstra算法属于广度优先BFS
A*算法在Dijkstra算法 h(n) = g(n)的基础上加入了h(n), 预估节点到终点的距离, 实现了类似贪心和深度优先DFS的路径查找, 如果 h(n)=0, 则A*算法=Dijkstra算法

0%