какую эвристическую функцию оценки или алгоритм можно считать недопустимой
Я изучил несколько эвристических функций, которые допустимы для решения классической задачи 8 головоломок, и я знаю, что вы можете умножить множитель на допустимую функцию, чтобы сделать ее недопустимой, однако мне интересно, есть ли другая недопустимая эвристическая функция для задачи 8 головоломок?
3 ответа:
В этой головоломке есть всевозможные недопустимые эвристики. Недопустимая эвристика просто должна переоценивать количество шагов, которые она примет для решения данной головоломки, и поэтому одна простая недопустимая эвристика будет
Поскольку любая разрешимая головоломка может быть решена менее чем за бесконечность шагов, эвристика недопустима.h(S) = infinityГораздо сложнее и интереснее было бы спросить, какие хорошие допустимые эвристики существуют, поскольку они требуйте, чтобы вы дали максимально возможное значение, которое вы можете, чтобы не переоценивать расстояние. На это у меня нет хорошего ответа. :- )
Эвристическая функция оценки оценивает стоимость оптимального пути между парой состояний в задаче поиска пути с одним агентом.
Подробнее читайте в статье эвристическая функция оценки.
В принципе, любая функция, которая завышает стоимость, недопустима, что означает, что построение недопустимых функций легко.
Википедия имеет хорошее описание