A*（AStar）算法总结

本文主要是介绍A*（AStar）算法总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

简介

A* 算法（念做：A Star）是一种常用的路径查找和图形遍历算法，具有较好的性能和准确度。让我为您简要介绍一下 A* 算法的原理和实现。

广度优先搜索：
广度优先搜索以广度作为优先级进行搜索。从起点开始，首先遍历起点周围邻近的点，然后再遍历已经遍历过的点邻近的点，逐步向外扩散，直到找到终点。
这种算法类似于洪水（Flood fill）一样向外扩张。
Dijkstra 算法：
Dijkstra 算法用于寻找图形中节点之间的最短路径。
考虑到不同节点之间的移动代价可能不相等，Dijkstra 算法需要计算每个节点距离起点的总移动代价。
A * 算法：
A* 算法综合了广度优先搜索和 Dijkstra 算法的特点。
它通过一个启发函数来计算每个节点的优先级，综合考虑节点距离起点的代价和距离终点的预计代价。
A* 算法在运算过程中，每次从优先队列中选取优先级最高的节点作为下一个待遍历的节点。
启发函数可以根据不同情况选择曼哈顿距离、对角距离或欧几里得距离。

实现代码

public class Node
{public int X { get; set; }public int Y { get; set; }public double G { get; set; } // 从起点到该节点的代价public double H { get; set; } // 启发式估计的终点代价public double F => G + H; // 总代价 (F = G + H)public Node Parent { get; set; } // 路径中的父节点
}

public class AStar
{private readonly int[,] _grid; // 您的网格或地图private readonly int _width;private readonly int _height;public AStar(int[,] grid){_grid = grid;_width = grid.GetLength(0);_height = grid.GetLength(1);}public List<Node> FindPath(Node start, Node goal){var openSet = new List<Node> { start }; // 待探索的节点集合var closedSet = new HashSet<Node>(); // 已探索的节点集合while (openSet.Count > 0){var current = openSet[0];for (var i = 1; i < openSet.Count; i++){if (openSet[i].F < current.F)current = openSet[i];}openSet.Remove(current);closedSet.Add(current);if (current == goal)return ReconstructPath(current);foreach (var neighbor in GetNeighbors(current)){if (closedSet.Contains(neighbor))continue;var tentativeG = current.G + GetDistance(current, neighbor);if (tentativeG < neighbor.G || !openSet.Contains(neighbor)){neighbor.Parent = current;neighbor.G = tentativeG;neighbor.H = GetDistance(neighbor, goal);if (!openSet.Contains(neighbor))openSet.Add(neighbor);}}}return null; // 未找到路径}private List<Node> ReconstructPath(Node node){var path = new List<Node> { node };while (node.Parent != null){node = node.Parent;path.Insert(0, node);}return path;}private IEnumerable<Node> GetNeighbors(Node node){// 实现获取有效邻居的逻辑var neighbors = new List<Node>();// 例如，检查相邻单元格并避开障碍物// 返回有效邻居节点的列表// 示例：检查上、下、左、右四个方向int[] dx = { -1, 1, 0, 0 };int[] dy = { 0, 0, -1, 1 };for (int i = 0; i < 4; i++){int newX = node.X + dx[i];int newY = node.Y + dy[i];if (IsValid(newX, newY)) // 检查是否在网格范围内且可行走neighbors.Add(new Node { X = newX, Y = newY });}return neighbors;}private double GetDistance(Node a, Node b){// 实现您的距离启发式函数（例如，曼哈顿距离、欧几里得距离）// 返回节点 a 和 b 之间的估计距离// 示例：曼哈顿距离return Math.Abs(a.X - b.X) + Math.Abs(a.Y - b.Y);}private bool IsValid(int x, int y){// 检查坐标是否在网格范围内且可行走return x >= 0 && x < _width && y >= 0 && y < _height && _grid[x, y] == 0;}
}

测试代码

    public void Test(){// 示例用法：var grid = new int[,]{// 您的网格数据（0 = 可行走，1 = 障碍物等）// 根据实际情况初始化};var startNode = new Node { X = 0, Y = 0 };var goalNode = new Node { X = 5, Y = 5 };var astar = new AStar(grid);var path = astar.FindPath(startNode, goalNode);}

介绍A*的博客

这篇关于A*（AStar）算法总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---