Эвристический поиск
Отсюда следует, что если h(n) – нижняя оценка действительного расстояния до целевого состояния, т.е. если h(n) никогда не дает завышенной оценки расстояния, то алгоритм А всегда отыщет оптимальный путь до цели при помощи оценочной функции f(n). Алгоритм, обладающий таким свойством, называется разрешимым (более подробное обсуждение этого вопроса читатель найдет в специальной литературе, в частности в работах Нмпьсона [Nilsson, 1980, Chapter 2] и Перла [Pearl, 1984, Chapter 2]).
Обозначения:
- s – узел начального состояния;
- g – узел целевого состояния;
- OPEN – список, который содержит,выбранные, но необработанные узлы;
- CLOSED – список, который содержит обработанные узлы.
Алгоритм:
- (1) OPEN: = {s}.
- (2) Если ОРЕМ: = {}, то прекратить выполнение. Пути к целевому состоянию на графе не существует.
- (3) Удалить из списка OPEN узел п, для которого f(n)<f(m) для любого узла m, уже присутствующего в списке OPEN, и перенести его в список CLOSED.
- (4) Сформировать список очередных узлов, в который возможен переход из узла n и удалить из него все узлы, образующие петли; с каждым из оставшихся связать указатель на узел n.
- (5) Если в сформированном списке очередных узлов присутствует g, то завершить выполнение. Сформировать результат – путь, порожденный прослеживанием указателей от узла g до узла s.
- (6) В противном случае для каждого очередного узла n', включенного в список, выполнить следующую последовательность операций:
- Вычислить f(n').
- Если n не присутствует ни в списке OPEN, ни в списке CLOSED, добавить его в список, присоединить к нему оценку f(n') и установить обратный указатель на узел n.
- Если n' уже присутствует в списке OPEN или в списке CLOSED, сравнить новое значение f(n)=new с прежним f(n')=old.
- Если old<new, прекратить обработку нового узла.
- Если new<old, заменить новым узлом прежний в списке, причем, если прежний узел был в списке CLOSED, перенести его в список OPEN.
Конец алгоритма.
Применение этого алгоритма рассмотрено в упр. 8.
Вычислительная мощность современных компьютеров все-таки недостаточна для того, чтобы использовать алгоритмы поиска решений даже с помощью направленного поиска с применением оценочной функции, не говоря уже о методике слепого перебора возможных состояний. Пространство состояний, в котором нужно вести поиск, при решении таких задач, как распознавание речи, выбор конфигурации компьютерной системы или планирование последовательности операций, настолько велико, что его невозможно проанализировать такими обобщенными методами за обозримый отрезок времени, если только не призвать на помощь знания, касающиеся конкретной предметной области.
Можно показать, что многие из этих проблем изоморфны абстрактным задачам, которые заведомо относятся к классу "необозримых" в том смысле, что их сложность, а соответственно и потребность в вычислительных ресурсах, экспоненциально возрастает при линейном увеличении размерности задачи.
Как будет показано далее, развитие экспертных систем пошло по пути привлечения опыта экспертов, как касающегося деталей поведения конкретных объектов в конкретной ситуации, так и стратегии логического вывода в определенной предметной области, что и позволяет преодолеть трудности, связанные со сложностью формализованного поиска в пространстве состояний.
Достаточно подробно результаты первых исследований в области программирования игр и машинного доказательства теорем описаны в сборнике статей под редакцией Фейгенбаума и Фельдмана [Feigenbaum and Feldman, 1963]. Я склонен к тому, чтобы считать "классическим" в истории искусственного интеллекта период, который начался с публикации в 1950 году статьи Шеннона об игре в шахматы [Shannon, 1950] и закончился выходом сборника Фейгенбаума и Фельдмана. Наиболее существенные результаты, полученные в этот период, можно сформулировать следующим образом:
- проблему любой сложности, в принципе, можно свести к проблеме поиска в пространстве состояний, если только удается ее формализовать в терминах начального состояния, конечного состояния и операций перехода в пространстве состояний;
- поиск в пространстве состояний должен направляться определенным образом представленными знаниями о конкретной предметной области.
Очень редко удается свести использование знаний к формулировке адекватной оценочной функции и таким образом помочь программе оценить свое поведение в текущей ситуации и найти правильный путь к решению. Но в большинстве случаев требуется нечто большее, что-то вроде глобальной стратегии решения проблем или явного использования знаний об объектах, их свойствах и связанных с ними действиях в конкретной предметной области, или комбинации того и другого.