A* 认识到不可能达到目标

Question

我在 wiki article 中对 8 拼图问题几乎逐字逐句地实现了 A*，但即使我有 closed 我仍然在应该失败的板上无限运行.

似乎打开新节点的速度大于关闭它们的速度，因为每个节点大约有 1-4 个新节点添加到 open 但只有一个节点从 open 到 closed。

那么，如何识别给定的起始板没有永远等待的目标路径？

这是代码：

public List<KeyValuePair<GameBoard, GameBoard.MoveDirection>> Search(GameBoard startBoard, GameBoard goal)
{
    InitSearch(startBoard, goal);
    while (_open.Count > 0)
    {
        GameBoard current = LowestFScoreInOpen();
        if (current.Equals(_goal))
        {
            return ReconstructPath(current);
        }

        _open.Remove(current);
        _closed.Add(current);

        foreach (GameBoard.MoveDirection direction in Enum.GetValues(typeof(GameBoard.MoveDirection)))
        {
            GameBoard neighbor = current.MoveAndCopy(direction);
            if(neighbor == null) continue;  // invalid direction 
            if(_closed.Contains(neighbor)) continue;

            int tentativeScore = _gScore[current] + 1;
            if (!_open.Contains(neighbor))
            {
                _open.Add(neighbor);
            }
            else if (tentativeScore >= _gScore[neighbor])
            {
                continue; // already in _open and this is not a better path 
            }

            // best path so far
            _cameFrom[neighbor] = new KeyValuePair<GameBoard, GameBoard.MoveDirection>(current, direction);
            _gScore[neighbor] = tentativeScore;
            int fscore = tentativeScore + Heuristic(neighbor);
            _fScore[neighbor] = fscore;
            _sortedFScore.Enqueue(new PriorityQueueItem<GameBoard, int>(neighbor, fscore));
        }
    }

    return null; // no path found
}

开始和目标板之间没有路径的示例：

开始：目标：

完整代码：https://pastebin.com/v10U2J2Z

Answer 1

这里的问题不在算法实现中（它也可能有问题 - 没有检查），但在 GameBoard class 的 GetHashCode() 的错误实现中：

public int[,] Board { get; }
public override int GetHashCode()
{
    return Board.GetHashCode();
}

Board 是数组，数组是 class（不是结构）所以它是默认的 GetHashCode() 实现只是 returns 一些保证相同的值仅限此实例。这意味着：

var a = new int[] {1,2,3};
var b = new int[] {1,2,3};
Debug.Assert(a.GetHashCode() == b.GetHashCode());

失败，因为即使数组内容相同 - 那些是不同的实例并且 GetHashCode returns 完全不同的值。

错误的 GetHashCode 实现用于算法的关键位置，最重要的是（对于这个具体问题）在封闭集中，即：

HashSet<GameBoard> _closed = new HashSet<GameBoard>();

当你这样做时

if (_closed.Contains(neighbor)) continue;

它无法检测到闭集包含给定的棋盘，即使它确实存在，因为违反了哈希函数的唯一要求（相等的对象应该 return 相等的哈希码）。所以你的闭集增长没有限制，因为你一次又一次地在那里添加相同的板。

使用此代码很容易检查：

var set = new HashSet<GameBoard>();
set.Add(new GameBoard(new int[,]
{
    {1, 2, 3},
    {8, 0, 4},
    {7, 6, 5},
}));
bool contains = set.Contains(new GameBoard(new int[,]
{
    {1, 2, 3},
    {8, 0, 4},
    {7, 6, 5},
})); // false

要修复，请执行以下操作：

public override int GetHashCode()
{                          
     // make _flatten readonly by the way, now it's not
     return _flatten.GetHashCode();
}

并且你的程序将终止（将抛出空引用异常，因为如果没有解决方案你 return null 但是打印解决方案时不检查它）。

A* 认识到不可能达到目标

A* to recognize it's impossible to get to the goal

c#

algorithm

search

artificial-intelligence

a-star