Манхэттен Эвристическая функция для A-star (A *)

Question

Я нашел этот алгоритм здесь .

У меня проблема, я не могу понять, как настроить и передать мою эвристическую функцию.

    static public Path<TNode> AStar<TNode>(TNode start, TNode destination,
        Func<TNode, TNode, double> distance,
        Func<TNode, double> estimate) where TNode : IHasNeighbours<TNode>
    {
        var closed = new HashSet<TNode>();
        var queue = new PriorityQueue<double, Path<TNode>>();
        queue.Enqueue(0, new Path<TNode>(start));
        while (!queue.IsEmpty)
        {
            var path = queue.Dequeue();
            if (closed.Contains(path.LastStep))
                continue;
            if (path.LastStep.Equals(destination))
                return path;
            closed.Add(path.LastStep);
            foreach (TNode n in path.LastStep.Neighbours)
            {
                double d = distance(path.LastStep, n);
                var newPath = path.AddStep(n, d);
                queue.Enqueue(newPath.TotalCost + estimate(n), newPath);
            }
        }
        return null;
    }

Как видите, он принимает 2 функции: расстояние и функцию оценки.

Используя функцию эвристического расстояния Манхэттена, мне нужно взять 2 параметра. Нужно ли изменить его источник и изменить его так, чтобы он принимал 2 параметра TNode, чтобы я мог передать оценку Манхэттена этому? Это означает, что 4-й параметр будет выглядеть так:

Func<TNode, TNode, double> estimate) where TNode : IHasNeighbours<TNode>

и измените функцию оценки на:

queue.Enqueue(newPath.TotalCost + estimate(n, path.LastStep), newPath);

Моя функция на Манхэттене:

    private float manhattanHeuristic(Vector3 newNode, Vector3 end)
    {
        return (Math.Abs(newNode.X - end.X) + Math.Abs(newNode.Y - end.Y));
    }

Answer 1

Хороший вопрос. Я согласен, что статья была запутанной. Я обновил его, чтобы ответить на ваш вопрос.

Во-первых, чтобы ответить на вопрос, который вы задали: следует ли изменить данный код, чтобы он выполнял другую функцию? Если вы хотите, конечно, но вы, конечно, не должны. Мой совет - передать функцию, которую хочет алгоритм, потому что это функция, которая ему нужна. Зачем передавать информацию, которая не нужна алгоритму?

Как это сделать?

Алгоритм A *, который я даю, принимает две функции.

Первая функция дает точное расстояние между двумя заданными соседними узлами .

Вторая функция дает расчетное расстояние между данным узлом и целевым узлом .

Это вторая функция, которой у вас нет.

Если у вас есть функция, которая дает расчетное расстояние между двумя указанными узлами и вам нужна функция, которая дает приблизительное расстояние между данным узлом и узел назначения , затем просто создайте эту функцию:

Func<Node, Node, double> estimatedDistanceBetweenTwoNodes = whatever;
Func<Node, double> estimatedDistanceToDestination = n=>estimatedDistanceBetweenTwoNodes(n, destination);

И все готово. Теперь у вас есть нужная вам функция.

Этот метод преобразования двухпараметрической функции в однопараметрическую функцию путем фиксации одного из параметров к определенному значению называется «частичным применением функции», и он чрезвычайно распространен в функциональном программировании.

Это все ясно?

Теперь перейдем ко второй и гораздо более серьезной проблеме. Как я описывал в своих статьях, правильная работа алгоритма основывается на консервативной функции оценки . Можете ли вы гарантировать , что расстояние до Манхэттена никогда не переоценивает ? Это кажется маловероятным. Если где-нибудь в сетке есть «диагональная» улица, то манхэттенское расстояние переоценивает оптимальное расстояние между двумя точками, и алгоритм A * не найдет его. Большинство людей используют евклидово расстояние (также известное как норма L2) для алгоритма A *, поскольку кратчайшее расстояние между двумя точками по определению не является завышенной. Почему вы используете расстояние Манхэттен? Я очень смущен, почему вы думаете, что это хорошая идея.

Answer 2

Да, вам нужно изменить код, поскольку нет возможности добавить туда метод estimate с двумя TNode параметрами.