Если у вас есть набор допустимых эвристики: h1,h2,h2,...,hnКакова максимальная допустимая эвристика, доминирующая эвристика?
Как это h = max(h1,h2,h2,...,hn) допустимый эвристический, которая доминирует их всех?
Не более ли значение h (n) лучше?
Для A *, f = g + n, а элемент с наименьшим значением f будет удален из списка. Так что не стоит брать min, чтобы доминировать в эвристике?
Допустимая эвристика никогда не переоценивает стоимость достижения цели. То есть его оценка будет ниже фактической стоимости или точно фактической стоимости, но не выше. Это необходимо для жадных подходов, таких как поиск A *, чтобы найти глобальное лучшее решение.
Например, представьте, что вы нашли решение со стоимостью 10. Лучшее решение имеет стоимость 8. Вы не используете допустимую эвристику, а оценка эвристики для решения, которая действительно стоит 8, равна 12 (это переоценивать). Поскольку у вас уже есть решение со стоимостью 10, A * никогда не будет оценивать лучшее решение, поскольку оно, по оценкам, будет более дорогостоящим.
В идеале ваша эвристика должна быть максимально точной, то есть допустимая эвристика не должна слишком сильно недооценивать истинную стоимость. Если это произойдет, A * все равно найдет наилучшее решение в конце концов, но для этого может потребоваться намного больше времени, потому что он пытается найти множество решений, которые выглядят хорошо в соответствии с вашей эвристикой, но оказываются плохими.
Это ответ на ваш вопрос. Все эвристики h1, ..., hn допустимы, поэтому они оценивают стоимость, равную или меньшую, чем истинная стоимость. Поэтому максимум этого набора оценок является, по определению, оценкой ближайшим к фактической стоимости (помните, что вы никогда не будете переоценивать). В идеальном случае это будет точная стоимость.
Если вы должны были принять минимальное значение, вы получите в итоге от от фактической стоимости - как указано выше, A * все равно найдет лучшее решение, но в гораздо меньшей степени эффективным способом.