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 のいずれかです。この理由は、パスが相対座標によってゴールにつながるようにしたかったからです。マップの境界チェックはありません。これは意図的なものです。これを、境界ノードを歩行不能にすることで置き換えます。
他の写真：
今回はうまくいきます。違いは、次のように最小コストの閉じたノードを検索するため、最後の colsed ノードの周りにノードを展開する順序に関係しています。
for(Node n : openList) {
if(n.getCost() < lcnode.getCost()) {
lcnode = n;
}
}
不等式を「<=」に変更すると、最初の図の問題が修正され、2 番目の図が台無しになります。
余談ですが、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;
}
}