我用Java写了一个路径搜索算法，大多数情况下它都能良好工作。然而，我发现了一种情况它会出错。我使用的启发式算法应该是一致的，而一致的启发式意味着算法应该总是找到离扩展节点最近的路径，据我所知。
如果我将不等式改为"<=", 第一张图片中的问题会得到解决，但第二张图片则会出现混乱。
顺便说一下，我稍微扩展了A*算法，以便在没有路径时，它可以从关闭列表中获取最低的H成本节点，并运行另一个搜索来定位该节点。这样，即使当前没有到达目标节点的路径，它也可以接近目标。
我没有包含每个类，我认为其他类与此问题无关。如果有不清楚的地方，我会包括它们，但是我不想让问题太长难读。
据我所知，理论上一致的启发式可以保证最优代价的节点扩展，因此我还没有弄清楚如何解决不准确性。我的代码有错吗？如果没有，我该如何解决这个问题？
编辑：我包括了一些缺失的代码以澄清问题：
这是问题的图片:
起点是绿色的，数字只表示从每个特定节点到红色目标路径的长度。
我的启发式类：
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());
}
}
类Node有通常的G、H和F成本以及一个父引用。当构造函数接收到null作为parent参数时，它变成自己的父亲。这就是为什么在buildPath函数中遇到“lcnode == lcnode.getParent()”条件时，路径构建循环会停止，因为第一个扩展的节点是其自身的父亲。路径由Direction片段组成，每个片段由x和y坐标组成，每个坐标都是-1、0或1。
这样做的原因是我希望路径通过相对坐标来导向目标。没有地图边界检查，这是有意义的。我通过使边界节点不可行走来代替进行边界检查。
另一张图片：
这次效果非常好。这与我围绕最后一个关闭节点扩展节点的顺序有关，因为我像这样搜索最低成本的关闭节点：
for(Node n : openList) {
if(n.getCost() < lcnode.getCost()) {
lcnode = n;
}
}
如果我将不等式改为"<=", 第一张图片中的问题会得到解决，但第二张图片则会出现混乱。
顺便说一下，我稍微扩展了A*算法，以便在没有路径时，它可以从关闭列表中获取最低的H成本节点，并运行另一个搜索来定位该节点。这样，即使当前没有到达目标节点的路径，它也可以接近目标。
据我所知，理论上一致的启发式可以保证最优代价的节点扩展，因此我还没有弄清楚如何解决不准确性。我的代码有错吗？如果没有，我该如何解决这个问题？
编辑：我包括了一些缺失的代码以澄清问题：
class Direction:
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;}
}
类 Node：
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;
}
}