使用 A 星寻找路径的启发式函数 [英] Heuristic function for finding the path using A star

问题描述

我正在尝试为以下问题找到最佳解决方案

I am trying to find a optimal solution for the following problem

1. 每个节点内表示的数字表示为(x,y).
2. 一个节点的相邻节点总是有一个 y 值，即(当前节点 y 值 +1).
3. 当我们从一个节点到其相邻节点时，x 值的变化成本为 1
4. 如果 x 的值没有变化，则从节点到其相邻节点没有成本.
5. 没有 2 个具有相同 y 值的节点被认为是相邻的.

1. The numbers denoted inside each node are represented as (x,y).
2. The adjacent nodes to a node always have a y value that is (current nodes y value +1).
3. There is a cost of 1 for a change in the x value when we go from one node to its adjacent
4. There is no cost for going from node to its adjacent, if there is no change in the value of x.
5. No 2 nodes with the same y value are considered adjacent.

最优方案是成本最低的方案，我正在考虑使用 A* 寻路算法来寻找最优方案.

The optimal solution is the one with the lowest cost, I'm thinking of using A* path finding algorithm for finding an optimal solution.

我的问题，A*是解决这类问题的好选择，还是我应该看看其他算法，我也在考虑使用递归方法来计算启发式成本，但我觉得它不是个好主意.

My question, Is A* a good choice for the this kind of problems, or should i look at any other algorithm, and also i was thinking of using recursive method to calculate the Heuristic cost, but i get the feeling that it is not a good idea.

这是我认为启发式函数会像这样的示例

This is the example of how I'm thinking the heuristic function will be like this

• 节点的启发式权重 = Min(其子节点的启发式权重)
• 子节点也是如此.

但据我所知，启发式是一个近似值，所以我认为就启发式函数而言，我走错了方向

But as far as my knowledge goes, heuristic is meant to be an approximate, so I think I'm going in the wrong direction as far as the heuristic function is concerned

推荐答案

A* 保证在具有非负边路径成本的图中找到成本最低的路径，前提是您使用了适当的启发式方法.什么使启发式函数合适?

A* guarantees to find the lowest cost path in a graph with nonnegative edge path costs, provided that you use an appropriate heuristic. What makes a heuristic function appropriate?

首先，它必须可接受，即.e.对于任何节点，它应该对从该节点到任何目标节点的最便宜路径的成本产生低估或正确估计.这意味着启发式算法永远不应该高估从节点到目标的成本.

First, it must be admissible, i. e. it should, for any node, produce either an underestimate or a correct estimate for the cost of the cheapest path from that node to any of goal nodes. This means the heuristic should never overestimate the cost to get from the node to the goal.

请注意，如果您的启发式计算每个节点的估计成本为 0，那么 A* 只会变成广度优先穷举搜索.所以 h(n)=0 仍然是一种可接受的启发式方法，只是最糟糕的一种.因此，在所有可接受的启发式方法中，对目标成本的估计越严格，效果越好.

Note that if your heuristic computes the estimate cost of 0 for every node, then A* just turns into breadth-first exhaustive search. So h(n)=0 is still an admissible heuristic, only the worst possible one. So, of all admissible heuristics, the tighter one estimates the cost to the goal, the better it is.

其次，计算必须便宜.它肯定应该是 O(1)，并且最好单独查看当前节点.按照您的建议递归评估成本将使您的搜索速度明显变慢，而不是更快！

Second, it must be cheap to compute. It should be certainly O(1), and should preferably look at the current node alone. Recursively evaluating the cost as you propose will make your search significantly slower, not faster!

因此，A* 适用性的问题是您是否能提出一个相当好的启发式方法.从你的问题描述来看，你是否可以轻松地想出一个并不清楚.

The question of A* applicability is thus whether you can come up with a reasonably good heuristic. From your problem description, it is not clear whether you can easily come up with one.

根据问题域，如果放宽要求，A* 可能非常有用.如果启发式变得不可接受，那么您将失去找到最佳路径的保证.然而，根据距离的高估程度，解决方案可能仍然足够好(对于足够好"的问题特定定义).优点是有时您可以更快地计算足够好"的路径.在某些情况下，启发式的概率估计效果很好(它可以有额外的约束以保持在可接受的范围内).

Depending on the problem domain, A* may be very useful if requirements are relaxed. If heuristic becomes inadmissible, then you lose the guarantee of finding the best path. Depending on the degree of overestimation of the distance, hovewer, the solution might still be good enough (for problem specific definition of "good enough"). The advantage is that sometimes you can compute that "good enough" path much faster. In some cases, probabilistic estimate of heuristics works good (it can have additional constraints on it to stay in the admissible range).

因此，一般来说，您对易处理问题进行广度优先搜索，接下来更快地获得 A* 用于具有可接受启发式的易处理问题.如果您的问题对于广度优先穷举搜索难以处理并且不承认启发式，那么您唯一的选择是满足于足够好"的次优解决方案.同样，A* 在这里可能仍然适用于不可接受的启发式，或者您应该查看波束搜索品种.不同之处在于，波束搜索对当前探索图的数量有限制，而 A* 通过选择成本较低的一些子集来间接限制它们.当不同搜索路径之间的成本差异很小时，即使具有宽松的可接纳性，也存在 A* 无法解决的实际情况.对路径数量有严格限制的波束搜索在此类问题中更有效.

So, in general, you have breadth-first search for tractable problems, next faster you have A* for tractable problems with admissible heuristic. If your problem is intractable for breadth-first exhaustive search and does not admit a heuristic, then your only option is to settle for a "good enough" suboptimal solution. Again, A* may still work with inadmissible heuristic here, or you should look at beam search varieties. The difference is that beam searches have a limit on the number of ways the graph is currently being explored, while A* limits them indirectly by choosing some subset of less costly ones. There are practical cases not solvable by A* even with relaxed admissbility, when difference in cost among different search path is slight. Beam search with its hard limit on the number of paths works more efficiently in such problems.

这篇关于使用 A 星寻找路径的启发式函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！