Безвозвратный поиск. 
Символический искусственный интеллект: математические основы представления знаний

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

Простейшим случаем безвозвратного поиска является стратегия «первый подходящий», описанная в и. 2.1.3. В этом случае поиск ведется вслепую, наудачу, и результат существенным образом зависит от того, в каком порядке перебираются (а значит, и применяются) правила при проверке. Если мы ничего не знаем о задаче, а пространство поиска велико, то не стоит рассчитывать на то, что стратегия «первый подходящий» даст хороший результат.

Так же как и в других случаях, в случае безвозвратного поиска можно ввести оценочную функцию F: D—>M.⁺, где R⁺ — множество неотрицательных вещественных чисел. Запись F (d) — оценка состояния БД d. Функция F подбирается таким образом, чтобы на терминальных узлах (тех состояниях базы, где выполняется условие окончания) функция принимала минимальное значение

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

«первый подходящий», а если оценочная функция подобрана удачно, то такая стратегия будет намного лучше.

Алгоритм 2.3. Стратегия выбора правила «первый подходящий, уменьшающий оценку»

proc Select (d, R) for r e R do.

if r. p (d) & F (r.f (d)) < F (d) then return ®.

end if end for return (nil) end proc.

Можно улучшить процедуру, выбирая такое правило, которое не просто уменьшает оценку, а уменьшает ее в наибольшей степени. Такую стратегию часто называют методом наискорейшего спуска, или градиентным методом, который относится к классу жадных алгоритмов {greedy search). В алгоритме 2.4 представлена простейшая реализация метода наискорейшего спуска.

Алгоритм 2.4. Стратегия выбора правила «наискорейший спуск»

proc Select (d, R) m := F (d) r' := nil for r e R do.

if r. p (d) & F (r.f (d)) < m then.

r' := r.

m := F (r. f (d)).

end if end for return (r') end proc.

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

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

Рассмотрим пример. В случае игры в «восемь» возьмем оценочную функцию F — это число шашек, находящихся не на своем месте. В результате граф поиска этой игры будет выглядеть следующим образом (рис. 2.6).

Рис. 2.6. Оценочная функция F: число шашек не на своем месте Здесь узлы графа обозначают состояния БД, а числа в узлах — это значение оценочной функции в данном состоянии.

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