A* 算法错误 [英] A* Algorithm Bug
本文介绍了A* 算法错误的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我尝试在 Java 中创建 A* 算法，但遇到了这个奇怪的错误.我知道 A* 并不总能找到最佳路径，但在这里它似乎违背了理性并选择了一条更糟糕的路径，而且我在代码中找不到导致这种情况的错误.似乎在我创建的其他地图上找到了最佳解决方案.这是错误的图片，以及节点的打印输出
I tried creating the A* algorithm in java and I have this strange bug. I know the A* doesn't always find the best path, but here it seems to go against reason and choose a worse path, and I can't find the bug in the code causing this. It seems to find the optimal solution on other maps I created. Here is a picture of the bug, and a printout of the nodes
这是我使用的(部分)代码.
Here is (part of) the code that I used.
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
// Matt Bellis 7/31/2011
// A* Algorithm
public class AStar {
private PriorityQueue<Node> openQ;
private Queue<Node> closedQ;
private int [][] map;
private int startX, startY, endX, endY;
private Node endNode;
public AStar(int[][]map, int startX, int startY, int endX, int endY) {
openQ = new PriorityQueue<Node>();
closedQ = new LinkedList<Node>();
this.map = map;
this.startX = startX;
this.startY = startY;
this.endX = endX;
this.endY = endY;
endNode = new Node(endX, endY, 0, null); // for calculating the manhattan distances later
}
private int manhattanDist(Node curr, Node target) {
int cX, tX, cY, tY;
cX = curr.getX();
tX = target.getX();
cY = curr.getY();
tY = target.getY();
return 10*(Math.abs(cX - tX)+Math.abs(cY - tY));
}
private boolean onClosedList(Node node) {
if(closedQ.isEmpty() == true)
return false;
Iterator<Node> it = closedQ.iterator();
while(it.hasNext()) {
Node nodeCheck = it.next();
if(nodeCheck.getX() == node.getX() && nodeCheck.getY() == node.getY())
return true;
}
return false;
}
private boolean checkAndReplaceOpen(Node node, Node curr, boolean diag) { // true means replaced
Iterator<Node> it = openQ.iterator();
while(it.hasNext()) {
Node nodeCheck = it.next();
if(nodeCheck.getX() == node.getX() && nodeCheck.getY() == node.getY()) {
// they are the same node, check to see the g cost
if(node.getG() < nodeCheck.getG()) { //entered node is better path
if(diag == true)
node.setG(curr.getG()+14);
else
node.setG(curr.getG()+10);
node.setF(node.getG() + node.getH());
node.setParent(curr);
return true;
}
return false;
}
}
return false;
}
private void addNeighbors(Node node) {
int x = node.getX();
int y = node.getY();
//System.out.println("Node: "+node);
//System.out.println("Right: "+map[y][x+1]);
if((x+1)< map[y].length && map[y][x+1] !=1) {
Node newNode = new Node(x+1, y, map[y][x+1], node);
if(onClosedList(newNode) == false) {
newNode.setG(node.getG()+10);
newNode.setH(manhattanDist(newNode, endNode));
newNode.setF(newNode.getG()+newNode.getH());
if(checkAndReplaceOpen(newNode, node, false) == false)
openQ.add(newNode);
}
//System.out.println("1Added Node: "+newNode);
}
//System.out.println("Left: Y:"+y+" X:"+(x-1));
if((x-1) >= 0 && map[y][x-1] !=1 ) {
Node newNode = new Node(x-1, y, map[y][x-1], node);
if(onClosedList(newNode) == false) {
newNode.setG(node.getG()+10);
newNode.setH(manhattanDist(newNode, endNode));
newNode.setF(newNode.getG()+newNode.getH());
if(checkAndReplaceOpen(newNode, node, false) == false)
openQ.add(newNode);
}
//System.out.println("2Added Node: "+newNode);
}
//System.out.println("Up: "+map[y+1][x]);
if((y+1) < map.length && map[y+1][x] !=1) {
Node newNode = new Node(x, y+1, map[y+1][x], node);
if(onClosedList(newNode) == false) {
newNode.setG(node.getG()+10);
newNode.setH(manhattanDist(newNode, endNode));
newNode.setF(newNode.getG()+newNode.getH());
if(checkAndReplaceOpen(newNode, node, false) == false)
openQ.add(newNode);
}
//System.out.println("3Added Node: "+newNode);
}
//System.out.println("Down: "+map[y-1][x]);
if((y-1) > 0 && map[y-1][x] !=1) {
Node newNode = new Node(x, y-1, map[y-1][x], node);
if(onClosedList(newNode) == false) {
newNode.setG(node.getG()+10);
newNode.setH(manhattanDist(newNode, endNode));
newNode.setF(newNode.getG()+newNode.getH());
if(checkAndReplaceOpen(newNode, node, false) == false)
openQ.add(newNode);
}
//System.out.println("4Added Node: "+newNode);
}
// ADDING IN DIAGONAL
// top right
if((y+1) < map.length && (x+1) < map[y].length && map[y+1][x+1] !=1) {
Node newNode = new Node(x+1, y+1, map[y+1][x+1], node);
if(onClosedList(newNode) == false) {
newNode.setG(node.getG()+14);
newNode.setH(manhattanDist(newNode, endNode));
newNode.setF(newNode.getG()+newNode.getH());
if(checkAndReplaceOpen(newNode, node, true) == false)
openQ.add(newNode);
}
}
// top left
if((y+1) < map.length && (x-1) >= 0 && map[y+1][x-1] !=1) {
Node newNode = new Node(x-1, y+1, map[y+1][x-1], node);
if(onClosedList(newNode) == false) {
newNode.setG(node.getG()+14);
newNode.setH(manhattanDist(newNode, endNode));
newNode.setF(newNode.getG()+newNode.getH());
if(checkAndReplaceOpen(newNode, node, true) == false)
openQ.add(newNode);
}
}
// bottom left
if((y-1) > 0 && (x-1) >= 0 && map[y-1][x-1] !=1) {
Node newNode = new Node(x-1, y-1, map[y-1][x-1], node);
if(onClosedList(newNode) == false) {
newNode.setG(node.getG()+14);
newNode.setH(manhattanDist(newNode, endNode));
newNode.setF(newNode.getG()+newNode.getH());
if(checkAndReplaceOpen(newNode, node, true) == false)
openQ.add(newNode);
}
}
// bottom right
if((y-1) >= 0 && (x+1) < map[y].length && map[y-1][x+1] !=1) {
Node newNode = new Node(x+1, y-1, map[y-1][x+1], node);
if(onClosedList(newNode) == false) {
newNode.setG(node.getG()+14);
newNode.setH(manhattanDist(newNode, endNode));
newNode.setF(newNode.getG()+newNode.getH());
if(checkAndReplaceOpen(newNode, node, true) == false)
openQ.add(newNode);
}
}
}
private Node solve() {
Node startNode = new Node(startX, startY, 0, null);
startNode.setH(manhattanDist(startNode, endNode));
startNode.setF(startNode.getG() + startNode.getH());
openQ.add(startNode);
while(openQ.isEmpty() == false) { // keep going until the queue is empty, or you find the end node
Node currNode = openQ.remove();
closedQ.add(currNode);
if(currNode.getX() == endX && currNode.getY() == endY) {
return currNode;
}
addNeighbors(currNode);
}
System.out.println("No solution found!");
return startNode; // bad!
}
public LinkedList<Node> algorithm() {
LinkedList<Node> pathr = new LinkedList<Node>();
LinkedList<Node> path = new LinkedList<Node>();
Node addNode = solve();
while(addNode.getParent() != null) {
pathr.add(addNode);
addNode = addNode.getParent();
}
pathr.add(addNode);
while(pathr.isEmpty() == false)
path.add(pathr.removeLast());
return path;
}
public void printList(LinkedList<Node> list) {
Iterator<Node> it = list.iterator();
while(it.hasNext())
System.out.println(it.next());
}
}
推荐答案
如果满足一个要求，A* 实际上总是给出最佳路径:
A* actually gives best path always if one requirement is met:
h(x,s) <= G(x,s) foreach x 其中:
x - 某个点
h() - 启发式函数
s - 停止点
G() - oracle"函数，让你得到点之间的最短距离(这当然是未知的)
G() - "oracle" function that gives you shortest distance between points (which is of course not known)
诀窍是，与启发式函数一样，给出的距离更短或等于魔法函数 G() 路径将是最短的.我在您的代码中看到的一个问题是，如果您是 fe.从端点开始对角线跳跃 1 次，您的启发式函数将返回 20(马纳坦距离)，而您的代码中的实际成本 G() 为 14(这是 1 次对角线跳跃的成本).我不知道这是否是唯一的错误，需要进一步研究代码，但尝试通过以下方式修复它:
the trick is, that as always as heurestic function gives distances that are shorter or equal to magical function G() path will be the shortest. The one problem I see with your code, is that if you are fe. 1 diagonal jump from endpoint, your heurestic function will return 20 (mahnattan distance), while your actual cost G() is 14 (this is the cost of 1 diagonal jump) in your code. I don't know if this is the only bug, need to study the code further, but try fixing it by:
- 将 14 更改为 20，使其匹配启发式
- 使用不同的指标，fe.欧几里得.
这篇关于A* 算法错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
