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*，您会发现它需要可受理性(而且我不记得一致性对于您的案例是否重要)。