В информатике , особенно в алгоритмах, связанных с поиском пути , эвристическая функция считается допустимой, если она никогда не переоценивает стоимость достижения цели, т. Е. Стоимость, которую она оценивает для достижения цели, не превышает минимально возможную стоимость из текущего точка на пути. [1]
Алгоритмы поиска
Допустимая эвристика используется для оценки стоимости достижения состояния цели в алгоритме информированного поиска . Чтобы эвристика была допустимой для задачи поиска, оценочная стоимость всегда должна быть меньше или равна фактической стоимости достижения целевого состояния. Алгоритм поиска использует допустимую эвристику для нахождения предполагаемого оптимального пути к состоянию цели от текущего узла. Например, в A * найдите функцию оценки (где текущий узел):
где
- = функция оценки.
- = стоимость от начального узла до текущего узла
- = ориентировочная стоимость от текущего узла до цели.
вычисляется с помощью эвристической функции. При недопустимой эвристике алгоритм A * мог упустить из виду оптимальное решение задачи поиска из-за завышенной оценки в.
Формулировка
- это узел
- это эвристический
- Стоимость указана достичь цели из
- оптимальная стоимость достижения цели с
- допустимо, если,
Строительство
Допустимая эвристика может быть получена из упрощенной версии проблемы или на основе информации из баз данных шаблонов, в которых хранятся точные решения подзадач проблемы, или с помощью индуктивных методов обучения .
Примеры
К проблеме пятнадцати головоломок применимы два разных примера допустимой эвристики :
Расстояние Хэмминга - это общее количество потерянных плиток. Ясно, что эта эвристика допустима, поскольку общее количество ходов для правильного упорядочивания плиток равно, по крайней мере, количеству неуместных плиток (каждую неустановленную плитку необходимо переместить хотя бы один раз). Стоимость (количество ходов) до цели (упорядоченной головоломки) равна как минимум расстоянию Хэмминга головоломки.
Манхэттенское расстояние головоломки определяется как:
Рассмотрим головоломку ниже, в которой игрок хочет переместить каждую плитку так, чтобы числа были упорядочены. Расстояние Манхэттена является допустимой эвристикой в этом случае, потому что каждая плитка должна быть перемещена, по крайней мере, на количество точек между ней и ее правильным положением. [2]
4 3 | 6 1 | 3 0 | 8 1 |
7 2 | 12 3 | 9 3 | 14 4 |
15 3 | 13 2 | 1 4 | 5 4 |
2 4 | 10 1 | 11 1 |
Нижние индексы показывают манхэттенское расстояние для каждой плитки. Общее расстояние Манхэттена для показанной головоломки составляет:
Гарантия оптимальности
Если допустимая эвристика используется в алгоритме, который за итерацию обрабатывает только один путь, который имеет наименьшую общую ожидаемую стоимость из нескольких возможных путей, и завершается в момент, когда какой-либо путь достигает цели, принимая этот путь как самый короткий (например, в поиске A * алгоритм ), то этот алгоритм завершится на кратчайшем пути. Чтобы понять, почему, просто представьте, что любой путь, на котором завершается алгоритм, был продвинут только потому, что его общая ожидаемая стоимость была самой низкой из возможных. Для допустимой эвристики ни один из кандидатов не переоценивает свои затраты, поэтому их истинные затраты могут быть только больше или равны стоимости принятого пути. Наконец, общая ожидаемая стоимость - это истинная стоимость пути, который достигает цели, потому что единственная допустимая эвристика при достижении цели равна нулю.
В качестве примера [3] того, почему допустимость может гарантировать оптимальность, предположим, что у нас есть следующие затраты: (стоимость выше / ниже узла - это эвристика, стоимость на границе - это фактическая стоимость)
0 10 0100 0НАЧАЛО ---- O ----- ЦЕЛЬ | |0 | | 100 | | О ------- О ------ О100 1 100 1 100
Итак, очевидно, что мы должны начать с посещения верхнего среднего узла, поскольку ожидаемая общая стоимость, т. Е. , является . Тогда целью был бы кандидат с равно . Затем мы явно выбираем нижние узлы один за другим, а затем обновленную цель, поскольку все они имеют ниже, чем текущей цели, т.е. их является . Таким образом, даже несмотря на то, что цель была кандидатом, мы не могли выбрать ее, потому что были еще пути получше. Таким образом, допустимая эвристика может гарантировать оптимальность.
Однако обратите внимание, что, хотя допустимая эвристика может гарантировать окончательную оптимальность, она не обязательно эффективна.
Заметки
Хотя все согласованные эвристики допустимы, не все допустимые эвристики согласованы.
Для задач поиска в дереве, если используется допустимая эвристика, алгоритм поиска A * никогда не вернет неоптимальный целевой узел.
Рекомендации
- ^ Рассел, SJ; Норвиг П. (2002). Искусственный интеллект: современный подход . Прентис Холл. ISBN 0-13-790395-2.
- ^ Корф, Ричард Э. (2000), «Недавний прогресс в разработке и анализе допустимых эвристических функций» (PDF) , в Choueiry, Berthe Y .; Уолш, Тоби (ред.), Абстракция, переформулирование и приближение: 4-й Международный симпозиум, SARA 2000 Horseshoe Bay, США, 26-29 июля 2000 г. Proceedings , 1864 , Springer, стр. 45–55, CiteSeerX 10.1.1.124.817 , DOI : 10.1007 / 3-540-44914-0_3 , ISBN 978-3-540-67839-7, дата обращения 26.04.2010
- ^ «Почему допустимая [ sic ] эвристика гарантирует оптимальность?» . алгоритм. Переполнение стека . Проверено 11 декабря 2018 .