Общие методы поиска решений в пространстве состояний

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

Задачу поиска в пространстве состояний можно сформулировать в общем виде так: Пусть исходная задача описывается тройкой (S, F, T), где S – множество начальных состояний; F – множество операторов, отображающих одни состояния в другие; T – множество целевых состояний. Решение задачи состоит в нахождении последовательности операторов f₁,f₂,…,f_k (f_i ÎF), которые преобразуют начальные состояния в конечные. Задача поиска в пространстве состояний описывается с помощью понятий теории графов [41]. Задается начальная вершина (исходное состояние) и множество целевых вершин T. Для построения пространства состояний используются операторы F. Последовательно от корня к вершинам дерева применяются операторы, относящиеся к этому уровню, для построения вершин-преемников следующего уровня (раскрытие вершин). Дуги идентифицируются как операторы преобразования. Получаемые вершины - преемники проверяются: не являются ли они целевыми. Далее переходят к следующему уровню. Терминальные вершины – это те, к которым нельзя применить никаких операторов. Раскрытие продолжается до тех пор, пока не получена целевая или терминальная вершина. Поиск на графе состояний – это процесс построения графа G, содержащего целевую вершину. Этот граф называется графом поиска. Различие нескольких вариантов реализации метода перебора, которые отличаются заданным порядком, в котором будут перебираться вершины.

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

Поиск в ширину. Вершины раскрываются в последовательности их порождения. Поиск идет по ширине дерева, т. к. раскрытие вершины происходит вдоль одного уровня. Целевая вершина выбирается сразу же после порождения. При поиске в ширину возможно нахождение наиболее короткого пути к целевой вершине, если такой путь есть. На рис. 6.3 представлены графы поиска, построение при поиске в глубину и в ширину.

а)

б)

Рис. 6.3. Графы поиска, построенные при поиске в глубину (а) и ширину (б)

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

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

Для методов поиска решения при представлении пространства состояний в виде графа характерно то, что в них в основном предусматривается запоминание результатовприменения нескольких последовательностей правил. Другая особенность – они работают в пробном режиме, т. е. при выборе и использовании применимого правила для какой-либо ситуации предусматривается возможность возврата к этой ситуации для применения другого правила. Достоинствами методов перебора является достаточно простая их реализация и возможность в принципе находить решение, если оно существует. Однако на практике всегда есть ограничения по времени и объему памяти на процесс реализации поиска. Для больших пространств и сложных массивов задач методы перебора неприемлемы – реальность комбинаторного взрыва. Для сокращения поиска необходима информация, называемая эвристической.

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

При использовании эвристических методов поиска открытые вершины стремятся упорядочить таким образом, чтобы процесс поиска распространился в наиболее перспективных направлениях. Для определения направления поиска используется некоторая мера, характеризующая перспективность вершины или пути, где эта вершина находится. Эту меру называют оценочной функцией f(n). Эта функция является оценкой стоимости кратчайшего пути из начальной вершины в целевую при условии, что он проходит через вершину n. При раскрытии вершины или определении пути выбирается вершина с минимальным значением оценочной функции. Оценочная функция должна адекватно характеризовать пространство поиска, т.е. необходим достаточно большой объем знаний о проблемной области и тщательный анализ пространства состояний. На практике использование количественных характеристик и весовых коэффициентов для представления этих знаний себя не оправдывает, так как применение не позволяет эффективно вести поиск решений (могут потребоваться большие объемы вычислений). Кроме того, эвристический поиск с использование оценочной функции предполагает достоверное знание пространства состояний. Однако в реальной практике при принятии решений сталкиваются с фактами и знаниями недостаточно полными и определенными. Кроме того, часто на процесс поиска влияет дефицит времени. В этих условиях люди используют методы, отличные от формального математического рассуждения. Формальное математическое рассуждение является монотонным, т.е. каждое заключение следует из предыдущего. (Монотонность – свойство некоторых логических и математических операций (функций), которое, говоря обобщенно, состоит в том, что направление возможного изменения результата операций зависит только от направления изменения того, над чем эти операции производятся.)

Специалисты, принимающие решения, используют немонотонные рассуждения, или рассуждения здравого смысла (основывающиеся на общих элементарных знаниях). Несмотря на то, что рассуждения здравого смысла являются довольно обыденными для людей, очень трудно достигнуть требуемого уровня реализации подобных рассуждений в ИИ. (Тем не менее, в некоторых классических ЭС, таких как MYCIN, PROSPECTOR, этот метод довольно успешно реализован для сокращения пространства поиска.

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

Метод редукции. Поиск необходимой совокупности данных для решения задачи сводится к решению составляющих подзадач. Задачи описываются различными способами: списки, деревья, массивы. Рассмотрим форму описания задачи как поиск в пространстве состояний. В данном представлении подзадачи рассматриваются как задачи нахождения связи определенными состояниями в пространстве поиска. Для представления исходной задачи в виде совокупности подзадач используется оператор перехода к новому описанию. Этот оператор преобразует исходную задачу таким образом, что при решении всех подзадач – преемников обеспечивается решение исходной задачи. Для каждого представления исходной задачи может существовать некоторое множество таких операторов, каждый из которых порождает свою совокупность подзадач. Часть этих подзадач может оказаться неразрешимой. Для других подзадач процесс повторяется, т.е. их в свою очередь, также сводят к подзадачам. Это продолжается до тех пор, пока каждая подзадача не будет иметь очевидное решение.

Процесс преобразования также удобно описывать с помощью графовых структур. Процесс поиска решения исходной задачи при таком описании представляет собой направленный граф редукции задач. Этот граф называется графом И/ИЛИ. Вершины этого графа представляют описания задач и подзадач. Граф И/ИЛИ содержит вершины двух типов. Тип “И” – соответствует задаче, решаемой при условии реализации всех ее подзадач в соответствующих вершинах – преемниках. Тип “ИЛИ” – соответствует задаче, решение которой возможно получить при решении одной из альтернативных подзадач в соответствующих вершинах – преемниках. На рис. 6.4. представлены фрогменты графов типа И/ИЛИ.

a)

б)

Рис. 6.4. Представление разбиения исходной задачи на подзадачи в виде графа И/ИЛИ (а) и преобразование графа И/ИЛИ (б).

Исходная задача S₀ разбивается на группы подзадач. Она может быть решена путем решения подзадач либо S₁ и S₂; либо S₃; S₄ и S₅. Вершины N, S₃, M, S₅ – это вершины типа “И”. Штриховой линией показан вариант решающего графа исходной задачи. Решения подзадач S₂, S₇, S₉, S₁₀, S₁₁ - предполагают известными. Решения других подзадач неизвестны. В структуру обычно вводятся дополнительные вершины, чтобы каждое множество подзадач формировалось под своей собственной родительской вершиной. Вершина графа И/ИЛИ может принадлежать к типу И либо ИЛИ. Поэтому исходный граф преобразуется и вводятся дополнительные вершины N и M, которые служат отдельными родительскими вершинами для подзадач {S₁, S₂} и {S₄, S₅. Таким образом, вершина S₀ преобразуется в вершину ИЛИ.

Реализация графа редукции аналогична реализации графа поиска решений в пространстве состояний. В частном случае, если вершин И нет, получается обычный граф пространства состояний. Поэтому метод редукции является в какой-то степени обобщением подхода с использованием пространства состояний.

Процесс поиска на графе И/ИЛИ заключается в построении решающего графа (или дерева решений), который является подграфом графа редукции.