Допустимая эвристика

Концепция поиска путей информатики

В информатике , особенно в алгоритмах , связанных с поиском пути , эвристическая функция считается допустимой , если она никогда не переоценивает стоимость достижения цели, т. е. оцениваемая ею стоимость достижения цели не превышает минимально возможной стоимости от текущей точка на пути. ^[1]

Это связано с концепцией непротиворечивой эвристики . Хотя все непротиворечивые эвристики допустимы, не все допустимые эвристики непротиворечивы.

Алгоритмы поиска

Допустимая эвристика используется для оценки стоимости достижения целевого состояния в алгоритме информированного поиска . Чтобы эвристика была приемлемой для задачи поиска, предполагаемая стоимость всегда должна быть ниже или равна фактической стоимости достижения целевого состояния. Алгоритм поиска использует допустимую эвристику для нахождения предполагаемого оптимального пути к целевому состоянию от текущего узла. Например, в поиске A* функция оценки (где находится текущий узел): ${\displaystyle n}$

${\displaystyle f(n)=g(n)+h(n)}$

где

${\displaystyle f(n)}$= функция оценки.

${\displaystyle g(n)}$= стоимость от начального узла до текущего узла

${\displaystyle h(n)}$= предполагаемая стоимость от текущего узла до цели.

${\displaystyle h(n)}$рассчитывается с помощью эвристической функции. При недопустимой эвристике алгоритм A* может пропустить оптимальное решение задачи поиска из-за завышения . ${\displaystyle f(n)}$

Формулировка

${\displaystyle n}$это узел

${\displaystyle h}$это эвристика

${\displaystyle h(n)}$обозначается стоимость достижения цели от ${\displaystyle h}$ ${\displaystyle n}$

${\displaystyle h^{*}(n)}$оптимальная стоимость достижения цели из ${\displaystyle n}$

${\displaystyle h(n)}$допустимо, если ${\displaystyle \forall n}$

${\displaystyle h(n)\leq h^{*}(n)}$

Строительство

Допустимая эвристика может быть получена на основе смягченной версии задачи или на основе информации из баз данных шаблонов, в которых хранятся точные решения подзадач задачи, или с использованием методов индуктивного обучения .

Примеры

К задаче « Пятнадцать головоломок» применимы два разных примера допустимых эвристик :

• Расстояние Хэмминга
• Расстояние Манхэттен

Расстояние Хэмминга — это общее количество неправильно размещенных плиток. Ясно, что эта эвристика допустима, поскольку общее количество ходов для правильного упорядочивания плиток не меньше количества неправильно расположенных плиток (каждую не стоящую на месте плитку необходимо переместить хотя бы один раз). Стоимость (количество ходов) достижения цели (упорядоченной головоломки) равна как минимум расстоянию Хэмминга головоломки.

Манхэттенское расстояние головоломки определяется как:

${\displaystyle h(n)=\sum _{\text{all tiles}}{\mathit {distance}}({\text{tile, correct position}})}$

Рассмотрим головоломку ниже, в которой игрок хочет переместить каждую плитку так, чтобы числа были упорядочены. Манхэттенское расстояние в данном случае является допустимой эвристикой, потому что каждую плитку придется переместить как минимум на количество мест между ней и ее правильным положением. ^[2]

Нижние индексы показывают расстояние Манхэттена для каждой плитки. Общее расстояние Манхэттена для показанной головоломки составляет:

${\displaystyle h(n)=3+1+0+1+2+3+3+4+3+2+4+4+4+1+1=36}$

Доказательство оптимальности

Если допустимая эвристика используется в алгоритме, который на итерации продвигается только по пути с наименьшей оценкой (текущая стоимость + эвристика) из нескольких путей-кандидатов, завершается в тот момент, когда его исследование достигает цели, и, что особенно важно, никогда не закрывает все оптимальные пути раньше завершение (что возможно с алгоритмом поиска A*, если не принять особых мер ^[3] ), то этот алгоритм может завершиться только на оптимальном пути. Чтобы понять почему, рассмотрим следующее доказательство от противного :

Предположим, что такому алгоритму удалось завершиться на пути T с истинной стоимостью T _true, большей, чем оптимальный путь S с истинной стоимостью S _true . Это означает, что перед завершением оценочная стоимость T была меньше или равна оценочной стоимости S (в противном случае S был бы выбран). Обозначим эти оцененные затраты T _eval и S _eval соответственно. Вышеизложенное можно резюмировать следующим образом:

S _верно < T _верно

T _eval ≤ S _eval

Если наша эвристика допустима, из этого следует, что на этом предпоследнем шаге T _eval = T _{истинно} , поскольку любое увеличение истинной стоимости за счет эвристики на T было бы недопустимым, и эвристика не может быть отрицательной. С другой стороны, допустимая эвристика потребует, чтобы S _eval ≤ S _true , что в сочетании с приведенными выше неравенствами дает нам T _eval < T _true и, более конкретно, T _eval ≠ T _true . Поскольку T _eval и T _true не могут быть одновременно равными и неравными, наше предположение должно быть ложным, и поэтому должно быть невозможно завершить процесс на более затратном, чем оптимальный, пути.

В качестве примера ^[4] предположим, что у нас есть следующие затраты: (стоимость выше/ниже узла — это эвристика, стоимость на краю — это фактическая стоимость)

0 10 0 100 0СТАРТ ---- O ----- ЦЕЛЬ | |0| |100 | | О ------- О ------ О100 1 100 1 100

Итак, очевидно, что мы начнем с посещения верхнего среднего узла, поскольку ожидаемая общая стоимость, т. е. равна . Тогда целью будет кандидат с равным . Тогда мы явно выбрали бы нижние узлы один за другим, а затем обновленную цель, поскольку все они имеют значение ниже текущей цели, т. е. их значение равно . Таким образом, даже несмотря на то, что цель была кандидатом, мы не могли выбрать ее, потому что существовали пути получше. Таким образом, допустимая эвристика может обеспечить оптимальность. ${\displaystyle f(n)}$ ${\displaystyle 10+0=10}$ ${\displaystyle f(n)}$ ${\displaystyle 10+100+0=110}$ ${\displaystyle f(n)}$ ${\displaystyle f(n)}$ ${\displaystyle f(n)}$ ${\displaystyle 100,101,102,102}$

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

Рекомендации

1. Рассел, SJ; Норвиг, П. (2002). Искусственный интеллект: современный подход . Прентис Холл. ISBN 0-13-790395-2.
2. Корф, Ричард Э. (2000), «Последний прогресс в разработке и анализе допустимых эвристических функций» (PDF) , в Шуэйри, Берта Ю.; Уолш, Тоби (ред.), Абстракция, переформулировка и аппроксимация: 4-й международный симпозиум, SARA 2000, Хорсшу-Бэй, США, 26–29 июля 2000 г., материалы , том. 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 апреля 2010 г.
3. Холте, Роберт (2005). «Распространенные заблуждения относительно эвристического поиска». Материалы третьего ежегодного симпозиума по комбинаторному поиску (SoCS) . Архивировано из оригинала 01 августа 2022 г. Проверено 10 июля 2021 г.
4. «Почему допустимые [sic] эвристики гарантируют оптимальность?» алгоритм. Переполнение стека . Проверено 11 декабря 2018 г.

Смотрите также

• Последовательная эвристика
• Эвристическая функция
• Алгоритм поиска