java - A*寻路算法——找到一条路径，但不是最优的最佳路径

Question

我正在研究 A* 算法。这是寻路方法的代码。作为引用，这是我正在使用的主板:/image/ORBqb.png每个颜色 block 代表不同的启发值。由于某种未知的原因，它每次都会找到一条路径，但并不总是正确的路径。这是寻路方法的代码。如果有人需要任何澄清，我很乐意提供。

public List<Point> findPath(Point start, Point end) {

    //declarations and instantiations
    List<PathState> closedList = new ArrayList<PathState>();    //the nodes already considered
    List<PathState> openList = new ArrayList<PathState>();      //nodes to be considered
    openList.add(new PathState(start, end, tm));                //add starting point
    PathState current = openList.get(0);

    while(!current.isGoal()){
        //sort open list to find the pathstate with the best hscore(sorts by hscore)
        Collections.sort(openList);
        current = openList.get(openList.size() - 1);
        closedList.add(current);
        openList.remove(current);

        //get the valid children of current node
        List<PathState> children = current.getChildren();;

        if(!current.isGoal()){              
            for(int i = 0; i < children.size(); i++){
                if(!closedList.contains(children.get(i))){
                    if(openList.contains(children.get(i))){
                        if(openList.get(openList.indexOf(children.get(i))).getgScore() > children.get(i).getgScore()){
                            //child is already on the open list, but this node has lower g value
                            //change g value and parent of node on open list
                            openList.get(openList.indexOf(children.get(i))).setG(children.get(i).getgScore());
                            openList.get(openList.indexOf(children.get(i))).changeParent(current);
                    }
                    }else{
                        //child not in closed list
                        openList.add(children.get(i));

                        //repaint the terrain panel with shades
                        tp.addAstarState(children.get(i));
                        tp.repaint();
                        try {
                            Thread.sleep(25);
                        } catch(Exception e) {
                            e.printStackTrace();
                        }
                    }
                }
            }
        }
    }
    //returns the path from winning node to start for output
    return current.getPath();
}

Answer 1

A* 基本上是 Djikstra 的算法，但您可以通过将距离函数与剩余距离的估计相结合来将搜索定向到目的地。

在节点 x 处，djikstra 的成本或“分数”为 (distance_so_far)

在 A* 处，它是 (distance_so_far + approximation_of_remaining_distance)

为了确保 A* 找到最短路径，estimate_of_remaining_distance必须是真正的下界。这意味着它必须始终小于实际剩余距离。这意味着，您永远不能高估这个距离，否则它会变成不精确的启发式，在这种情况下它不一定能找到最短路径。

这是一个很好的引用:http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

它链接到此引用文献，该引用文献解释了有关启发式函数的更多信息:http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html