4

我使用 Justin Heyes-Jones 实现 astar 算法。我的启发式函数只是欧几里得距离。在附图中(抱歉质量不好)描述了一个特定的情况:假设我们从节点 1 到节点 2。最短的方法是通过节点 a - b - c - d - e。但是带有欧几里得启发式的逐步 Astar 将为我们提供通过以下节点的方法:a - b' - c' - d' - e 我理解为什么会发生这种情况。但是我该怎么做才能让它返回最短路径?!

astar错误的最短路径查找

真正的路线图导入代码:

#include "search.h"

class ArcList;

class MapNode
{
public:

    int x, y;       // ���������� ����
    MapNode();
    MapNode(int X, int Y);
    float Get_h( const MapNode & Goal_node );
    bool GetNeighbours( AStarSearch<MapNode> *astarsearch, MapNode *parent_node );
    bool IsSamePosition( const MapNode &rhs );
    void PrintNodeInfo() const;

    bool operator == (const MapNode & other) const;

    void setArcList( ArcList * list );

private:
    ArcList * list;
};

class Arc
{
public:
    MapNode A1;
    MapNode B1;
    Arc(const MapNode & a, const MapNode & b);
};

class ArcList
{
public:

    void setArcs( const std::vector<Arc> & arcs );
    void addArc( const Arc & arc );

    size_t size() const;

    bool addNeighbours( AStarSearch<MapNode> * astarsearch, const MapNode & neighbour );

private :
    std::vector<Arc> arcs;
};

std::vector <MapNode> FindPath(const MapNode & StartNode, const MapNode & GoalNode)
{
    AStarSearch<MapNode> astarsearch;
    astarsearch.SetStartAndGoalStates( StartNode, GoalNode );

    unsigned int SearchState;
    unsigned int SearchSteps = 0;

    do
    {
        if ( SearchSteps % 100 == 0)
            std::cout << "making step " << SearchSteps << endl;

        SearchState = astarsearch.SearchStep();

        SearchSteps++;
    }
    while ( SearchState == AStarSearch<MapNode>::SEARCH_STATE_SEARCHING );

    std::vector<MapNode> S;
    if ( SearchState == AStarSearch<MapNode>::SEARCH_STATE_SUCCEEDED )
    {
        int steps = 0;

        for ( MapNode * node = astarsearch.GetSolutionStart(); node != 0; node = astarsearch.GetSolutionNext() )
        {
            S.push_back(*node);
//            node->PrintNodeInfo();
        }

        astarsearch.FreeSolutionNodes();
    }
    else if ( SearchState == AStarSearch<MapNode>::SEARCH_STATE_FAILED )
    {
        throw " SEARCH_FAILED ";
    }
    return S;
}

函数 FindPath 给了我结果节点的向量。

这是 addNeighbours 方法:

bool ArcList::addNeighbours( AStarSearch<MapNode> * astarsearch, const MapNode & target )
{
    assert(astarsearch != 0);
    bool found = false;
    for (size_t i = 0; i < arcs.size(); i++ )
    {
        Arc arc = arcs.at(i);

        if (arc.A1 == target)
        {
            found = true;
            astarsearch->AddSuccessor( arc.B1 );
        }
        else if (arc.B1 == target )
        {
            found = true;
            astarsearch->AddSuccessor( arc.A1 );
        }
    }

    return found;
}

和 get_h 方法:

float MapNode::Get_h( const MapNode & Goal_node )
{
    float dx = x - Goal_node.x;
    float dy = y - Goal_node.y;
    return ( dx * dx  + dy * dy );
}

我知道它不是精确的距离(这里不取平方根) - 这样做是为了在评估时节省一些机器资源。

4

2 回答 2

4

当您使用 A* 图搜索时,即您只考虑对节点的第一次访问而忽略未来的访问,这实际上可能在您的启发式不一致时发生。如果启发式不一致并且您使用图形搜索(您保留已访问状态的列表,并且如果您已经遇到过状态,则不要再次扩展它),您的搜索不会给出正确的答案。

但是,当您使用具有可接受启发式的 A* 树搜索时,您应该得到正确的答案。树搜索和图搜索的区别在于,在树搜索中,每次遇到它时都会扩展状态。因此,即使一开始您的算法决定采用较长的 b', c', d' 路径,稍后它会返回到 a,再次扩展它并发现 b, c', d 路径实际上更短。

因此我的建议是,要么使用树搜索而不是图搜索,要么选择一致的启发式。

有关一致的定义,请参见例如:Wikipedia: A* Search Algorithm

编辑:虽然上述情况仍然正确,但这种启发式确实是一致的,我为造成的混乱道歉。

EDIT2:虽然启发式本身是可接受且一致的,但实施不是。为了性能,你决定不做平方根,这使得你的启发式算法不可接受,这就是你得到错误结果的原因。

对于未来,最好尽可能天真地首先实现您的算法。它通常有助于使它们更具可读性,并且它们不太容易出现错误。如果有错误,则更容易发现。因此,我的最终建议是不要优化,除非你需要它,或者除非其他一切运行良好。否则你可能会遇到麻烦。

于 2012-04-06T16:35:56.517 回答
0

似乎在 get_h 方法中取平方根已经解决了它。事实证明我的启发式是不可接受的(至少我认为这可以解释)。特别感谢 Laky 和 ​​justinhj 的帮助!!!

于 2012-04-14T09:32:18.967 回答