algorithm - 使用具有困难限制的 A Star 查找最短路径

Question

我需要解决以下问题:我有一个网格，您可以在其中沿 8 个方向移动，N、S、E、W、NE、NW、SE、SW。

正交移动总是花费 1。如果前一个移动是正交的，或者如果前一个移动是对角线且花费 2，则对角移动花费 1，否则花费 2。

所以举几个例子来更好地解释:

1. 移动 NE,NE 将花费 1+2 = 3

2. 移动 NE,E,NE 将花费 1+1+1 = 3

3. 移动 NE,NE,NE 将花费 1+2+1 = 4

我认为这足以了解它的要点。

我不知道如何实现 A* 算法来实现这一目标。我的启发式函数:

private double heuresticDistance(Node p1, Node p2){
        double dx = Math.abs(p1.x - p2.x);
        double dy = Math.abs(p1.y - p2.y);
        // D = 1d, D2 = 1.5d;
        return D * (dx + dy) + (D2 - 2 * D) * Math.min(dx, dy);
    }

显然，在这种情况下它并不好，在某些情况下它不会走最短路径(成本方面)，这意味着它可能会采用不同的方式来降低成本。

重要的是它总是会找到最便宜的，或者如果有多个则找到最便宜的一个。

你能给我一些提示吗？我的 A* 实现非常简单，我想我是根据维基百科伪代码编写的。

编辑:

public class Node{
    public int x,y;
}

Answer 1

您的启发式函数不是 admissible .

查看从 (0, 0) 到 (1, 1) 的路径。您的启发式告诉您它等于 1 * (1 + 1) + (1.5 - 2) * 1 = 1.5。但是路径是 1。所以你高估了你的目标，从而使你的启发式 Not Acceptable ，这导致 A* 找到错误的路径。

仔细看看 A*，你会发现它需要可接纳性(而且我不记得一致性对你的情况是否重要)。