4

私はastarアルゴリズムのJustinHeyes-Jones実装を使用しています。私のヒューリスティック関数は、ユークリッド距離です。添付の図面（品質が悪いため申し訳ありません）には、特定の状況が示されています。ノード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*検索アルゴリズム

編集：上記はまだ真実ですが、このヒューリスティックは確かに一貫しています、混乱をお詫び申し上げます。

EDIT2：ヒューリスティック自体は許容され、一貫性がありますが、実装はそうではありませんでした。パフォーマンスのために、平方根を使用しないことにしました。これにより、ヒューリスティックが許容されなくなり、間違った結果が得られたのはそのためです。

将来的には、最初にアルゴリズムをできるだけ素朴に実装することをお勧めします。通常、読みやすくするのに役立ち、バグが発生しにくくなります。バグがある場合は、簡単に見つけることができます。したがって、私の最後のアドバイスは、必要でない限り、または他のすべてがうまく機能していない限り、最適化しないことです。そうしないと、トラブルに巻き込まれる可能性があります。

于 2012-04-06T16:35:56.517 に答える
0

get_hメソッドで平方根を取ることで解決したようです。私のヒューリスティックは許容できなかったことがわかりました（少なくともこれがそれを説明していると思います）。これを手伝ってくれたLakyとjustinhjに特に感謝します!!!

于 2012-04-14T09:32:18.967 に答える