Java A * Проблемы с реализацией

Question

Я написал реализацию алгоритма A *, взятый в основном из This wiki page, однако у меня есть серьезная проблема; в том, что я считаю, что я посещаю слишком много узлов при расчете маршрута, что разрушает мою работу. Я пытался выяснить проблему на несколько дней, и я не понимаю, что случилось. Обратите внимание, что все мои структуры данных реализованы самостоятельно, но я их протестировал и считаю, что это не проблема. На всякий случай я включил реализацию Queue Queue.

closedVertices - это хэш-карта вершин.

private Vertex routeCalculation(Vertex startLocation, Vertex endLocation, int routetype) 
{ 
    Vertex vertexNeighbour;    

    pqOpen.AddItem(startLocation); 

    while (!(pqOpen.IsEmpty())) 
    {  
     tempVertex = pqOpen.GetNextItem(); 


      for (int i = 0; i < tempVertex.neighbors.GetNoOfItems(); i++) //for each neighbor of tempVertex 
      { 
       currentRoad = tempVertex.neighbors.GetItem(i); 
       currentRoad.visited = true; 

       vertexNeighbour = allVertices.GetNewValue(currentRoad.toid); 

       //if the neighbor is in closed set, move to next neighbor 
       checkClosed();    
       nodesVisited++; 
       setG_Score(); 
       //checks if neighbor is in open set 
       findNeighbour(); 
       //if neighbour is not in open set 
       if (!foundNeighbor || temp_g_score < vertexNeighbour.getTentativeDistance()) 
       { 
        vertexNeighbour.setTentativeDistance(temp_g_score); 
        //calculate H once, store it and then do an if statement to see if it's been used before - if true, grab from memory, else calculate. 
        if (vertexNeighbour.visited == false) 
         vertexNeighbour.setH(heuristic(endLocation, vertexNeighbour)); 


         vertexNeighbour.setF(vertexNeighbour.getH() + vertexNeighbour.getTentativeDistance());      

        // if neighbor isn't in open set, add it to open set 
        if (!(foundNeighbor)) 
        {  
         pqOpen.AddItem(vertexNeighbour); 
        } 
        else 
        { 
         pqOpen.siftUp(foundNeighbourIndex); 
        } 
       } 

      } 
     } 
    } 
    return null; 
} 

Может ли кто-нибудь увидеть, где я могу исследовать слишком много узлов?

Кроме того, я попытался реализовать способ вычисления самого быстрого (синхронизированного) маршрута путем изменения F по скорости дороги. Правильно ли я говорю, что это правильный способ сделать это? (Я разделил скорость дороги на 100, потому что в противном случае потребовалось много времени).

Answer 1

Я нашел свою собственную ошибку; Я реализовал способ вычисления эвристики для каждого узла неправильно - у меня был оператор IF, чтобы проверить, был ли H уже рассчитан, но я сделал это неправильно, и поэтому он никогда не вычислял H для некоторых узлов; что приводит к чрезмерному исследованию узлов. Я просто удалил строку: if (vertexNeighbour.visited == false), и теперь у меня есть идеальные вычисления.

Однако я все еще пытаюсь выяснить, как рассчитать самый быстрый маршрут с точки зрения времени.