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

Лекция 29-03-12

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

2. Поиск методом «генерация - проверка».

Процесс поиска может быть сформулирован в терминах «генерация-проверка». Действительно, пространство поиска (пространство состояний или И-ИЛИ граф), как правило, явно не задано. Поэтому для осуществления процесса поиска необходимо генерировать очередное возможное решение (состояние или подзадачу) и проверить, не является ли оно результирующим. Разумно потребовать, чтобы генератор удовлетворял требованиям полноты и неизбыточности. Говорят, что генератор является полным, если он обеспечивает генерацию всех возможных решений. Генератор является неизбыточным, если он генерирует каждое решение только один раз. Обеспечение свойства неизбыточности является важным, но трудновыполнимым, т.к. в соответствии с этим требованием не допускается генерация не только тождественных, но и синонимичных решений. Например, если задача генератора синтезировать все фразы языка, то весьма трудно (если вообще возможно) сделать такой генератор неизбыточным.

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

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

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