В чем разница между монотонностью и допустимостью эвристики?

Я читаю мой учебник по ИИ, и мне интересно, какая разница между монотонностью и допустимостью эвристики (я знаю, что они не являются взаимоисключающими).

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

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

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

Ответ 1

Russel and Norvig, 2ed page 99:

Второе решение состоит в том, чтобы гарантировать, что оптимальный путь к любому повторному состоянию всегда является первым, за которым следует - как в случае с обычным поиском. Это свойство выполняется, если мы накладываем дополнительное требование на h(n), а именно требование согласованности (также называемое монотонностью).

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

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

Ответ 2

Допустимость:

Алгоритм поиска допустим, если гарантировано найти минимальный путь к решению всякий раз, когда такое решение существует. Первый поиск по ширине допустим, поскольку он рассматривает каждое состояние на уровне n перед рассмотрением любого состояния на уровне n + 1.

Монотонность: Это свойство запрашивает, является ли алгоритм локально допустимым, т.е. Он всегда недооценивает стоимость между любыми двумя состояниями в пространстве поиска. Напомним, что A * не требует, чтобы g (n) = g * (n). Эвристическая функция h является монотонной, если: 1. Для всех состояний ni и nj, где nj является потомком ni, h (ni) - h (nj) <= cost (ni, nj).

2. Эвристическая оценка состояния цели равна 0: h (Цель) = 0.

Ответ 3

Монотонное обучение - это когда агент не может изучать какие-либо знания, которые противоречат тому, что он уже знает. Например, он не может заменить выражение своим отрицанием. Таким образом, база знаний может только расти с новыми фактами монотонно. Преимущества монотонного обучения:

1. значительно упрощенное обслуживание правды

выбор 2.greater в стратегиях обучения

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

1.Подробная применимость к реальным доменам,

2. более высокая свобода в порядке вещей, которые изучаются в

Связанное свойство - это согласованность знания. Если архитектура должна поддерживать согласованную базу знаний, то любая стратегия обучения, которую она использует, должна быть монотонной.