Являются ли эвристические функции отрицательными значениями недопустимыми?

Question

Насколько я понимаю, допустимость эвристики остается в пределах «фактической стоимости расстояния» для данного оцениваемого узла. Я должен был разработать некоторые эвристики для поиска решений A * в пространствах состояний и получил большую положительную эффективность, используя эвристику, которая иногда может возвращать отрицательные значения, поэтому, чтобы определенные узлы были более «плотно сформированы» с целью государство имеет более высокое место на границе.

Однако, я беспокоюсь, что это недопустимо, но не может найти достаточно информации в Интернете, чтобы проверить это. I did find this one paper from the University of Texas, который, как представляется, упоминается в одном из последних доказательств того, что «... поскольку эвристические функции неотрицательны». Может ли кто-нибудь подтвердить это? Я предполагаю, что это потому, что вы возвращаете отрицательное значение, поскольку ваша эвристическая функция превратит ваш g-cost отрицательный (и, следовательно, вмешивается в «поведение по умолчанию» dijkstra-esque A *).

Answer 1

Заключения: Эвристические функции, которые производят отрицательные значения не являются неприемлемыми, по себе, но есть потенциал, чтобы сломать гарантии A *.

Интересный вопрос. По сути, единственным условием приемлемости является то, что эвристика никогда не переоценивает расстояние до цели. Это важно, потому что переоценка в неправильном месте может искусственно сделать лучший путь хуже, чем другой путь, и не позволять ему когда-либо изучаться. Таким образом, эвристика, которая может обеспечить завышенные значения, теряет гарантию оптимальности. Недооценка не несет те же затраты. Если вы недооцениваете стоимость перехода в определенном направлении, в конечном итоге весы кромки будут превышать стоимость перехода в другом направлении, поэтому вы также изучите это направление. Единственная проблема - потеря эффективности.

Если все ваши края имеют положительные затраты, отрицательное эвристическое значение может быть только недооценено. Теоретически недооценка должна быть только хуже, чем более точная оценка, поскольку она обеспечивает строго меньшую информацию о потенциальной стоимости пути и, вероятно, приведет к увеличению количества узлов. Тем не менее, это не будет недопустимым.

Однако, вот пример, который показывает, что теоретически возможно при отрицательных эвристические значения нарушить гарантированную оптимальность A *:

В этом графике, очевидно, лучше пройти через узлы A и B. Это будет стоить три, а не шесть, что является стоимостью прохождения через узлы C и D. Однако отрицательные эвристические значения для C и D приведут к тому, что A * достигнет конца через них до исследуя узлы A и B. В сущности, эвристическая функция продолжает думать, что этот путь станет значительно лучше, пока не станет слишком поздно. В большинстве реализаций A * это вернет неправильный ответ, хотя вы можете исправить эту проблему, продолжая исследовать другие узлы, пока наибольшее значение для f (n) не будет больше стоимости найденного вами пути. Обратите внимание, что в этой эвристике нет ничего недопустимого или непоследовательного. На самом деле я действительно удивлен тем, что неотрицательность чаще всего упоминается как правило для эвристики A *.

Конечно, все это демонстрирует, что вы не можете свободно использовать эвристику, которая возвращает отрицательные значения, не опасаясь последствий. Вполне возможно, что определенная эвристика для данной проблемы будет очень хорошо работать, несмотря на то, что она отрицательна. Для вашей конкретной проблемы маловероятно, что что-то подобное происходит (и мне действительно интересно, что он работает так хорошо для вашей проблемы и все еще хочет больше думать о том, почему это может быть).