我用 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;
}
}
方向.D_COST = 14，方向.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。原因是我希望路径通过相对坐标通向目标。没有地图边界检查，这是故意的。我通过使边界节点不可行走来代替它。
另一张照片：
这次效果很好。区别与我在最后一个关闭节点周围展开节点的顺序有关，因为我搜索成本最低的关闭节点，如下所示：
for(Node n : openList) {
if(n.getCost() < lcnode.getCost()) {
lcnode = n;
}
}
如果我将不等式更改为“<=”，则第一张图片中的问题已解决，而第二张图片则搞砸了。
附带说明一下，我稍微扩展了 A*，以便如果没有路径，它会从封闭列表中获取最低 H 成本节点，并针对该节点运行另一个搜索。这样，即使当前没有通往目标节点的路径，它也会接近目标。
我没有包括每一堂课，我认为其他的与这个问题无关。如果有不清楚的地方，我会包括他们，但不想让问题太长而无法阅读。
据我所知，理论表明一致的启发式方法可以保证节点扩展具有最佳成本，所以我还不知道如何解决不准确的问题。我在代码中犯了任何错误吗？如果没有，我该如何解决这个问题？
编辑：我包括了一些缺失的代码以使事情变得清晰：
上课方向：
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;
}
}