如何让A*算法给出最短路径？（见附图）

Question

如何让A*算法给出最短路径？（见附图）

4

我使用Justin Heyes-Jones实现的astar算法。我的启发式函数只是欧几里得距离。在附加的图中（抱歉质量不佳），描述了一种特定的情况：假设我们从节点1到节点2。最短路径将通过节点a - b - c - d - e。但是，使用欧几里得启发式的逐步Astar将为我们提供通过以下节点的路径：a - b' - c' - d' - e，我了解为什么会出现这种情况。但是我该怎么做才能使其返回最短路径？！

真实道路地图导入的代码：

#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 );
}

我知道这不是精确的距离（这里没有进行平方根运算）- 这样做是为了在评估时节省一些机器资源。

- Starter

我们能看到你的代码吗？这样我们就可以找出哪里出了问题。 - Elliot Bonneville

弧长是否也是平方距离？ - Laky

是的，但我并不真正使用它。我所拥有的输入只是一系列弧。这就是我从中获取有关节点及其邻居信息的地方。没有必要评估弧长，因为我对每个经过的节点都有一个g(x)函数。如果我错了，请纠正我。 - Starter

这样你就可以进行最佳优先搜索而不是A算法。A算法的重点在于将值设为distanceSoFar + heurisitc。openSet按照这个值进行排序。如果你不计算从初始状态到当前节点所需的成本，可能会得到不理想的结果。 - Laky

1

这真的很奇怪。是的，那行代码可以实现你想要的功能，但你是否传递了正确的成本，即实际距离的平方？而且你总是生成所有的邻居吗？你应该进行一些调试并尝试定位问题，因为它似乎会是你代码中的某个错误。节点之间的弧长是否始终大于它们的欧几里得距离？我可以想象，如果你从真实地图中获取数据，可能会存在一些不精确性。 - Laky

显示剩余2条评论

2个回答

0

看起来在 get_h 方法中进行平方根运算已经解决了问题。结果发现我的启发式函数不是可接受的（至少我认为这可以解释）。特别感谢 Laky 和 justinhj 的帮助！！！

- Starter

如果你想感谢我，你可以在我的答案旁边打上一个勾；）我会稍微编辑一下以反映最终发生的事情。 - Laky

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Laky · Accepted Answer

当您使用A*图搜索时，即只考虑对节点的第一次访问并忽略后续访问时，这实际上可能发生在您的启发式不一致时。如果启发式不一致且使用图搜索（保留已访问状态列表，如果已经遇到了一个状态，则不再扩展它），则您的搜索将无法给出正确答案。

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

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

关于一致性的定义，请参见：Wikipedia: A* Search Algorithm 编辑：虽然上述仍然正确，但此启发式确实是一致的，我为造成的混淆道歉。

EDIT2: 尽管这种启发式本身是可接受且一致的，但其实现并非如此。出于性能考虑，您决定不进行平方根运算，这使得您的启发式不可接受，并且这就是您得到错误结果的原因。

对于未来，最好总是尽可能地先将算法实现为简单朴素的形式。这通常有助于保持可读性，并且它们更不容易出现错误。如果存在缺陷，则更容易发现。因此，我的最终建议是除非需要，否则不要优化，或者除非其他所有事情都顺利。否则，您可能会遇到麻烦。