A* 认识到实现目标是不可能的 [英] A* to recognize it's impossible to get to the goal

查看:20
本文介绍了A* 认识到实现目标是不可能的的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我在 目标:

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

解决方案

这里的问题不在于算法实现(好吧也可能有问题 - 没有检查),而在于 GetHashCode() 用于 GameBoard 类:

public int[,] Board { get;}公共覆盖 int GetHashCode(){返回 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_closed = new HashSet();

当你这样做

if (_closed.Contains(neighbor)) continue;

它无法检测到封闭集包含给定的棋盘,即使它确实存在,因为违反了散列函数的唯一要求(相等的对象应返回相等的散列代码).所以你的封闭集增长没有限制,因为你一次又一次地在那里添加相同的板.

使用此代码易于检查:

var set = new HashSet();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},}));//错误的

要修复,请执行以下操作:

public override int GetHashCode(){//顺便把 _flatten 设为只读,现在不是返回_flatten.GetHashCode();}

并且你的程序将终止(将抛出空引用异常,因为如果没有解决方案你会返回空值,但在打印解决方案时不检查这个).

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屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆