曼哈顿A级明星的启发式功能(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.

使用Manhattan Heuristic Distance函数，我需要采用2个参数.我是否需要修改他的源并将其更改为接受TNode的2个参数，以便可以向其传递曼哈顿估算值?这意味着第四个参数将如下所示:

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级明星的启发式功能(A *)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！