A *认识到不可能达到目标 [英] A* to recognize it's impossible to get to the goal
问题描述
我为8个难题的问题实现了A *，几乎与
目标：
完整代码： https://pastebin.com/v10U2J2Z
这里的问题不在算法实现中（当然，它也可能有问题-未检查），但是 GameBoard 类的 GetHashCode（）的错误实现：
public int [，]董事会{get; }
公共重写int GetHashCode（）
{
return Board.GetHashCode（）;
}
木板是数组并且array是一个类（不是结构），因此它的默认 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>（）;
这样做的时候
如果（_closed.Contains（neighbor））继续;
由于唯一的条件对于哈希函数（相等的对象应返回相等的哈希码）被违反。因此，封闭集的增长不受限制，因为您一次又一次地添加了相同的板。
易于检查以下代码：
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}，
}））； //错误
要解决此问题，请执行以下操作：
公共重写int GetHashCode（）
{
//顺便说一句_flatten为只读，现在它不是
return _flatten.GetHashCode（） ;
}
程序将终止（将引发空引用异常，因为您返回null如果没有解决方案，但在打印解决方案时不检查此问题。
I implemented A* for the 8 puzzle problem pretty much word for word to the pseudo code in the wiki article but even though I have closed I still get infinite runtime on boards that should fail.
It seems that the rate of opening new nodes is larger than closing them, since for each node about 1-4 new nodes are added to the open but only one node is moved from open to closed.
So what can be done to recognize that a given starting board has no path to the goal without waiting forever?
This is the code:
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
}
Example for start and goal board with no path between them:
Start: Goal:
Full code: https://pastebin.com/v10U2J2Z
The problem here is not in algorithm implementation (well there might be problems with it too - did not check), but in wrong implementation of GetHashCode() for GameBoard class:
public int[,] Board { get; }
public override int GetHashCode()
{
return Board.GetHashCode();
}
Board is array and array is a class (not struct) so it's default GetHashCode() implementation just returns some value which is guaranteed to be the same for this instance only. That means that:
var a = new int[] {1,2,3};
var b = new int[] {1,2,3};
Debug.Assert(a.GetHashCode() == b.GetHashCode());
Fails, because even though array contents are the same - those are different instances and GetHashCode returns completely different values.
That wrong GetHashCode implementation is used in critical places in your algorithm, most importantly (for this concrete problem) in closed set, which is:
HashSet<GameBoard> _closed = new HashSet<GameBoard>();
When you do
if (_closed.Contains(neighbor)) continue;
It fails to detect that closed set contains given board, even if it really does, because the only requiremet for a hash function (objects that are equal should return hash codes that are equal) is violated. So your closed set growth without bound because you add the same boards there again and again.
Easy to check with this code:
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
To fix, do something like:
public override int GetHashCode()
{
// make _flatten readonly by the way, now it's not
return _flatten.GetHashCode();
}
And your program will terminate (will throw null reference exception, because you return null if there is no solution but don't check for this when printing solution).
这篇关于A *认识到不可能达到目标的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
