我在实现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; // 无效方向 if(_closed.Contains(neighbor)) continue; int tentativeScore = _gScore[current] + 1; if (!_open.Contains(neighbor)) { _open.Add(neighbor); } else if (tentativeScore >= _gScore[neighbor]) { continue; // 已经在_open中且这不是更好的路径 } // 到目前为止的最佳路径 _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; // 未找到路径}起始和目标棋盘之间没有路径的示例：
起始:
目标:
完整代码：https://pastebin.com/v10U2J2Z
回答：
这里的问题不在于算法实现（当然，算法实现也可能有问题——我没有检查），而在于GameBoard类的GetHashCode()方法实现错误：
public int[,] Board { get; }public override int GetHashCode(){ return Board.GetHashCode();}Board是一个数组，而数组是一个类（不是结构体），所以它的默认GetHashCode()实现只是返回某个值，这个值只保证对于这个实例是相同的。这意味着：
var a = new int[] {1,2,3};var b = new int[] {1,2,3};Debug.Assert(a.GetHashCode() == b.GetHashCode());会失败，因为即使数组内容相同——它们是不同的实例，GetHashCode返回完全不同的值。
这个错误的GetHashCode实现被用在算法的关键地方，最重要的是（对于这个问题）在关闭集合中，它是：
HashSet<GameBoard> _closed = new HashSet<GameBoard>();当你执行
if (_closed.Contains(neighbor)) continue;它无法检测到关闭集合中包含给定的棋盘，即使它确实包含，因为哈希函数的唯一要求（相等的对象应该返回相等的哈希码）被违反了。所以你的关闭集合会无限制地增长，因为你一次又一次地添加相同的棋盘到其中。
可以用以下代码轻松检查：
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(){ // 顺便说一下，让_flatten成为只读的，现在它不是 return _flatten.GetHashCode();}这样你的程序就会终止（会抛出空引用异常，因为如果你没有找到解决方案时返回null，但在打印解决方案时没有检查这一点）。
