问题描述
在智能搜索问题中最常用的用于估计距离的启发式方法是什么?特别是，我对可以(通常)用作 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.
- Chebyshev 距离 - 沿单个坐标的距离，以较大者为准.虽然这通常是可以接受的(它会被低估，因为它没有考虑沿其他轴的运动)，但它的信息量绝对不如曼哈顿距离.这在某些情况下可能很有用，但并不常见.
- 闵可夫斯基距离 - 曼哈顿距离和欧几里得(直线)距离的一般情况.但是，它明显不如这两种特殊情况直观，因此，再次说明，我无法举出一个很好的例子来说明您何时会选择它而不是其中一种.
- 汉明距离 - 这并不适用于所有问题，但它计算为您需要对两个向量进行的最小编辑次数，以使它们相同.由于它是最小数量，因此对于某些问题可能是可以接受的，例如 具有等长单词.(如果字长不相等，则需要使用 Levenshtein Distance，它允许插入间隙.这需要相当长的时间来计算 (O(n^2))，因此不太可能成为一种有效的启发式方法).
- 堪培拉距离，一种缩放的曼哈顿距离，通常用于散布在原点周围的点，但在许多情况下是不可接受的.
- Jaccard 距离 是比较集合时使用的相似性度量的特点.它比不存在更强烈地加权特征的存在.需要对特征集使用启发式的问题相对少见，因此很难知道可接受性的合理默认假设是什么.总的来说，我猜想现有特征和不存在特征之间的不对称性可能会使 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.
这篇关于有哪些常见的可接受的距离启发式方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！