A* 启发式，高估/低估? [英] A* heuristic, overestimation/underestimation?

问题描述

我对高估/低估这两个术语感到困惑.我完全了解 A* 算法的工作原理，但我不确定高估或低估启发式算法的影响.

I am confused about the terms overestimation/underestimation. I perfectly get how A* algorithm works, but i am unsure of the effects of having a heuristic that overestimate or underestimate.

当你取直接鸟瞰线的平方时是不是高估了?为什么它会使算法不正确?所有节点都使用相同的启发式方法.

Is overestimation when you take the square of the direct birdview-line? And why would it make the algorithm incorrect? The same heuristic is used for all nodes.

当您取直接鸟瞰线的平方根时是否低估?为什么算法仍然正确?

Is underestimation when you take the squareroot of the direct birdview-line? And why is the algorithm still correct?

我找不到解释清楚的文章，所以我希望这里有人有一个很好的描述.

I can't find an article which explains it nice and clear so I hope someone here has a good description.

推荐答案

当启发式的估计高于实际最终路径成本时，您就高估了.当它较低时，您就低估了(您不必低估，您只需要不要高估；正确 估计就可以了).如果你的图的边成本都是 1，那么你给出的例子会提供高估和低估，尽管平面坐标距离在笛卡尔空间中也很有效.

You're overestimating when the heuristic's estimate is higher than the actual final path cost. You're underestimating when it's lower (you don't have to underestimate, you just have to not overestimate; correct estimates are fine). If your graph's edge costs are all 1, then the examples you give would provide overestimates and underestimates, though the plain coordinate distance also works peachy in a Cartesian space.

高估并不完全使算法不正确"；这意味着您不再有可接受的启发式，这是保证 A* 产生最佳行为的条件.使用不可接受的启发式方法，该算法可能会做大量多余的工作来检查它应该忽略的路径，并且可能会因为探索这些路径而找到次优路径.这是否真的发生取决于您的问题空间.之所以会发生这种情况，是因为路径成本与估计成本脱节"，这实质上使算法对哪些路径比其他路径更好的想法变得一团糟.

Overestimating doesn't exactly make the algorithm "incorrect"; what it means is that you no longer have an admissible heuristic, which is a condition for A* to be guaranteed to produce optimal behavior. With an inadmissible heuristic, the algorithm can wind up doing tons of superfluous work examining paths that it should be ignoring, and possibly finding suboptimal paths because of exploring those. Whether that actually occurs depends on your problem space. It happens because the path cost is 'out of joint' with the estimate cost, which essentially gives the algorithm messed up ideas about which paths are better than others.

我不确定您是否会找到它，但您可能想查看 维基百科A* 文章.我提到(和链接)主要是因为 Google 几乎不可能找到它.

I'm not sure whether you will have found it, but you may want to look at the Wikipedia A* article. I mention (and link) mainly because it's almost impossible to Google for it.

这篇关于A* 启发式，高估/低估?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！