Ошибка алгоритма A *

Question

Я попытался создать алгоритм A * в Java, и у меня есть эта странная ошибка. Я знаю, что 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());
}
 }

Answer 1

A * фактически дает лучший путь всегда , если выполняется одно требование:

h(x,s) <= G(x,s) foreach x, где:

x - некоторая точка

h() - эвристическая функция

s - точка остановки

G() - функция «оракула», которая дает вам кратчайшее расстояние между точками (что, конечно, неизвестно)

Хитрость в том, что как всегда эвристическая функция дает расстояния, которые короче или равны магической функции G () путь будет самым коротким.Единственная проблема, которую я вижу с вашим кодом, заключается в том, что если вы чувствуете себя плохо.1 диагональный переход от конечной точки, ваша эвристическая функция вернет 20 (махаттанское расстояние), в то время как ваша фактическая стоимость G () равна 14 (это стоимость 1 диагонального прыжка) в вашем коде.Я не знаю, является ли это единственной ошибкой, необходимо изучить код дальше, но попробуйте исправить ее следующим образом:

• Изменение 14 на 20, чтобы оно совпадало с эвристическим
• Используйте другую метрику, напримеревклидовой.

Answer 2

Для начала, насколько я знаю, A * всегда находит лучший путь ...

Я не просмотрел весь ваш код, но ваша ручная функция касается меня. A * использует «допустимую эвристику», что означает, что эвристическая функция может не переоценивать стоимость поездки до целевого узла. Если это так, то у вас фактически есть алгоритм A, который может не найти лучший путь.

Чтобы исключить это, позвольте вам вручную вернуть функцию 0, что является допустимой эвристикой, потому что она не переоценивает. Если ваша проблема все еще возникает с этим, проблема в другом месте.

Если я правильно понимаю, ваша стоимость диагонального движения равна 10, тогда как стоимость любого другого движения равна 14. Принимая это, ваша манхэттенская функция возвращает 10 для горизонтального или вертикального движения, что нормально (10 <14) но 20 для диагонального перемещения, что не хорошо (20> 10). Это может быть ошибкой.

Answer 3

По вашему изображению похоже, что вы на самом деле не рассчитываете правильное манхэттенское расстояние. Не берите в голову, ваш манхэттенский метод выглядит хорошо.

Если вы допускаете движение по диагонали, то следующий за последним ходом такой же оптимальный, как и прямой путь к цели.

(Я признаю, что я не читал код близко, хотя .. слишком устал)