Стратегии информированного поиска

Стратегии информированного поиска представляют собой улучшенный вариант стратегий неинформированного поиска. При информированном поиске развертывается узел с наименьшим значением функции оценки f(x), которая обычно измеряет расстояние до цели. Такой подход называется поиском по первому наилучшему совпадению (best first search). Информированный поиск позволяет более эффективно достигать цели (т.е. за меньшее число развертываний узлов).

Название «поиск по первому наилучшему совпадению» не совсем точно. Если бы мы действительно могли развертывать самый лучший узел первым, то не было и поиска как такового — путь к цели был бы известен. На самом деле, мы можем выбирать узел, который представляется наилучшим в соответствии с функцией оценки f(n). Если функция оценки выбрана удачно, то развертываемый узел действительно окажется наилучшим узлом, но фактически функции оценки иногда оказываются малопригодными и даже способны завести в тупик.

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

Так, в задаче поиска маршрута между городами стоимость наименее дорогостоящего пути можно оценивать как расстояние по-прямой до цели. В этом случае эвристическая функция — это расстояние по прямой от узла n до целевого узла.

Эвристические функции (или эвристики) представляют собой наиболее общую форму, в которой к алгоритму поиска подключаются дополнительные знания о задаче.

Ниже рассмотрим две стратегии поиска с помощью эвристик — жадный поиск и поиск А*.

Дата добавления: 2015-07-26; просмотров: 218; Нарушение авторских прав

Мы поможем в написании ваших работ!