求Julia中支持A*搜索的动态生成无限无向图相关库及资料

核心需求概述 #

你需要针对无限无向动态图（以整数格点的骑士移动图为例）实现A*最短路径搜索，且希望使用Julia生态中的现成库替代自行实现的代码。这类图无需预先构建完整结构，仅通过动态生成邻居节点、边权重及启发式函数来运行算法。

Julia中可用的A*搜索库及适配方案 #

1. Graphs.jl（核心图论生态） #

Graphs.jl是Julia最成熟的图论库，内置a_star函数，完美支持动态生成的无限图：

• 无需预先构建图对象，只需实现三个关键函数：
  • neighbors(v)：返回顶点v的所有邻接节点（如骑士移动的8个格点）
  • edge_weight(u, v)：返回边u-v的权重（此处固定为1）
  • 可选的启发式函数heuristic(a, b)：用于加速搜索，需满足可采纳性（不高估实际路径长度）
• 顶点类型建议使用Tuple{Int,Int}而非数组，因为元组可被哈希，能作为算法中已访问集合的键。

2. Pathfinding.jl（专用路径规划库） #

该库专注于路径搜索算法，提供的A*实现对动态图的支持更轻量化：

• 无需依赖图结构，直接基于邻居生成函数、权重函数和启发式函数运行
• 内置了常见路径规划场景的工具，适合快速适配骑士移动这类网格问题

3. SimpleWeightedGraphs.jl #

作为Graphs.jl的扩展，它支持带权图的操作，同样可通过动态函数适配无限图：

• 虽然名称包含"Simple"，但允许通过函数式方式动态提供邻居和权重，无需预先构建完整图

关键实现要点 #

• 启发式函数的可采纳性：以骑士移动为例，可使用以下启发式（永远不高估实际步数）：

  function knight_heuristic(a::Tuple{Int,Int}, b::Tuple{Int,Int})
      dx = abs(a[1] - b[1])
      dy = abs(a[2] - b[2])
      # 基于骑士移动特性的启发式计算
      return ceil(max(dx, dy) / 2)
  end
  

• 避免无限循环：A*算法会自动维护已访问节点集合，仅生成当前路径所需的邻居节点，不会遍历整个无限图

示例代码（基于Graphs.jl） #

using Graphs

# 动态生成骑士移动的邻居节点
function knight_neighbors(v::Tuple{Int,Int})
    x, y = v
    return [
        (x+1, y+2), (x+2, y+1),
        (x+2, y-1), (x+1, y-2),
        (x-1, y-2), (x-2, y-1),
        (x-2, y+1), (x-1, y+2)
    ]
end

# 定义边权重（骑士移动每条边权重为1）
function knight_weight(u, v)
    return 1.0
end

# 可采纳的启发式函数
function knight_heuristic(a, b)
    dx = abs(a[1] - b[1])
    dy = abs(a[2] - b[2])
    return ceil(max(dx, dy) / 2)
end

# 运行A*搜索
start = (3, 4)
goal = (10, 10)
path = a_star(start, goal, knight_neighbors, knight_weight, knight_heuristic)

println("最短路径步数：", length(path) - 1)
println("路径节点：", path)

内容的提问来源于stack exchange，提问作者jeffgroves