Java A* 实施问题

Question

我写了一个 A* 算法的实现，主要取自 This wiki page，但是我有一个主要问题；因为我相信我在计算路线时访问了太多节点，因此破坏了我的表现。几天来我一直在试图找出问题所在，但我看不出出了什么问题。请注意，我所有的数据结构都是自行实现的，但我已经对其进行了测试并相信它们不是问题所在。为了以防万一，我已经包含了我的优先级队列实现。

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) 现在我有了完美的计算。

不过，我仍在努力弄清楚如何根据时间计算最快的路线。

Java A* 实施问题

Java A* Implementation Issues

java

path

a-star

path-finding