启发式功能，使用星找到路径 [英] Heuristic function for finding the path using A star

问题描述

我试图寻找以下问题的最优解

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

1. 表示每个节点内的数字是重新psented为 $ P $（X，Y）。
2. 在相邻节点到节点总是有一个是值是（当前节点y值+1）。
3. 有1在 X 值，当我们从一个节点到其相邻
系统变化的成本
4. 在没有成本从节点将与其相邻，如果出现在 X 的值没有变化。
5. 使用相同的是价值2号节点被认为是相邻的。

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

• 节点的启发式重量=最小值（它启发重的子节点）
• 这同样适用于子节点了。

但据我所知的推移，启发式，就是要近似，所以我想我会在错误的方向尽可能的启发函数而言

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?

首先，它必须是的受理条件的，我。即应，对于任何节点，要么产生一个低估或一个正确的估计为最便宜的路径从该节点到任何目标的节点的成本。这意味着启发式不应高估的成本，从该节点到目标获得

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），并应preferably看当前节点孤单。递归评估成本，你建议会让你的搜索显著慢，不是越快！

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!

的*适用性的问题因此是你是否能拿出一个相当不错的启发。从您的问题描述，目前尚不清楚是否可以很容易地拿出之一。

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 *可能是，如果要求放松非常有益的。如果启发式变得不可接受的，那么你就失去找到最佳路径的保证。根据不同的距离，高估的程度，hovewer，解决方案可能仍不够好（为足够好的问题具体定义）。其优点是，有时你可以计算说，足够好的路径快得多。在某些情况下，启发式概率估计做工不错（它可以有额外的限制就可以留在允许的范围内）。

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 *通过选择费用较低的人的一些子集间接限制它们。有实际的情况不是由*即使有宽松的可容许，当在不同的搜索路径之间的成本差异是轻微的可以解决的。其硬限制波束搜索上的路径的数量更有效地工作在这样的问题。

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.

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