Я встретил термин допустимая эвристика в контексте алгоритма поиска A *. Может ли кто-нибудь объяснить (или дать интуицию), почему эвристическая функция h допустима, только если она не переоценивает фактическое расстояние?Почему допустимая эвристика работает?
Подумайте о состоянии остановки А *, алгоритм останавливается, если он достигает узел цели с определенным F значения, где F равно G - путем, построенного до сих пор от начальной точки плюс эвристического значением H, который представляет собой оценка оставшегося пути к цели.
В узле цели, F равно G как оценка оставшегося пути к цели 0.
условие остановки действует только тогда, когда H допустимо, так как тогда мы можем определить, что если значение F мы вычислили на узле цели меньше любого другого значения F, которое мы вычислили в любом другом узле, мы можем точно определить, что это самый короткий путь, поскольку ни один другой путь не может достичь цели с меньшим значением F.
Если это не допустимо, то может быть какой-то другой узел, для которого мы вычислили F с переоценкой оставшегося пути к цели, и мы не можем остановить алгоритм, поскольку может существовать более короткий путь.
thank u для вашего времени! – ishan3243
Для тех, кто не ищет предоставленные ресурсы бесплатно и без усилий.
В компьютерной науке, в частности, в алгоритмах, связанных с первопрохождение, эвристическая функция называется допустимым, если она никогда не завышает стоимость достижения цели, то есть стоимость он оценок для достижения цели не выше минимально возможного стоимости от текущей точки пути. Допустимая эвристика - , также известная как оптимистическая эвристика.
Это ссылка на Википедию:
http://en.wikipedia.org/wiki/Admissible_heuristic
Эвристический допустимо, если он не переоценивает истинную стоимость, просто потому, что он определил это путь.
ok, вместо того, чтобы быть самоуверенным, вы должны снова прочитать мой вопрос ..... Я прошу интуицию, почему это верно в контексте поиска A *. Википедия не дает никаких аргументов в поддержку этого ... она просто формулирует факты. – ishan3243
@ ishan3243 Чтобы быть справедливым, мое последнее предложение дает единственный правильный ответ на ваш вопрос. Это просто определяется таким образом. – ziggystar
Я так не верю ..... Должна быть причина, почему это так определено. Если вы видите другой ответ, я думаю, что его несколько объяснили. – ishan3243
Вы прочитали статью в Википедии? – ziggystar
Вы понимаете причину, по которой в A * эвристика не должна переоценивать оставшееся расстояние до цели? –
@RonTeller Скажем * should *. – ziggystar