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

Question

我正在研究一个A*算法。这是寻路方法的代码。作为参考，这是我正在使用的板：http://i.imgur.com/xaAzNSw.png?1每种颜色的瓷砖代表不同的启发式数值。由于某些未知的原因，它每次都会找到一条路径，只是并不总是正确的路径。以下是寻路方法的代码。如果任何人需要任何澄清，我很乐意提供。

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 + estimate_of_remaining_distance)

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

这是一个很好的参考：http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

它链接到这个参考，它解释了更多关于启发式函数的内容：http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html