어떻게 A * 알고리즘을 최단 경로로 만들 수 있습니까? (그림을 동봉하십시오)

Question

저는 Astar 알고리즘의 Justin Heyes-Jones 구현을 사용합니다. 내 휴리스틱 함수는 유클리드 거리입니다. 첨부 된 도면 (품질이 좋지 않다면)에서 특정 상황을 설명합니다. 즉, 노드 1에서 노드 2로 이동한다고 가정합니다. 최단 경로는 노드 a-b-c-d-e를 통과합니다. 그러나 유클리드 발견 적 방법을 사용한 단계별 Astar는 다음과 같은 노드를 통해 우리에게 방법을 제공 할 것입니다 : a - b '- c'- d '- e 그리고 나는 이것이 일어나는 이유를 이해합니다. 하지만 최단 경로를 돌려 주려면 어떻게해야합니까?!

false shortest path finding by the 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 나에게 결과 노드의 벡터를 제공합니다.

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

여기

는 addNeighbours 방법입니다 평가할 때 자원.

Answer 1

A * 그래프 검색을 사용할 때, 즉 노드를 처음 방문한 것으로 간주하고 향후 방문을 무시할 때 경험적으로 일관성이없는 경우가 발생할 수 있습니다. 경험적 방법이 일관성이없고 그래프 검색을 사용하면 (방문한 상태의 목록을 유지하고 이미 상태가 발생한 경우 다시 확장하지 않음) 검색에서 올바른 답을 제공하지 않습니다.

그러나 허용 가능한 휴리스틱과 함께 A * 트리 검색을 사용하는 경우 정답을 얻어야합니다. 트리 및 그래프 검색의 차이점은 트리 검색에서 사용자가 만날 때마다 상태를 확장한다는 것입니다. 따라서 처음에 알고리즘이 더 긴 b ', c', d '경로를 취하기로 결정하더라도 나중에 a로 돌아가서 다시 확장하고 b, c, d 경로가 실제로 더 짧음을 알 수 있습니다.

내 조언은 그래프 검색 대신 트리 검색을 사용하거나 일관된 휴리스틱을 선택하는 것입니다.

일관성의 정의는, 예를 들어, 참조 : Wikipedia: A* Search Algorithm

편집 : 위에서 여전히 사실이지만,이 추론은 내가 혼란을 드려 죄송합니다, 참으로 일치한다.

EDIT2 : 경험적 방법 자체가 허용 가능하고 일관성이 있지만 구현은 그렇지 않습니다. 성능 향상을 위해 제곱근을 사용하지 않기로 결정 했으므로 결과적으로 잘못된 결과를 얻었습니다.

앞으로는 알고리즘을 가능한 한 순진하게 구현하는 것이 좋습니다. 일반적으로 이들을 더 읽기 쉽도록 유지하고 버그가 적습니다. 버그가 있으면 더 쉽게 발견 할 수 있습니다. 따라서 필자가 필요로하지 않는 한 또는 다른 모든 것이 잘 작동하지 않는 한 내 최종 조언은 최적화되지 않을 것입니다. 그렇지 않으면 문제가 생길 수 있습니다.

Answer 2

get_h 메서드에서 제곱근을 사용하면 해결 된 것 같습니다. 내 경험에 의하면 (적어도 나는 이것을 설명한다고 생각한다) 인정받지 못했다. 이걸 도와 준 Laky와 justinhj에게 특별한 감사 !!!