Алгоритм Звезды - Справка по части G и H

Question

У меня проблемы с настройкой функций H и G. Происходит то, что когда я запускаю программу, она иногда находит лучший путь, а иногда уходит из пути, чтобы добраться до места.

Вот несколько скриншотов происходящего:

Хороший поиск пути

Неверный путь поиска

Это мои текущие настройки для 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 - это стоимость от начала до текущего узла, а не только до соседнего узла. В данный момент вы больше занимаетесь жадным поиском, просто идете вперед в кратчайшем направлении и не смотрите назад, как далеко вы уже прошли.

так что вы получили «стоимость от начала до текущей» + «(ниже) оценочную стоимость от текущей до цели».