какую эвристическую функцию оценки или алгоритм можно рассматривать как недопустимую

Question

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

Answer 1

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

h(S) = infinity

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

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

Answer 2

Функция эвристической оценки оценивает стоимость оптимального пути между парой состояний в задаче поиска пути одного агента.

Подробнее о Функция эвристической оценки статья.

Answer 3

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

Википедия имеет хорошее описание