Эвристический поиск

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

,

где - соответствует расстоянию на графе от узла до начального состояния;

- оценка расстояния от до узла, представляющего конечное состояние(целевое).

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

На рис.12 показано гипотетическое пространство с эвристическими оценками некото­рых из его состояний. Состояния, по которым велся эвристи­ческий поиск, отмечены полужирным шрифтом, отметим, что поиск не ведется по всему пространству. Другими словами, цель алгоритма поиска состоит в том, чтобы прийти к целевому состоянию кратчайшим путем. Чем более обоснованной является эври­стика тем меньше состояний нужно проверить при поиске цели.

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

Рисунок 12 - Эвристический поиск в гипотетическом пространстве состояний и алгоритм

Дата добавления: 2014-01-03