* 길 찾기 - 거대한 열린지도가 느리다

Question

나는 작은 격자에 완벽하게 작동하는 A * 길 찾기를 구현했습니다. 그러나지도가 커지고 아래에 묘사 된지도와 같이 더 이상 미로 구조가되지 않으면 알고리즘이 점점 느려집니다. A *의 정의에 따라

, 나는 열린 목록과 폐쇄 된 목록을 사용하고 있습니다. 공개 목록은 std::set을 사용하여 구현됩니다. 닫힌 목록은 Qt의 QSet을 사용하여 구현됩니다. QSet은 std::unordered_list의 Qt 구현입니다.

내 응용 프로그램을 프로파일 링 한 후 std::set의 트리를 다시 조정하는 것이 가장 비용이 많이 드는 작업임을 알아 차렸습니다. 두 개의 서로 다른 맵에서 알고리즘을 실행할 때 눈에 띄게 나타납니다. 아래에는 큰 오픈리스트 크기가 있고 다른 미로와 같은 맵은 훨씬 낮은 오픈리스트 크기입니다.

미로와 같은 맵에서 공개 목록의 크기는 20 ~ 120 개의 노드 사이에서 변동합니다. 오픈 맵은 서서히 2000 개 이상의 노드까지 성장했습니다.

오픈리스트의 크기를 줄일 수있는 방법이 있다면 제 질문은 무엇입니까?

나는 다음과 같은 방법을 시도 :

• 변경 열린 목록을 std::priority_queue에 : 나는 그것을 이미 요소가있는 경우에 볼 수있는 공개 목록을 확인해야하기 때문에이를 구현 할 수 없습니다. 그리고 내가 틀렸다면 나에게 올바른 것이지만, priority_queue가 같은 균형 조정 문제에 부딪치지 않을까?

• 더 높은 추론 가중치를 사용하십시오. 문제를 해결하지 못했지만 열린 목록의 노드 크기 순서는 여전히 동일합니다.

• 열려있는 목록에서 노드 잘라 내기 : 결과가 더 빨리 통과하지만 경로를 찾을 수없는 경우가 많습니다. 처음에는 관련성이 없어지는 높은 F (경험적 + 움직임) 비용으로 값을 다듬기 만하면 이것이 효과가 있다고 생각했습니다. 이 가정은 틀린 것으로 판명되었습니다.

미리 감사드립니다.

EDIT1 : 설명을위한 몇 가지 코드가 추가되었습니다.

std::shared_ptr<Node> Pathfinding::findPath(float heuristicWeight) { 
    int i = 0; 
    while (!m_sOpen.empty()) { 
     ++i; 
     std::shared_ptr<Node> current = *m_sOpen.begin(); 
     m_sOpen.erase(current); 
     m_sClosed.insert(*current); 
     if (updateNeighbours(current, heuristicWeight)) { 
      return std::make_shared<Node>(*m_sClosed.find(*m_nEnd)); 
     } 
     if (i % 100 == 0) { 
      qInfo() << "Sizes: " << i << " open_size= " << m_sOpen.size() << " & closed_size= " << m_sClosed.size(); 
     } 
    } 
    return NULL; 
} 

bool Pathfinding::updateNeighbours(std::shared_ptr<Node> current, float heuristicWeight) { 
    int maxRows = wm.getRows(); // Rows in map 
    int maxCols = wm.getCols(); // Cols in map 
    for (int x = clamp((current->getX()-1),0,maxCols-1); x <= clamp((current->getX()+1),0,maxCols-1); ++x) { 
     for (int y = clamp((current->getY()-1),0,maxRows-1); y <= clamp((current->getY()+1),0,maxRows-1); ++y) { 
      bool exists = false; 
      Node n = Node(x,y); // Node to compare against and insert if nessecary. 
      // Tile contains information about the location in the grid. 
      Tile * t = wm.m_tTiles[(x)+(maxCols * y)].get(); 
      if (t->getValue() != INFINITY) { // Tile is not a wall. 
       for (std::set<std::shared_ptr<Node>>::iterator it = m_sOpen.begin(); it != m_sOpen.end(); ++it) { 
        if (**it == n) { 
         exists = true; 
         if ((*it)->getF() > (current->getG() + moveCost(*it,current)) + (*it)->getH()) { 
          (*it)->setG(current->getG() + moveCost(*it,current)); 
          (*it)->setParent(current); 
         } 
         break; 
        } 
       } 
       bool exists_closed = (m_sClosed.find(n) != m_sClosed.end()); 
       if (!exists && !exists_closed) { 
        std::shared_ptr<Node> sN = std::make_shared<Node>(n); 
        sN->setParent(current); 
        sN->setG(current->getG() + moveCost(sN,current)); 
        sN->setH(manhattenCost(sN,m_nEnd)*heuristicWeight); 
        if (sN->getH() == 0) { m_sClosed.insert(*sN); return true; } 
        else m_sOpen.insert(sN); 
       } 

      } 
     } 
    } 
    return false; 
} 

Answer 1

std::set에서 std::priority_queue으로의 전환. 큐를 큐에 추가하기 전에 노드가 이미 열린 세트에 있는지 확인할 필요가 없습니다. 이미 닫혀진 세트에 삽입하지 않는 것이 더 쌉니다.