Эвристика - это то, что имеет тенденцию быть очень специфичным для данной проблемы, поскольку идея состоит в том, чтобы включить дополнительные знания, которые могут возникнуть в связи с этой проблемой. Таким образом, «общая эвристика» не является очень полезной категорией. Тем не менее, похоже, что вы конкретно говорите о метриках расстояния, что является немного более четко определенным подмножеством.
В терминах допустимых эвристики для расстояния, два, которые вы уже упоминали, безусловно, наиболее распространенные:
- Прямая линия расстояние является единственным допустимым эвристика для общего, без ограничений движения в пространстве, так как кратчайший путь между любыми двумя точками - прямая.
- Конечно, любая сложная проблема будет иметь некоторые ограничения на движение. Общее одно из этих ограничений в этом движении должно происходить по одной оси за раз, и для таких проблем подходит Манхэттенское расстояние.
Есть еще некоторые популярные метрики расстояния, но они в меньшей степени применимы как эвристика.
- Чебышева Расстояние - расстояние вдоль одной координаты, в зависимости от того больше. Хотя это, как правило, допустимо (оно будет недооценивать, поскольку оно не учитывает движение по другим осям), оно менее информативно, чем расстояние Манхэттена. Иногда это может быть полезно, но они необычны.
- Minkowski Distance - общий случай Манхэттена Расстояние и эвклидово (прямая линия). Тем не менее, это заметно менее интуитивно, чем любой из этих особых случаев, поэтому опять же я не могу придумать хороший пример того, когда вы выберете его по одному из них.
- Хэмминг Расстояние - Это не относится ко всем проблемам, но оно рассчитано как минимальное количество изменений, которое вам нужно сделать для двух векторов, чтобы сделать их идентичными. Поскольку это минимальное число, оно потенциально допустимо для некоторых проблем, таких как word mutation game с одинаковыми длинными словами. (Если длина слов была неравнозначной, вам нужно будет использовать Levenshtein Distance, что позволяет вставлять промежутки. Это занимает довольно много времени, чтобы вычислить (O (n^2)) и, следовательно, менее вероятно, будет эффективной эвристикой) ,
- Canberra Distance, своего рода масштабированное Манхэттенское расстояние, часто используется для точек, разбросанных вокруг источника, но во многих случаях будет недопустимым.
- Jaccard Distance - мера подобия, используемая при сравнении наборов признаков. Он весит присутствие признаков сильнее, чем отсутствие. Проблемы, в которых вам нужно использовать эвристику для наборов функций, являются относительно необычными, поэтому трудно понять, какие разумные предположения о допустимости для допустимости будут. В общем, я бы предположил, что асимметрия между существующими и отсутствующими функциями может сделать недопустимым для Джакбара расстояние для некоторых проблем, но это, вероятно, не будет проблемой, если вы действительно заботитесь об имеющихся функциях.
Есть, конечно, много других метрик расстояния, но это те из них, которые менее популярны, чем прямая линия и расстояние Манхэттена, хотя и являются достаточно распространенными.