Что означает, что эвристика считается приемлемой?

Question

Мне сказали, что допустимая эвристика для алгоритма поиска - это тот, который никогда не переоценивает кратчайший путь к цели. Однако справедливо ли иметь, что узлы состояния без цели имеют эвристическое значение 0 или является их дополнительным правилом допустимости, которое также утверждает, что только целевые состояния могут иметь эвристическое значение 0?

Например, кратчайший путь между узлом и целью государственного D выглядит следующим образом:

A = 5 
B = 4 
C = 3 
D = 0 

ли следующее эвристический быть действительным:

A = 4 
B = 4 
C = 0 
D = 0 

ли эта эвристика также может быть действительной (в то время также бесполезно)

A = 0 
B = 0 
C = 0 
D = 0 

Answer 1

Допустимая эвристика - это просто та, которая, как вы сказали, не переоценить расстояние до цели. Допускается недооценить, и два приведенных вами примера действительно являются допустимыми эвристиками.

Как правило, в тех алгоритмах, которые мы обсуждаем с помощью этих эвристик (например, A *), полезно, если эвристика максимально приближена к истине. Итак, как вы уже заметили себя, последний пример с эвристическими значениями 0 для всех узлов был бы не очень полезен. Как правило, вы хотите, чтобы ваши эвристические значения были как можно ближе к истине, хотя и допустимы (удостоверяются, что они никогда не переоценить)