최단 경로를 찾을 수있는 길 찾기?

Question

A * 경로 찾기 알고리즘은 최단 경로 100 % 또는 시간 (올바르게 구현 된 경우)을 찾도록 보장됩니까?

int Graph::FindPath(Node *start, Node *finish, list<vec2f> &path) 
{ 
    list<NodeRecord*> open; 
    list<NodeRecord*> closed; 
    list<NodeRecord*>::iterator openIt; 
    list<NodeRecord*>::iterator closedIt; 

    // add the starting node to the open list 
    open.push_back(new NodeRecord(start, NULL, 0.0f, 0.0f + start->pos.DistanceSq(finish->pos))); 
    // NodeRecord(Node *node, Node *from, float cost, float totalCost) 

    while(!open.empty()) 
    { 
     // find the node record with the lowest cost 
     NodeRecord *currentRecord = open.front(); 
     openIt = ++open.begin(); 

     while(openIt != open.end()) 
     { 
      if((*openIt)->total < currentRecord->total) 
       currentRecord = (*openIt); 

      openIt++; 
     } 

     // get a pointer to the current node 
     Node *currentNode = currentRecord->node; 

     // if the current node is the finish point 
     if(currentNode == finish) 
     { 
      // add the finish node 
      path.push_front(currentNode->pos); 

      // add all the from nodes 
      Node *from = currentRecord->from; 

      while(!closed.empty()) 
      { 
       // if this node record is where the path came from, 
       if(closed.back()->node == from) //&& closed.back()->from != NULL 
       { 
        // add it to the path 
        path.push_front(from->pos); 

        // get the next 'from' node 
        from = closed.back()->from; 
       } 

       // delete the node record 
       delete closed.back(); 
       closed.pop_back(); 
      } 

      while(! open.empty()) 
      { 
       delete open.back(); 
       open.pop_back(); 
      } 

      // a path was found 
      return 0; 
     } 

     // cycle through all neighbours of the current node 

     bool isClosed, isOpen; 

     for(int i = 0; i < (int)currentNode->neighbours.size(); i++) 
     { 
      // check if neigbour is on the closed list 
      isClosed = false; 
      closedIt = closed.begin(); 
      while(closedIt != closed.end()) 
      { 
       if(currentNode->neighbours[i] == (*closedIt)->node) 
       { 
        isClosed = true; 
        break; 
       } 

       closedIt++; 
      } 

      // skip if already on the closed list 
      if(isClosed == true) 
       continue; 

      float cost = currentRecord->cost + currentNode->distance[i]; 
      float totalCost = cost + currentNode->neighbours[i]->pos.DistanceSq(finish->pos); 

      // check if this neighbour is already on the open list 
      isOpen = false; 
      openIt = open.begin(); 
      while(openIt != open.end()) 
      { 
       if(currentNode->neighbours[i] == (*openIt)->node) 
       { 
        // node was found on the open list 
        if(totalCost < (*openIt)->total) 
        { 
         // node on open list was updated 
         (*openIt)->cost = cost; 
         (*openIt)->total = totalCost; 
         (*openIt)->from = currentNode; 
        } 

        isOpen = true; 
        break; 
       } 

       openIt++; 

      } 

      // skip if already on the open list 
      if(isOpen == true) 
       continue; 

      // add to the open list 
      open.push_back(new NodeRecord(currentNode->neighbours[i], currentNode, cost, totalCost)); 
     } 

     // move the current node to the closed list after it has been evaluated 
     closed.push_back(currentRecord); 
     open.remove(currentRecord); 
    } 

    // free any nodes left on the closed list 
    while(! closed.empty()) 
    { 
     delete closed.back(); 
     closed.pop_back(); 
    } 

    // no path was found 
    return -1; 
} 

Answer 1

Yes (하지만 구현에 깊이 관여하지 않았습니다.)

대부분의 사람들이 놓친 것은 휴리스틱 알고리즘이 최종 솔루션에 대한 순회 비용을 과소 평가해야한다는 것입니다 (이를 "admissible"라고 함). 그것은 당신의 코드에서 내 눈에,

---

어쨌든 (이것은 "consistent"라고합니다) 또한 발견 단조 솔루션에 접근하기에 좋은 (그러나 절대적으로 필요하지 않음), 당신은 아마 당신의 폐쇄에 대한 std::set를 사용해야합니다 목록과 std::deque을 열어 두 검색어에 대한 검색 및 삽입이 O (n)가 아닌지 확인하십시오. 또한 new NodeRecords을 만들면 안되며, 간접적으로 우회적으로 작용하므로 예외가 발생하면 알고리즘에 메모리가 누출됩니다.

Answer 2

Wikipedia에 따르면 A *는 최단 경로를 더 빨리 찾는 데 휴리스틱을 사용하지만 실제는 Dijkstra의 최단 경로 알고리즘을 수정 한 것으로, 경험칙이 충분하지 않으면 A *가 Dijkstra와 거의 동일합니다.

그래서 예, A *가 최단 경로를 찾는다는 보장이 있습니다.

Answer 3

흥미롭게도 허용 가능한 휴리스틱 스는 최적의 솔루션을 100 % 제공하지만 특정 상황에서는 느려질 수 있습니다. 대략적으로 동일한 총 거리가 여러 경로 인 경우 허용되지 않는 발견 적 방법은 상대적으로 동등한 경로 사이에서 더 빠른 "의사 결정"을 제공합니다. 이 작업을 수행하려면 닫힌 목록을 사용해야합니다.

실제로 "Heuristics"라는 책에서 발견 한 사실적 방법이 소량으로 과대 평가되는 경우 제공되는 솔루션이 같은 양 (최대)으로 최적보다 길다는 것을 증명합니다.

특정 빠른/실시간 응용 프로그램의 경우 솔루션 품질에 대한 작은 비용으로 속도를 높이는 진정한 도움이 될 수 있습니다.