A *探路者给出次优路径

我在java中编写了一个探路者，在大多数情况下，它运行得很好 . 但是，我发现了一个出错的情况 . 我使用的启发式应该是一致的，并且一致的启发式意味着算法应该始终找到到它扩展的节点的最近路径，据我所知 .

这是问题的图片：

起始节点为绿色，数字仅表示从每个特定节点到以红色表示的目标的路径长度 .

我的启发式课程：

package heuristics;
import pathcomponents.Direction;


public class Heuristics {

    public static int DO(int x1, int y1, int x2, int y2) {
        int dx = Math.abs(x1 - x2);
        int dy = Math.abs(y1 - y2);
        int D, O;
        if(dx > dy) {
            D = dy;
            O = dx - D;
        }
        else {
            D = dx;
            O = dy - D;
        }
        return D*Direction.D_COST + O*Direction.O_COST;
    }

}

Direction.D_COST = 14，Direction.O_COST = 10

启发式返回以下值：对角线距离* 14正交距离* 10 .

算法：

package pathfinders;


import java.util.LinkedList;
import pathcomponents.Direction;
import pathcomponents.Node;
import pathcomponents.Path;
import heuristics.Heuristics;


public class ProxyAStar {

    static private boolean contains(LinkedList<Node> list, int x, int y) {
        for(Node n : list)
            if(n.getX() == x && n.getY() == y) return true;
        return false;
    }

    public static Path buildPath(Node lcnode) {
        int cost = lcnode.getG();
        LinkedList<Direction> path = new LinkedList<Direction>();
        while(lcnode != lcnode.getParent()) {
            int dx = lcnode.getX() - lcnode.getParent().getX();
            int dy = lcnode.getY() - lcnode.getParent().getY();
            path.add(new Direction(dx, dy));
            lcnode = lcnode.getParent();
        }
        return new Path(path, cost);
    }

    public static Path search(boolean[][] map, int sx, int sy, int gx, int gy) {
        LinkedList<Node> openList   = new LinkedList<Node>();
        LinkedList<Node> closedList = new LinkedList<Node>();
        openList.add(new Node(sx, sy, 0, Heuristics.DO(sx, sy, gx, gy), null));
        while(!openList.isEmpty()) {
            Node lcnode = openList.peekFirst();
            for(Node n : openList) {
                if(n.getCost() < lcnode.getCost()) {
                    lcnode = n;
                }
            }
            int x = lcnode.getX();
            int y = lcnode.getY();
            if(x == gx && y == gy) {
                return buildPath(lcnode);
            }
            closedList.add (lcnode);
            openList.remove(lcnode);
            for(int i = -1; i <= 1; ++i) {
                for(int j = -1; j <= 1; ++j) {
                    int cx = x + i;
                    int cy = y + j;
                    if((i == 0 && j == 0) || map[cx][cy] == false)continue;
                    if(!contains(openList,cx,cy) && !contains(closedList,cx,cy)){
                        openList.add(new Node(cx, cy, lcnode.getG() + Heuristics.DO(x, y, cx, cy), Heuristics.DO(cx, cy, gx, gy), lcnode));
                    }
                }
            }
        }
        Node lcnode = closedList.peekFirst();
        for(Node n : closedList) {
            if(n.getH() < lcnode.getH()) {
                lcnode = n;
            }
        }
        openList   = null;
        closedList = null;
        return search(map, sx, sy, lcnode.getX(), lcnode.getY());
    }
}

类节点具有通常的G，H和F成本以及父引用 . 当构造函数接收null作为父参数时，它将成为其自己的父参数 . 这就是为什么在buildPath函数中满足条件“lcnode == lcnode.getParent（）”时路径构建循环停止的原因，因为展开的第一个节点是父本身 . 路径由方向片组成，它由x和y坐标组成，每个坐标为-1,0或1.原因是我希望路径通过相对坐标导向目标 . 没有 Map 边框检查，这是故意的 . 我通过使边界节点不可移动来替换它 .

另外一张照片：

这次运作得很好 . 差异与我在最后一个colsed节点周围扩展节点的顺序有关，因为我搜索成本最低的封闭节点，如下所示：

for(Node n : openList) {
    if(n.getCost() < lcnode.getCost()) {
        lcnode = n;
    }
}

如果我将不等式更改为“<=”，则第一张图片中的问题将被修复，第二张图片中的问题会变得混乱 .

在旁注中，我稍微扩展了A *，这样如果没有路径，它将从关闭列表中获得最低的H cost节点，并运行另一个针对该节点的搜索 . 这样，即使目前没有到目标节点的路径，它也会接近目标 .

我没有把每个 class 都包括在内，我认为其他 class 与这个问题无关 . 如果某些事情不清楚，我会哄骗他们，不想让这个问题读得太长 .

据我所知，理论规定一致的启发式方法可以保证节点以最优的成本扩展，因此我无法弄清楚如何解决这种不准确性 . 我在代码中犯了什么错误吗？如果没有，我该如何解决这个问题呢？

编辑：我包含了一些缺失的代码，以使事情清楚：

class 方向：

package pathcomponents;
public class Direction {
    public static final int D_COST = 14;
    public static final int O_COST = 10;
    public static int signum(int n) {
        return (n < 0) ? -1 : ((n == 0) ? 0 : 1);
    }
    private final int x, y;
    public Direction(int x, int y) {
        this.x = signum(x);
        this.y = signum(y);
    }
    public Direction(Direction source) {
        this.x = source.x;
        this.y = source.y;
    }
    public int getX() {return x;}
    public int getY() {return y;}
}

类节点：

package pathcomponents;
public class Node {
    private final int    x, y;
    private       int       G;
    private final int       H;
    private       int       F;
    private       Node parent;
    public Node(int x, int y, int G, int H, Node parent) {
        this.x      =                                x;
        this.y      =                                y;
        this.G      =                                G;
        this.H      =                                H;
        this.F      =                            G + H;
        this.parent = (parent == null) ? this : parent;
    }
    public int  getX()      {return      x;}
    public int  getY()      {return      y;}
    public int  getG()      {return      G;}
    public int  getH()      {return      H;}
    public int  getCost()   {return      F;}
    public Node getParent() {return parent;}
    public void setParent(Node parent, int G) {
        this.parent = parent;
        this.G      =      G;
        F           = G +  H; 
    }
}