A *算法错误(A* Algorithm Bug)

我试图创建Java中的A *算法，我有这个奇怪的错误。 我知道A *并不总能找到最佳路径，但这里似乎违背原因，并选择一个更糟糕的路径，我无法找到代码中的bug导致此。 这似乎找到我创建的其他地图的最佳解决方案。 下面是错误的图片，和节点的打印输出

http://i.imgur.com/IudT7.png

下面是（部分），我使用的代码。

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());
}
 }

Answer 1:

A *实际上给始终如果要求得到满足最佳路径：

h(x,s) <= G(x,s) foreach x其中：

x -一些点

h() - heurestic功能

s -停止点

G() - “神谕”的功能，让你点之间的最短距离（这当然是不知道的）

关键是，随着总是作为heurestic函数给出为短于或等于神奇函数G（）路径将是最短的距离。 有一个问题我与你的代码中看到的是，如果你是铁。 从端点1周斜跳，你heurestic函数将返回20（mahnattan距离），而实际成本G（）为14（这是1周跳的成本）在你的代码。 我不知道这是唯一的错误，需要进一步研究代码，而是试图通过固定它：

• 更改14至20，以便它匹配heurestic
• 使用不同的指标，铁。 欧氏。

Answer 2:

对于初学者来说，据我所知，A *总能找到最好的方式...

我没有看过了所有的代码，但是你的曼哈顿功能是关于我。 A *使用的“启发的”，意思是启发式功能可能高估前往目标节点的成本。 如果是的话，你实际上是具有A算法，它可能无法找到最佳路径。

要排除，让你曼哈顿函数返回0，这是一个启发的，因为它没有高估。 如果你的问题仍然与occures，问题是其他地方。

如果我看到的正确，您的对角线运动成本为10，其中对于任何其他运动的成本是14。给予，在你的曼哈顿功能水平或垂直移动，这是细返回10（10 <14），但20，用于对角线移动，这是不精（20> 10）。 这可能是错误。

Answer 3:

从你的形象，它看起来像你不是实际计算正确的曼哈顿距离。 没关系，你的曼哈顿方法看起来不错。

如果允许对角线移动，然后旁边的最后一步将是一样走直奔目标为最佳。

（我得承认，我没有看过的代码密切，但..太累了）

文章来源: A* Algorithm Bug