При изучении путей ознакомительных проблем в области искусственного интеллекта , эвристическая функция называется последовательными , или монотонным , если его оценка всегда меньше или равна расчетное расстояние от любой соседней вершины до цели, плюс стоимость достижения этот сосед.
Формально, для каждого узла N и каждый преемник P из N , предполагаемая стоимость достижения цели из N не больше , чем на этапе стоимость получения до P плюс предполагаемой стоимость достижения цели из P . Это:
- а также
где
- h - последовательная эвристическая функция
- N - любой узел в графе
- P - любой потомок N
- G - любой целевой узел
- c (N, P) - стоимость достижения узла P из N
Неформально каждый узел i будет давать оценку, которая с учетом стоимости достижения следующего узла всегда меньше оценки в узле i + 1 .
Последовательная эвристика также допустима , т. Е. Она никогда не переоценивает стоимость достижения цели ( обратное , однако, не всегда верно). Это доказывается по индукции .
Позволять - оценочная стоимость целевого узла. Отсюда следует, что базовое условие тривиально выполняется при 0 ≤ 0. Поскольку эвристика согласована,. Приведенные сроки равны истинной стоимости,, поэтому любая последовательная эвристика также допустима, поскольку она ограничена сверху истинной стоимостью.
Обратное явно неверно, поскольку мы всегда можем построить эвристику, которая всегда ниже истинной стоимости, но, тем не менее, несовместима, например, путем увеличения эвристической оценки от самого дальнего узла по мере приближения и, когда оценка становится в лучшем случае истинной стоимостью , мы делаем .
Последствия монотонности
Согласованные эвристики называются монотонными, потому что предполагаемая окончательная стоимость частичного решения монотонно не убывает по лучшему пути к цели, где это стоимость наилучшего пути от начального узла к . Это необходимо и достаточно, чтобы эвристика подчинялась неравенству треугольника , чтобы быть последовательной. [1]
В алгоритме поиска A * использование последовательной эвристики означает, что после расширения узла стоимость, с которой он был достигнут, является минимально возможной при тех же условиях, которые алгоритм Дейкстры требует при решении задачи кратчайшего пути (отсутствие циклов с отрицательной стоимостью ). Фактически, если в графе поиска задана стоимость для последовательного , то A * эквивалентен поиску лучшего первого на этом графе с использованием алгоритма Дейкстры. [2] В необычном случае, когда допустимая эвристика несовместима, узел будет нуждаться в повторном расширении каждый раз, когда для него будет достигнута новая лучшая (на данный момент) стоимость.
Если данная эвристика допустимо, но не согласованно, можно искусственно заставить эвристические значения вдоль пути быть монотонно неубывающими, используя
как эвристическое значение для вместо , где узел, непосредственно предшествующий на пути и . Эта идея принадлежит Ласло Меро [3] и теперь известна как pathmax. Вопреки распространенному мнению, pathmax не превращает допустимую эвристику в последовательную эвристику. Например, если A * использует pathmax и эвристику, которая допустима, но не согласована, не гарантируется наличие оптимального пути к узлу при его первом раскрытии. [4]
Смотрите также
Рекомендации
- ↑ Жемчужина, Иудея (1984). Эвристика: стратегии интеллектуального поиска для решения компьютерных проблем . Эддисон-Уэсли. ISBN 0-201-05594-5.
- ^ Эделькамп, Стефан; Шредль, Стефан (2012). Эвристический поиск: теория и приложения . Морган Кауфманн. ISBN 978-0-12-372512-7.
- ^ Меро, Ласло (1984). «Алгоритм эвристического поиска с изменяемой оценкой». Искусственный интеллект . 23 : 13–27. DOI : 10.1016 / 0004-3702 (84) 90003-1 .
- ^ Холте, Роберт (2005). «Распространенные заблуждения относительно эвристического поиска» . Материалы третьего ежегодного симпозиума по комбинаторному поиску (SoCS) .