有哪些常见的距离启发式方法? [英] What are some common admissible heuristics for distance?

问题描述

在智能搜索问题中用于估计距离的最常见的启发式方法是什么?特别是，我对可以(通常)用作A *搜索的允许启发式的指标感兴趣.我碰到过直线距离和曼哈顿距离，但是还有其他距离吗?

What are the most common heuristics used to estimate distance in intelligent search problems? In particular, I'm interested in metrics that can (usually) be used as admissible heuristics for A* search. I came across straight line distance and Manhattan distance but are there any others?

推荐答案

启发式方法通常非常特定于给定的问题，因为其思想是合并您可能对该问题具有的更多知识.因此，一般启发式"不是一个非常有用的类别.就是说，这听起来像是您在专门谈论距离指标，它是一个定义更明确的子集.

Heuristics are something that tends to be very specific to a given problem, as the idea is to incorporate additional knowledge that you might have about that problem. So "general heuristics" isn't a very useful category. That said, it sounds like you are specifically talking about distance metrics, which is a slightly more well-defined subset.

就可接受的距离启发式方法而言，您已经提到的两个绝对是最常见的:

In terms of admissible heuristics for distance, the two that you already mentioned are definitely the most common:

• 直线距离是空间中一般无限制运动的唯一可允许的启发式方法，因为任意两点之间的最短路径是一条直线.
• 当然，几乎所有具有挑战性的问题都会对运动产生一些限制.这些限制中的常见限制之一是，移动一次必须沿一条轴发生，并且对于此类问题，曼哈顿距离是适当的.

• Straight line distance is the only admissible heuristic for general, unconstrained movement in space, because the shortest path between any two points is a straight line.
• Of course, just about any challenging problem will have some constraints on movement. A common one of these constraints in that movement must occur along a single axis at a time, and for such problems, Manhattan distance is appropriate.

还有其他一些流行的距离度量标准，但它们一般不适用于启发式方法.

There are some other popular distance metrics, but they are less generally applicable as heuristics.

• 切比雪夫距离-沿单个坐标的距离，以较大者为准.尽管这通常应该是可以接受的(这会被低估，因为它没有考虑沿其他轴的运动)，但它的信息量绝对不如曼哈顿距离.在某些情况下，这很有用，但并不常见.
• Minkowski距离 -曼哈顿距离和欧几里得(直线)距离的一般情况.但是，它显然不如这两种特殊情况中的任何一种直观，因此，再次，我无法提供一个很好的例子说明何时选择它们中的一种.
• Hamming Distance -不适用于所有问题，但是它是根据您需要对两个向量进行最小化编辑才能使其相同而计算的.由于它是最小数目，因此对于某些问题，例如堪培拉距离 比例缩放的曼哈顿距离，通常用于分散在原点周围的点，但在许多情况下是不可接受的.
• "Jaccard Distance" 是比较集时使用的相似性度量功能.它比不存在更强地加权特征的存在.需要在功能集上使用启发式的问题相对少见，因此很难知道可接受性的合理默认假设是什么.总的来说，我想现在和缺少的特征之间的不对称性可能会使Jaccard距离对于某些问题是不可接受的，但是如果您只真正关心现在的特征，则可能不会成为问题.

• Chebyshev Distance - the distance along a single coordinate, whichever is bigger. While this should usually be admissible (it will underestimate because it doesn't take into account movement along the other axes), it is strictly less informative than Manhattan distance. There may be some occasions where this is useful, but they are uncommon.
• Minkowski Distance - a general case of Manhattan Distance and Euclidean (straight line) distance. However, it is notably less intuitive than either of those special cases, so, again, I can't come up with a good example of when you would choose it over one of them.
• Hamming Distance - This isn't applicable to all problems, but it is calculated as the minimum number of edits that you would need to make to two vectors to make them identical. Since it is the minimum number, it would potentially be admissible for some problems, such as the word mutation game with equal length words. (If word lengths were unequal you would need to use Levenshtein Distance, which allows gaps to be inserted. This takes a fairly long time to compute (O(n^2)) and so is less likely to be an efficient heuristic).
• Canberra Distance, a sort of scaled Manhattan Distance, is often used for points scattered around the origin, but would be inadmissible in many cases.
• Jaccard Distance is a similarity measure used when comparing sets of features. It weights presences of features more strongly than absences. Problems in which you need to use a heuristic on feature sets are relatively uncommon, so it's hard to know what reasonable default assumptions for admissibility would be. In general, I would guess that the asymmetry between present and absent features could make Jaccard distance inadmissible for some problems, but that it's likely to not be a problem if you truly only care about present features.

当然，还有许多其他距离度量标准，但是这些度量标准大多数都比直线距离和曼哈顿距离更不受欢迎，但仍然相当普遍.

There are, of course, many other distance metrics, but these are most of the ones that are less popular than straight line and Manhattan distance while still being reasonably common.

这篇关于有哪些常见的距离启发式方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！