A-star (A*) 的曼哈顿启发式函数 [英] Manhattan Heuristic function for A-star (A*)

问题描述

我发现了这个算法 这里.

我有一个问题，我似乎无法理解如何设置和传递我的启发式函数.

I have a problem, I cant seem to understand how to set up and pass my heuristic function.

    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 个函数，一个距离函数和一个估计函数.

As you can see, it accepts 2 functions, a distance and a estimate function.

使用曼哈顿启发式距离函数，我需要取2个参数.我是否需要修改他的源代码并将其更改为接受 TNode 的 2 个参数，以便我可以将曼哈顿估计值传递给它?这意味着第 4 个参数将如下所示:

Using the Manhattan Heuristic Distance function, I need to take 2 parameters. Do I need to modify his source and change it to accepting 2 parameters of TNode so I can pass a Manhattan estimate to it? This means the 4th param will look like this:

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));
    }

推荐答案

好问题.我同意这篇文章令人困惑.我已更新它以解决您的问题.

Good question. I agree that the article was confusing. I've updated it to address your question.

首先，回答您提出的问题:您是否应该修改给出的代码以采用不同的功能?如果您愿意，当然可以，但您当然不必.我的建议是传递算法想要的函数，因为那是它需要的函数.为什么要传递算法不需要的信息?

First, to answer the question you asked: should you modify the code given to take a different function? If you want, sure, but you certainly don't have to. My advice is to pass the function that the algorithm wants, because that's the function that it needs. Why pass information that the algorithm doesn't need?

怎么办?

我给出的 A* 算法有两个函数.

The A* algorithm I give takes two functions.

第一个函数给出两个给定相邻节点之间的精确距离.

The first function gives the exact distance between two given neighbouring nodes.

第二个函数给出给定节点和目标节点之间的估计距离.

The second function gives the estimated distance between a given node and the destination node.

这是您没有的第二个功能.

It is the second function that you don't have.

如果您有一个函数可以给出两个给定节点之间的估计距离，并且您需要一个函数来给出给定节点之间的估计距离em> 和 目标节点 然后构建该函数:

If you have a function that gives the estimated distance between two given nodes and you need a function that gives the estimated distance between a given node and the destination node then just build that function:

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

你已经完成了.现在您拥有了所需的功能.

And you're done. Now you have the function you need.

这种通过将其中一个参数固定为某个值将双参数函数变为单参数函数的技术称为部分函数应用"，在函数式编程中极为常见.

This technique of turning a two-parameter function into a one-parameter function by fixing one of the parameters to a certain value is called "partial function application" and it is extremely common in functional programming.

这都清楚了吗?

现在讨论第二个更严重的问题.正如我在我的文章中所描述的，算法的正确操作取决于估计函数是否保守.你能保证曼哈顿距离永远不会高估吗?这似乎不太可能.如果网格中的任何地方都有对角"街道，则曼哈顿距离高估了两点之间的最佳距离，A* 算法将找不到它.大多数人将欧几里得距离(也称为 L2 范数)用于 A* 算法，因为根据定义，两点之间的最短距离并不是高估.你为什么使用曼哈顿距离?我很困惑为什么你认为这是一个好主意.

Now on to the second and much more serious problem. As I described in my articles, the correct operation of the algorithm is predicated on the estimation function being conservative. Can you guarantee that the Manhattan distance never overestimates? That seems unlikely. If there is a "diagonal" street anywhere in the grid then the Manhattan distance overestimates the optimal distance between two points, and the A* algorithm will not find it. Most people use the Euclidean distance (aka the L2 norm) for the A* algorithm because the shortest distance between two points is by definition not an overestimate. Why are you using the Manhattan distance? I am very confused as to why you think this is a good idea.

这篇关于A-star (A*) 的曼哈顿启发式函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！