Допустимая эвристическая функция

Question

Я знаю, что допустимая эвристическая функция недооценивает фактическую стоимость цели, но я хочу заключить, что эвристическая функция h3, являющаяся суммой двух допустимых эвристических функций (h1 и h2), может быть допустимой, а не если дополнительная информация о h1 и h2 не указана. Считаете ли вы, что это правильное требование?

Благодаря

Answer 1

Допустимая эвристика один, который никогда не переоценивает стоимость минимальной стоимости пути от узла к узлу цели. Таким образом, эвристика специфична для определенного пространства состояний, а также для конкретного состояния цели в этом пространстве состояний. Он должен быть допустимым для всех состояний в этом пространстве поиска. Чтобы помнить, «никогда не переоценивает» или «никогда недооценивает», просто помните, что допустимая эвристика слишком оптимистична. Это приведет к тому, что A * будет искать пути, которые оказались бы более дорогими, чем оптимальный путь. Это не помешает A * расширять узел, который находится на оптимальном пути, создавая слишком высокое эвристическое значение h. Более сильное требование к эвристике состоит в том, что оно последовательное, иногда называемое монотонным. Эвристика h согласована, если ее значение не убывает вдоль пути. Математически эвристика h согласована, если для каждого узла n родительского узла p,

Answer 2

Я думаю, что исходный вопрос еще не ответил - также не в комментариях к предыдущему ответу.

Если h1 и h2 допустимы, то h3 = h1 + h2 вообще НЕ допустимо, хотя это может случиться в особых случаях (т. Е. Нулевая эвристика допустима и может быть добавлена ​​к другой эвристике произвольно много раз, не нарушая допустимость). Это очень легко увидеть. Представьте себе проблему, когда все состояния являются либо целевыми состояниями, либо они могут быть превращены в состояние цели только с одним действием стоимости 1. Таким образом, допустима любая эвристика, которая возвращает 0 для состояния цели и 1 для состояния без цели. Пусть s - состояние без цели. Тогда допустимы h1 (s) = h2 (s) = 1, но h3 (s) = 2 нет.

Конечно, допустимая допустимая эвристика допустима (это также очень легко увидеть), поэтому h3 = max (h1, h2) будет доминировать над h1 и h2 (то есть, по крайней мере, так же хорошо, как и любой из них) и все еще допустимы.

Существуют более сложные способы, чем просто принятие максимальной допустимой эвристики, чтобы объединить их в более точный. Наиболее известный метод, который я знаю называется стоимость перегородки: При обеспечении того, чтобы никакое действие не может внести свой вклад в расходы как h1 и h2, это безопасно добавить их значения. Основная идея использовать это (я думаю, проверьте это самостоятельно!), Создав n проблемных экземпляров исходной проблемы (при использовании n эвристик), и убедитесь, что всякий раз, когда действие имеет первоначальную стоимость m проблема номер я (который используется для эвристического числа я), то, что само действие стоило во всех других п-1 проблем. Таким образом, все проблемы/эвристика все еще имеют все доступные действия, в то время как суммирование их стоимости гарантировано не переоценивается, то есть допустимо (при условии, что все эвристики допустимы). Я думаю, что статья «Оптимальный допустимый состав эвристики абстракции» (http://www.sciencedirect.com/science/article/pii/S0004370210000652) подробно объясняет эту идею.