Главная arrow Поиск arrow Стратегии поиска
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

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

Общий рассматриваемый здесь подход называется поиском по первому наилучшему совпадению. Поиск по первому наилучшему совпадению представляет собой разновидность общего алгоритма Tree-Search или Graph-Search, в котором узел для развертывания выбирается на основе функции оценки, f(n). По традиции для развертывания выбирается узел с наименьшей оценкой, поскольку такая оценка измеряет расстояние до цели.

Поиск по первому наилучшему совпадению может быть реализован в рамках описанной в данной книге общей инфраструктуры поиска с помощью очереди по приоритету — структуры данных, в которой периферия поиска поддерживается в возрастающем порядке f-значений. Название «поиск по первому наилучшему совпадению» (best first search) узаконено традицией, но неточно. В конце концов, если бы мы действительно могли развертывать наилучший узел первым, то не было бы и поиска как такового; решение задачи представляло бы собой прямое шествие к цели. Единственное, что мы можем сделать, — это выбрать узел, который представляется наилучшим в соответствии с функцией оценки. Если функция оценки действительно является точной, то выбранный узел в самом деле окажется наилучшим узлом, но фактически функция оценки иногда оказывается малопригодной и способной завести поиск в тупик. Тем не менее авторы будут придерживаться названия «поиск по первому наилучшему совпадению», поскольку более подходящее название «поиск по первому совпадению, которое можно считать наилучшим» было бы довольно громоздким.

Существует целое семейство алгоритмов поиска по первому наилучшему совпадению, Best-First-Search, с различными функциями оценки. Ключевым компонентом этих алгоритмов является эвристическая функция, обозначаемая как h(n):

h(n) = оценка стоимости наименее дорогостоящего пути от узла n до целевого узла

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

Эвристические функции (или просто эвристики) представляют собой наиболее общую форму, в которой к алгоритму поиска подключаются дополнительные знания о задаче. На данный момент мы будем определять их как произвольные функции, относящиеся к конкретной проблеме, с одним ограничением: если n — целевой узел, то h(n) = 0. В оставшейся части настоящего раздела рассматриваются два способа использования эвристической информации для управления поиском.