При изучении задач поиска пути в искусственном интеллекте эвристическая функция называется последовательной или монотонной, если ее оценка всегда меньше или равна расчетному расстоянию от любого соседнего объекта. вершины к цели плюс стоимость достижения этого соседа.
Как сделать эвристику последовательной?
Эвристика непротиворечивости
- Последовательная эвристика: для каждой вершины n и каждого преемника n' из n, порожденного любым действием a: h(n) ≤ c(n, a, n') + h(n')
- Требуется только для приложений A для поиска по графу.
Является ли 0 последовательной эвристикой?
"Для любого пространства поиска всегда существует допустимая и непротиворечивая эвристика A". Ну, я знаю, что всегда есть допустимая эвристика, например ноль, так как это занижение реальной стоимости (хотя это привело бы к равномерной стоимости вместо).
Может ли эвристика быть последовательной и недопустимой?
Примечания. Хотя все непротиворечивые эвристики допустимы, не все допустимые эвристики непротиворечивы. Для задач поиска по дереву, если используется допустимая эвристика, алгоритм поиска A никогда не вернет субоптимальный целевой узел.
Подразумевает ли допустимость согласованность?
1 Ответ. Если вы не делаете что-то очень необычное, допустимая эвристика также будет последовательной. На самом деле проблема понять разницу, и почемунеобходима последовательность, заключается в том, что придумывать примеры нетривиально.
