Согласованная и допустимая эвристика

Question

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

Просьба привести пример, в котором это так.

Answer 1

Как и в Расселе и Норвиге в Искусственный интеллект: современный подход (наиболее часто используемый учебник по ИИ) сложно выдвинуть эвристику, допустимую, но не последовательную.

Очевидно, что вы можете выбрать значения для узлов в графе, чтобы эвристика, которую они представляют, допустима, но не последовательна. This paper by Felner et al имеет хороший пример двух способов, что это возможно, но это немного плотная, так что я буду резюмировать:

• Эта эвристика противоречива в c1, поскольку он дает более низкий (т.е. менее информативная) нижняя граница стоимости для достижения цели, чем ее родительский узел. Смета расходов на достижение цели через родительский узел составляет не менее 10 (поскольку стоимость пути до p равна 5, а эвристическая оценка в p также равна 5). Однако оценка стоимости для достижения цели через c1 составляет всего 8 (стоимость родительского (5), плюс стоимость пути от родителя (1) плюс эвристическая оценка по c1 (2)).
• Поскольку этот график неориентирован, эта эвристика также противоречива на c2, потому что переход от c2 к p имеет ту же проблему, что и выше.

Felner et al также предоставляют несколько конкретных примеров допустимой, но непоследовательной эвристики. Рассмотрим задачу 8-головоломка:

В этой головоломке есть 8 раздвижные плитки пронумерованных 1-8, и один пустое пространство. Плитки начинают из строя (как на изображении слева). Цель состоит в том, чтобы получить головоломку в состояние, показанное выше справа, исключительно путем перемещения плитки в пустое пространство. Классическая эвристика для этой проблемы (расстояние Манхэттена каждой плитки до места, где она должна быть) допустима и последовательна.

Однако, вы можете придумать другую эвристику. Возможно, вы просто хотите посмотреть расстояние Манхэттена (то есть количество квадратов) от 1, 2 и 3 до мест, где они должны находиться в состоянии цели. Эвристический, хотя и менее информативный, чем манхэттенский расклад всех плиток, по-прежнему допустим и последователен.

Но скажем, что вы выбираете дополнительную группу квадратов, возможно, 5, 6 и 7. И тогда скажем, что способ вычисления эвристики на каждом узле случайным образом выбирает одно из этих множеств (1,2 , 3) или (5, 6 и 7) и вычисляя их расстояние в Манхэттене до их местоположений цели. Эта эвристика все еще допустима - она ​​может только недооценивать или сопоставлять количество ходов, необходимых для достижения цели. Тем не менее, более несовместим - между эвристическими оценками на каждом узле нет четкой связи.

Answer 2

Долгожитель, но я дам свои два цента в любом случае.Я думаю, что самый простой способ подумать об этом заключается в том, что допустимая эвристика говорит, что вы не можете перерегулировать себя, когда попадаете на определенный определенный узел цели, в то время как последовательная эвристика говорит, что вы не можете перерегулировать себя, когда попадаете в ЛЮБОЙ узел. Это делает отношения понятными: поскольку узлом цели является некоторый узел, допустимая эвристика допустима. Но так как допустимое только гарантирует это свойство для одного узла, допустимое не означает согласованности.