我最近为我的基于代理的模型实现了A*算法,它使用了一个2D数组。搜索的目的是为座席提供通向目标位置的位置列表。我的实现可以工作,但是有时当我执行算法时,它会返回一个替代路径,该路径仍然连接到主路径。我不明白它为什么要这么做。在下面编写代码: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;
}
发布于 2015-02-04 21:41:53
如果路径也是最优的,那么选择哪一条都无关紧要。有一种方法可以优化算法,值得一试:结合使用A*和波束搜索。波束搜索将减少所需的存储空间。
https://stackoverflow.com/questions/28322551
复制相似问题