java - 优化 A* 算法

Question

我最近为我使用二维数组的基于代理的模型实现了 A* 算法。搜索的目的是为代理提供通向目标位置的位置列表。我的实现有效，但是有时当我执行算法时，它会返回一条仍然连接到主路径的替代路径。我不明白为什么要这样做。代码如下: http://pbrd.co/1DFaeIr

public boolean generatePath(Location startLocation, Location goalLocation) {
        setUpStartingPoint(startLocation, goalLocation); //Set up everything before search 
        boolean pathExist = false;
        int loop = 0;

        openList.add(startNode); //Put start node in openList (Initial starting point)
        while(pathExist == false) {
            if(openList.isEmpty() ==  false) { //More locations to check
                System.out.println("Step: " + loop);
                System.out.println(currentNode);
                System.out.println(openList);
                System.out.println(closedList);

                reOrderList(openList);
                Node lowestFvalueNode = openList.remove(0); //Get the node with the lowest F value in openList
                lowestFvalueNode.setParent(currentNode);
                currentNode = lowestFvalueNode;
                closedList.add(lowestFvalueNode);

                if(checkNodeInList(closedList, goalNode)) {
                    System.out.println("Found");
                    computeCurrentPath(currentNode);
                    pathExist = true;
                }
                else {
                    ArrayList<Node> currentNodeAdjNodes = getAdjacentNodes(currentNode);
                    for(Node adjNode : currentNodeAdjNodes) {
                        if(checkNodeInList(closedList, adjNode)) { //If node is in the closedList

                        }
                        else {
                            if(checkNodeInList(openList, adjNode) == false) {
                                computeNodeValues(adjNode); //Compute the G,H and F values of node
                                adjNode.setParent(currentNode); //Set the nodes parent as current node
                                openList.add(adjNode); //Add node to open list
                            }
                            else {
                                Node actualAdjNodeInOpenList = getNodeInList(openList, adjNode);
                                int currentMovementCostToNode = currentNode.getGvalue() + getMovementCostToNode(currentNode, adjNode);

                                if(currentMovementCostToNode < adjNode.getGvalue()) {
                                    computeNodeValues(adjNode);
                                    adjNode.setParent(currentNode);
                                    reOrderList(openList);
                                }
                            }
                        }
                    }
                }

                loop++;
            }
            else {
                pathExist = false;
                System.out.println("Path doesn't exist");
                return false;
            }
        }
        System.out.println(path);
        return pathExist;
    }

Answer 1

如果路径也是最优的，那么选择哪一条都没有关系。有一种优化算法的方法值得一试:使用 A* 和 Beam 搜索。束搜索将减少所需的内存空间。