首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >优化A*算法

优化A*算法
EN

Stack Overflow用户
提问于 2015-02-04 21:23:32
回答 1查看 188关注 0票数 1

我最近为我的基于代理的模型实现了A*算法,它使用了一个2D数组。搜索的目的是为座席提供通向目标位置的位置列表。我的实现可以工作,但是有时当我执行算法时,它会返回一个替代路径,该路径仍然连接到主路径。我不明白它为什么要这么做。在下面编写代码:http://pbrd.co/1DFaeIr

代码语言:javascript
运行
复制
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;
    }
EN

回答 1

Stack Overflow用户

发布于 2015-02-04 21:41:53

如果路径也是最优的,那么选择哪一条都无关紧要。有一种方法可以优化算法,值得一试:结合使用A*和波束搜索。波束搜索将减少所需的存储空间。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/28322551

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档