1

我尝试在 java 中创建 A* 算法，但我遇到了这个奇怪的错误。我知道 A* 并不总能找到最佳路径，但在这里它似乎违背了理性并选择了更糟糕的路径，而且我在代码中找不到导致此问题的错误。它似乎在我创建的其他地图上找到了最佳解决方案。这是错误的图片和节点的打印输出

在此处输入图像描述 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());
}
 }
4

3 回答 3

4

如果满足一项要求， A* 实际上总是给出最佳路径：

h(x,s) <= G(x,s) foreach x在哪里：

x- 某点

h()- 启发式功能

s- 停止点

G()- “oracle”功能，让您在点之间的距离最短（这当然是未知的）

诀窍是，与启发式函数一样，总是给出更短或等于魔法函数 G() 的距离，路径将是最短的。我在您的代码中看到的一个问题是，如果您是 fe. 从端点进行 1 次对角线跳跃，您的启发式函数将返回 20（mahnattan 距离），而您的代码中的实际成本 G() 为 14（这是 1 次对角线跳跃的成本）。我不知道这是否是唯一的错误，需要进一步研究代码，但尝试通过以下方式修复它：

  • 将 14 更改为 20，使其与启发式匹配
  • 使用不同的度量，fe。欧几里得。
于 2011-08-03T22:29:18.897 回答
3

首先，据我所知，A* 总是能找到最好的方法......

我没有查看您的所有代码，但是您的 manhatten 函数与我有关。A* 使用“可接受的启发式”，这意味着启发式函数可能不会高估前往目标节点的成本。如果是这样，您实际上有一个 A 算法，它可能找不到最佳路径。

为了排除这种情况，让你 manhatten 函数返回 0，这是一个可接受的启发式方法，因为它不会高估。如果您的问题仍然存在，则问题出在其他地方。

如果我没看错的话，对角线运动的成本是 10，而任何其他运动的成本是 14。考虑到这一点，你的 manhattan 函数返回 10 进行水平或垂直运动，这很好 (10 < 14) 但 20 用于对角线运动，这是不好的（20 > 10）。那可能是错误。

于 2011-08-03T22:29:29.617 回答
0

从您的图像来看，您实际上并没有计算正确的曼哈顿距离。没关系，你的曼哈顿方法看起来不错。

如果您允许对角线移动，那么倒数第二个移动与直接走向目标一样最佳。

（我承认我没有仔细阅读代码，虽然..太累了）

于 2011-08-03T22:14:14.843 回答