基于C#的AStar最短路径算法实现问题求助

核心问题诊断 #

你的代码存在几个关键问题，导致路径回溯逻辑失效且不符合A*算法的核心设计：

1. 单一路径递归，无回溯尝试：每次只选择当前节点的最优邻居递归，没有尝试其他可能的路径，一旦走死路就直接清空路径，忽略了回溯后探索其他邻居的可能
2. 错误的路径清空逻辑：遇死路时path.Clear()会清空整个路径，正确做法应该是移除当前节点，回到上一层继续探索
3. 全局修改节点状态：直接修改邻居节点的g和h值，会导致同一个节点被不同路径访问时状态混乱
4. Visited集合的误用：A*算法中不应将节点一旦标记为已访问就彻底排除，需要允许通过更优路径重新访问节点

修正步骤与代码实现 #

1. 调整Node类（避免全局状态污染）

将g和h改为临时计算值，不存储为节点成员，防止不同路径的计算互相干扰：

public class Node
{
    public string Name { get; private set; }    
    public Coordinate Location { get; private set; }
    public List<Node> Neighbours { get; set; }

    public Node(string name, Coordinate location)
    {
        Name = name;
        Location = location;
        Neighbours= new List<Node>();
    }

    public void AddNeighbours(List<Node> neighbours)
    {
        Neighbours.AddRange(neighbours);
    }

    public double distanceTo(Node node)
    {
        return Location.Distance(node.Location);
    }
}

2. 修正Graph类的递归A*实现

重点修复路径回溯逻辑，加入正确的递归返回判断与节点移除：

public class Graph
{
    List<Node> Nodes = new List<Node>();

    public Graph(List<Node> nodes) 
    { 
        Nodes = nodes; 
    }

    // 辅助字典存储节点的临时g、h值，避免修改节点本身
    private Dictionary<Node, double> _gScores = new Dictionary<Node, double>();
    private Dictionary<Node, double> _hScores = new Dictionary<Node, double>();

    public List<Node> GetShortestPath(Node source, Node destination)
    {
        _gScores.Clear();
        _hScores.Clear();
        _gScores[source] = 0;
        _hScores[source] = source.distanceTo(destination);
        
        return RecursiveAStar(source, destination, new HashSet<Node>(), new List<Node>());
    }

    private List<Node> RecursiveAStar(Node current, Node destination, HashSet<Node> closedSet, List<Node> currentPath)
    {
        if (current == destination)
        {
            currentPath.Add(destination);
            return new List<Node>(currentPath); // 返回路径副本，避免后续修改影响结果
        }

        closedSet.Add(current);
        currentPath.Add(current);

        // 计算所有邻居的g、h值，仅保留更优路径的数值
        foreach (var neighbour in current.Neighbours)
        {
            if (closedSet.Contains(neighbour)) continue;
            
            double tentativeG = _gScores[current] + current.distanceTo(neighbour);
            if (!_gScores.ContainsKey(neighbour) || tentativeG < _gScores[neighbour])
            {
                _gScores[neighbour] = tentativeG;
                _hScores[neighbour] = neighbour.distanceTo(destination);
            }
        }

        // 获取未访问且总代价最小的邻居列表
        var nextNodes = current.Neighbours
            .Where(n => !closedSet.Contains(n))
            .OrderBy(n => _gScores[n] + _hScores[n])
            .ToList();

        foreach (var nextNode in nextNodes)
        {
            var resultPath = RecursiveAStar(nextNode, destination, closedSet, currentPath);
            if (resultPath.Count > 0) // 找到有效路径，直接返回
            {
                return resultPath;
            }
        }

        // 所有邻居都探索完毕未找到路径，回溯：移除当前节点
        currentPath.Remove(current);
        closedSet.Remove(current); // 移除closedSet，允许其他路径再次访问该节点
        return new List<Node>(); // 返回空列表表示此路径无效
    }
}

关键逻辑说明 #

• 路径回溯：当当前节点的所有邻居都探索失败后，执行currentPath.Remove(current)将当前节点从路径中移除，回到上一层递归继续探索其他可能的邻居
• 状态隔离：使用字典_gScores和_hScores存储临时计算值，避免修改Node类的成员变量，防止不同路径的计算互相干扰
• 递归返回判断：每次递归调用后检查返回的路径是否有效（非空），有效则直接返回，无效则继续尝试下一个邻居
• ClosedSet的回溯：移除当前节点时同时从closedSet中移除，允许其他路径可能以更优方式重新访问该节点

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