path-finding - 星型算法-G和H部分的帮助

Question

我在使H和G正常工作时遇到麻烦。发生的事情是，当我运行该程序时，它有时会找到最佳路径，而有时会偏离目的地。

以下是发生情况的屏幕截图:

Good path find

Bad path find

这是我当前对F，H和G的设置:

public double f(Node current, Node adj, Node goal)
{
    double f = g(current, adj) + h(current, goal);
    return f;
}

public double h(Node current, Node goal)
    {
        double dx = goal.getX() - current.getX();
        double dy = goal.getY() - current.getY();

        double h = Math.sqrt(dx*dx + dy*dy);

        return h;
    }

public double g(Node current, Node adj)
    {
        double dx = adj.getX() - current.getX();
        double dy = adj.getY() - current.getY();

        double g = Math.sqrt(Math.abs(dx) + Math.abs(dy));
        System.out.println("g " + g);
        return g;
    }

谢谢!

Answer 1

G值是从起点到当前节点的成本，而不仅仅是到相邻节点的成本。此刻，您正在做更多的贪婪搜索，只是朝最短的方向前进，而不回头看已经走了多远。

因此您得到了“从开始到当前的成本” +“(从当前到目标的)估算成本”。