Согласованная эвристика

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

Формально для каждого узла N и каждого преемника P из N оценочная стоимость достижения цели из N не превышает стоимость шага перехода к P плюс оценочная стоимость достижение цели из P. То есть:

$h\; (N)\; \le \; c\; (N,\; P)\; +\; h\; (P)\; \{\backslash \; displaystyle\; h\; (N)\; \backslash \; leq\; c\; (N,\; P)\; +\; h\; (P)\}$и

$h\; (G)\; =\; 0.\; \{\backslash \; displaystyle\; h\; (G)\; =\; 0.\; \backslash ,\}$

где

• h - согласованная эвристическая функция
• N - любой узел в графе
• P является любым потомком N
• G является любым целевым узлом
• c (N, P) - это стоимость достижения узла P из N

Последовательная эвристика также допустима, т. Е. Она никогда не переоценивает стоимость достижения цели (обратное, однако, не всегда верно). Это доказывается индукцией по $m\; \{\backslash \; displaystyle\; m\}$, длине наилучшего пути от узла к цели. По предположению $час\; (N\; m)\; \le \; h\; \ast \; (N\; m)\; \{\backslash \; displaystyle\; h\; (N\_\; \{m\})\; \backslash \; leq\; h\; ^\; \{*\}\; (N\_\; \{m\})\}$, где $h\; \ast \; (n)\; \{\backslash \; displaystyle\; h\; ^\; \{*\}\; (n)\}$обозначает стоимость кратчайшего пути от n до цели. Следовательно,

$h\; (N\; m\; +\; 1)\; \le \; c\; (N\; m\; +\; 1,\; N\; m)\; +\; h\; (N\; m)\; \le \; c\; (N\; m\; +\; 1,\; N\; m)\; +\; h\; \ast \; (N\; m)\; =\; h\; \ast .\; (N\; m\; +\; 1)\; \{\backslash \; displaystyle\; h\; (N\_\; \{m\; +\; 1\})\; \backslash \; leq\; c\; (N\_\; \{m\; +\; 1\},\; N\_\; \{m\})\; +\; h\; (N\_\; \{m\})\; \backslash \; leq\; c\; (N\_\; \{m\; +\; 1\},\; N\_\; \{m\})\; +\; h\; ^\; \{*\}\; (N\_\; \{m\})\; =\; h\; ^\; \{*\}\; (N\_\; \{m\; +\; 1\})\}$,

, что делает его допустимым. ($N\; m\; +\; 1\; \{\backslash \; displaystyle\; N\_\; \{m\; +\; 1\}\}$- любой узел, лучший путь которого к цели длиной m + 1 проходит через некоторый непосредственный дочерний элемент $N\; m\; \{\backslash \; displaystyle\; N\_\; \{m\}\}$, наилучший путь которого к цели имеет длину m.)

.

Сравнение допустимой, но непоследовательной функции эвристической оценки.

Согласованная эвристика называется монотонной, потому что оценочная окончательная стоимость частичного решения, $f\; (N\; j)\; =\; g\; (N\; j)\; +\; h\; (N\; j)\; \{\backslash \; displaystyle\; f\; (N\_\; \{j\})\; =\; g\; (N\_\; \{j\})\; +\; h\; (N\_\; \{j\})\}$монотонно неубывает по лучшему пути к цели, где $g\; (N\; j)\; =\; \sum \; i\; =\; 2\; jc\; (N\; i\; -\; 1,\; N\; i)\; \{\backslash \; displaystyle\; g\; (N\_\; \{j\})\; =\; \backslash \; sum\; \_\; \{i\; =\; 2\}\; ^\; \{j\}\; c\; (N\_\; \{i-1\},\; N\_\; \{i\})\}$- стоимость наилучшего пути от начального узла $N\; 1\; \{\backslash \; displaystyle\; N\_\; \{1\}\}$до $N\; j\; \{\backslash \; displaystyle\; N\_\; \{j\}\}$. Это необходимо и достаточно, чтобы эвристика подчинялась неравенству треугольника , чтобы быть согласованной.

В алгоритме поиска A * использование согласованной эвристики означает, что однажды узел расширяется, стоимость, с которой он был достигнут, является минимально возможной, при тех же условиях, которые требует алгоритм Дейкстры при решении задачи о кратчайшем пути (без циклов с отрицательной стоимостью). Фактически, если для поискового графа задана стоимость $c\; \text{'}(N,\; P)\; =\; c\; (N,\; P)\; +\; h\; (P)\; -\; h\; (N)\; \{\backslash \; displaystyle\; c\text{'}\; (N,\; P)\; =\; c\; (\; N,\; P)\; +\; h\; (P)\; -h\; (N)\}$для согласованного $h\; \{\backslash \; displaystyle\; h\}$, тогда A * эквивалентно поиску по первому наилучшему на этом графе с использованием алгоритма Дейкстры. В необычном случае, когда допустимая эвристика несовместима, узел будет нуждаться в повторном расширении каждый раз, когда для него будет достигнута новая лучшая (на данный момент) стоимость.

Если данная эвристика $h\; \{\backslash \; displaystyle\; h\}$допустима, но не согласована, можно искусственно заставить эвристические значения вдоль пути быть монотонно неубывающими, используя

$h\; \prime \; (P)\; \leftarrow \; max\; (h\; (P),\; h\; \prime \; (N)\; -\; c\; (N,\; P))\; \{\backslash \; displaystyle\; h\; \text{'}(P)\; \backslash \; gets\; \backslash \; max\; (h\; (P),\; h\text{'}\; (N)\; -c\; (N,\; P))\}$

в качестве эвристического значения для $P\; \{\backslash \; displaystyle\; P\}$вместо $h\; (P)\; \{\backslash \; displaystyle\; h\; (P)\}$, где $N\; \{\backslash \; displaystyle\; N\}$- это узел, непосредственно предшествующий $P\; \{\backslash \; displaystyle\; P\}$на пути, а $ч\; \text{'}(начало)\; =\; ч\; (начало)\; \{\backslash \; Displaystyle\; ч\text{'}\; (начало)\; =\; ч\; (начало)\}$. Эта идея принадлежит Ласло Меро и теперь известна как pathmax. Вопреки распространенному мнению, pathmax не превращает допустимую эвристику в последовательную эвристику. Например, если A * использует pathmax и эвристику, которая допустима, но не согласована, не гарантируется наличие оптимального пути к узлу при первом расширении.

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

1. ^Перл, Иудея (1984). Эвристика: стратегии интеллектуального поиска для решения компьютерных проблем. Эддисон-Уэсли. ISBN 0-201-05594-5.
2. ^Эделькамп, Стефан; Шредль, Стефан (2012). Эвристический поиск: теория и приложения. Морган Кауфманн. ISBN 978-0-12-372512-7.
3. ^Меро, Ласло (1984). «Алгоритм эвристического поиска с изменяемой оценкой». Искусственный интеллект. 23 : 13–27. DOI : 10.1016 / 0004-3702 (84) 90003-1.
4. ^Холте, Роберт (2005). «Распространенные заблуждения относительно эвристического поиска». Материалы третьего ежегодного симпозиума по комбинаторному поиску (SoCS).