为什么我的 A* 实现没有找到最短路径而是找到第一条路径？

Question

这是正在发生的事情的视觉表示

由于某种原因，我的实现似乎没有计算最短路径，而是计算它找到的第一条路径，我似乎不明白为什么。

有什么我错过的非常明显的事情吗？

这是我学习时做的笔记，这就是我一直在复习的内容

1. 使用起始节点和空闭集初始化开集。

2. 当开集不为空时，选择从起始节点到达目标节点的成本最低的节点，加上从该节点到达目标节点的估计成本，并将其从开集中删除。

3. 如果所选节点是目标节点，则算法终止，并从目标节点追溯到起始节点。

4. 否则，将所选节点添加到闭集并评估其邻居节点。对于不在封闭集中且不是障碍物的每个相邻节点，使用启发式函数计算从起始节点到达该节点的暂定成本以及从该节点到达目标节点的估计成本。如果相邻节点尚不存在于开集中，则将其添加到开集中。

5. 重复步骤2-4，直到找到目标节点或开集为空。

A*算法应该保证它会找到从起始节点到目标节点的最短路径，只要启发式函数是可接受的（即它永远不会高估到达目标节点的实际成本）并且网格不包含循环或负边权重。

public class World
{
    public int Width { get; set; }
    public int Height { get; set; }

    public Node[,] Nodes { get; set; }
    public List<Node> Path { get; set; }

    public World(int width, int height)
    {
        Width = width;
        Height = height;
        Nodes = new Node[Width, Height];

        Build();
    }

    private void Build()
    {
        for (int y = 0; y < Height; y++)
        {
            for (int x = 0; x < Width; x++)
            {
                Nodes[x, y] = new Node(x, y);
            }
        }
    }

    public void Find()
    {
        Node Start = GetStartNode(Nodes);
        Node Destination = GetDestinationNode(Nodes);

        var openSet = new List<Node>();
        var closedSet = new List<Node>();
        openSet.Add(Start);

        while (openSet.Any())
        {
            Node n = GetLowestFCostNode(openSet);
            
            if (n.NodeState == NodeState.Destination)
            {
                /* Trace Back Path */
                Path = TracebackPath(n, Start);
                break;
            }

            closedSet.Add(n);
            openSet.Remove(n);

            foreach (var node in GetAdjacentNodes(n, Nodes))
            {
                if (closedSet.Contains(node) || node.NodeState == NodeState.Obstruction)
                    continue;

                int currentGCost = node.GCost + NodeDistance(n, node);

                bool recalculate;
                if (!openSet.Contains(node))
                {
                    openSet.Add(node);
                    recalculate = true;
                }
                else if (currentGCost < node.GCost)
                {
                    recalculate = true;
                }
                else
                {
                    recalculate = false;
                }

                if (recalculate)
                {
                    node.Parent = n;
                    node.GCost = currentGCost;
                    node.HCost = HueristicsCost(node, Destination);
                    node.CalculateFCost();
                }
            }
        }
    }

    private int HueristicsCost(Node node, Node destination)
    {
        int dx = Math.Abs(node.X - destination.X);
        int dy = Math.Abs(node.Y - destination.Y);
        return 10 * (dx + dy);
    }

    private int NodeDistance(Node a, Node b)
    {
        if (Math.Abs(a.X - b.X) == 1 && Math.Abs(a.Y - b.Y) == 1)
            return 14;
        return 10;
    }

    private List<Node> GetAdjacentNodes(Node candidate, Node[,] fields)
    {
        var fieldList = new List<Node>();
        var width = fields.GetLength(0);
        var height = fields.GetLength(1);

        /* Check Lateral Neighbors */
        for (var x = candidate.X - 1; x <= candidate.X + 1; x++)
        {
            /* Check Vertical Neighbors */
            for (var y = candidate.Y - 1; y <= candidate.Y + 1; y++)
            {
                /* Bounds Check */
                if (x >= 0 && x < width && y >= 0 && y < height && (x != candidate.X || y != candidate.Y))
                {
                    fieldList.Add(fields[x, y]);
                }
            }
        }

        return fieldList;
    }


    private Node GetLowestFCostNode(List<Node> openSet)
    {
        Node lowestFCostNode = null;
        int lowestFCost = int.MaxValue;

        foreach (Node node in openSet)
        {
            if (node.FCost < lowestFCost || (node.FCost == lowestFCost && node.HCost < lowestFCostNode.HCost))
            {
                lowestFCost = node.FCost;
                lowestFCostNode = node;
            }
        }

        return lowestFCostNode;
    }

    private List<Node> TracebackPath(Node node, Node start)
    {
        List<Node> list = new List<Node>();
        while (node != start)
        {
            list.Add(node);
            node.Tile.Fill = Brushes.Cyan;
            node = node.Parent;
        }

        list.Add(start);

        return list;
    }

    private Node GetDestinationNode(Node[,] nodes)
    {
        foreach (var node in nodes)
        {
            if (node.NodeState == NodeState.Destination)
                return node;
        }

        throw new Exception("No Destination Field.");
    }

    private Node GetStartNode(Node[,] nodes)
    {
        foreach (var node in nodes)
        {
            if (node.NodeState == NodeState.Start)
                return node;
        }

        throw new Exception("Could not find a starting node.");
    }
}

Node.cs

public class Node
{
    public int X { get; }
    public int Y { get; }
    public Rectangle Tile { get; set; }

    /* Estimated Distance from CurrentNode to the StartNode */
    public int GCost { get; set; }

    /* Estimated Distance From CurrentNode To DestinationNode */
    public int HCost { get; set; }

    /* G + HCost Combined */
    public int FCost { get; set; }
    public Node Parent { get; set; }

    private NodeState _nodeState;

    public NodeState NodeState
    {
        get { return _nodeState; }
        set
        {
            InvokeNodeState(value);
            _nodeState = value;
        }
    }

    public Node(int x, int y)
    {
        X = x;
        Y = y;

        CreateTile();
    }

    private void CreateTile()
    {
        Tile = new Rectangle()
        {
            Width = 25,
            Height = 25,
            Fill = Brushes.ForestGreen,
            Stroke = Brushes.Black,
            StrokeThickness = 2
        };

        Tile.MouseDown += (sender, args) =>
        {
            switch (NodeState)
            {
                case NodeState.None:
                    NodeState = NodeState.Obstruction;
                    break;
                case NodeState.Obstruction:
                    NodeState = NodeState.Start;
                    break;
                case NodeState.Start:
                    NodeState = NodeState.Destination;
                    break;
                case NodeState.Destination:
                    NodeState = NodeState.None;
                    break;
                default:
                    throw new ArgumentOutOfRangeException();
            }
        };

        Canvas.SetLeft(Tile, X * 25);
        Canvas.SetTop(Tile, Y * 25);
    }

    private void InvokeNodeState(NodeState value)
    {
        switch (value)
        {
            case NodeState.None:
                Tile.Fill = Brushes.ForestGreen;
                break;
            case NodeState.Obstruction:
                Tile.Fill = Brushes.SaddleBrown;
                break;
            case NodeState.Start:
                Tile.Fill = Brushes.Yellow;
                break;
            case NodeState.Destination:
                Tile.Fill = Brushes.Red;
                break;
            default:
                throw new ArgumentOutOfRangeException(nameof(value), value, null);
        }
    }

    public void CalculateFCost()
    {
        FCost = GCost + HCost;
        Tile.Fill = Brushes.DarkGreen;
        Tile.ToolTip = $"FCost: {FCost} - GCost: {GCost} - HCost: {HCost}";
    }
}

public enum NodeState
{
    None,
    Obstruction,
    Start,
    Destination
}

Answer 1

用于估计剩余距离的启发式绝不能高估剩余距离。你的启发是：

int dx = Math.Abs(node.X - destination.X);
int dy = Math.Abs(node.Y - destination.Y);
return 10 * (dx + dy);

而你的距离计算是

if (Math.Abs(a.X - b.X) == 1 && Math.Abs(a.Y - b.Y) == 1)
    return 14;
return 10;

因此，考虑节点 (0, 0) 和 (1,1)，估计距离为 20，而实际距离为 14。这使得启发式不可接受。最简单的解决方法是更改(dx + dy)​​为Math.Max(dx, dy).

调试 A* 时，将启发式设置为 0 可能会很有用，这应该将算法变成 Djikstra。如果效果更好，您就知道您的问题与启发式有关。

关于数据结构的一些注意事项，如果您想提高算法的性能，您可能应该使用除 List 之外的其他内容作为开/闭集。对于闭集，一些常见的选择是 HashSet 或 2D 数组。对于开放集，典型的数据结构是 MinHeap，因为它具有快速插入和删除的功能。