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

Ответ 1

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

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

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

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

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

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

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

Ответ 2

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