Достоинства и недостатки методов поиска в пространстве состояний

Приведем примеры задач, для решения которых могут применяться методы поиска в пространстве состояний.

• 1. Комбинаторные задачи. Классический пример — задача о коммивояжере (см. параграф 2.4). Состояния задаются списком городов, операторы соответствуют действию: направиться в город Л, направиться в город В,…, направиться в город N. Критерий достижения цели: любое описание, начинающееся и оканчивающееся городом А и перечисляющее все другие города, есть описание состояния, удовлетворяющего поставленной цели. Данная задача допускает поиск оптимального решения, поскольку дугам могут быть приписаны стоимости (длина пути) перехода из одного города в другой. Данная задача хорошо представима в графической форме (карте расстояний), что и делает ее удобной для применения методов поиска в пространстве состояний. Считается, что метод поиска в пространстве состояний применим при числе городов до 50. К данному классу задач хорошо сводятся практически любые однокритериальные задачи лабиринтного типа.
• 2. Задачи синтаксического анализа. При работе с языками (естественными или искусственными) задается грамматика построения правильных выражений (строк символов — слов, предложений, выражений) в данном языке и, следовательно, способ определения принадлежности произвольной строки символов к этому языку. Тогда множество состояний задачи синтаксического анализа может быть задано как множество строк (слов).

Начальное и целевое состояния определяются какими-то фиксированными словами в алфавите этого языка. Операторы могут быть заданы в виде правил переписывания типа: ррф —> р0ф, где подстрока (3 может быть заменена подстрокой 0. Эти правила могут выражать, например, синтаксис рассматриваемого языка. Критерий цели для этой задачи может быть задан строкой, число символов которой совпадает с числом символов целевого слова. Пример задачи такого типа: как слово «море» преобразовать в слово «рыба» путем замены на каждом шаге одной буквы. Очевидно, что при большом числе правил переписывания граф пространства состояний становится слишком большим.

• 3. Задачи распределения. Известен объем продукции каждого типа; размеры поставок, которые должны быть осуществлены в заданные пункты. Необходимо найти такое распределение поставок, при котором, например, затраты на перевозки были бы минимальными. Состояния описываются списком объемов избыточной продукции, которая имеется в заданных пунктах. Операторы соответствуют передаче избытка продукции из одного пункта в другой. В качестве критерия может быть взято целевое состояние, при котором будут удовлетворены все заявки на поставку требуемой продукции. Типичная задача линейного программирования.
• 4. Задачи управления типа: требуется перевести объект управления с начальными значениями установленных параметров процесса в состояние, при котором эти параметры будут иметь заданные значения. Задача об обезьяне и бананах является типичной задачей этого класса.

Возникают вопросы: когда же следует применять описанные здесь методы поиска в пространстве состояний? Для каких классов задач эти методы применимы и могут дать эффективные решения?

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

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

Если найден удачный способ представления задачи, важно также, чтобы пространство состояний было не слишком большим. Существует множество примеров задач, кажущихся трудными, но таких, что при правильной их трактовке соответствующие пространства состояний оказываются очень узкими. Подчас пространство состояний «сжимается в точку» после того, как обнаруживается, что некоторые операторы могут быть выброшены за ненадобностью, а другие — объединены в более мощные операторы. И даже если такие простые преобразования неосуществимы, может оказаться, что полное переформулирование задачи, изменяющее само понятие состояния, приведет к меньшему пространству. Таким образом, проблема поиска хорошего представления имеет важнейшее значение. Поиск его всегда опирается на специфику задачи, использует ее кардинальным образом. Это означает, что способ представления всегда носит уникальный характер, но сути, является особым искусством и, следовательно, вряд ли существуют какие-то единые правила поиска хороших представлений.

Во всех рассмотренных нами классах задач, для решения которых обычно применяются методы поиска в пространстве состояний, число свойств объектов предметной области и отношений между ними, служащих затем основой для распознавания ситуаций, всегда небольшое. Например, в задаче об обезьяне и бананах — это Координаты (Обезьяны, Ящика, Бананов) и два отношения — «находиться на», «находиться у». В задаче коммивояжера использовались свойство «Иметь имя», а в качестве отношения — расстояние между каждыми двумя городами. Задача распределения — имена пунктов нахождения продукции и поставок, объемы имеющихся и требуемых поставок. Очевидно, что при увеличении числа свойств, отношений и их значений размерность пространства состояний будет быстро возрастать таким образом, что применение переборных методов станет практически нереализуемым.

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

• 1. Необходимы способы представления знаний о задаче, безразличные к содержанию (смыслу) самих знаний. Это позволит применять эти способы для представления знаний в любых предметных областях для решения задач.
• 2. Эти способы должны иметь механизм логического анализа, позволяющий моделировать человеческую логику выработки решений на выбранных моделях представления знаний.
• 3. Эти способы должны решать задачи, которые не решаются известными формальными моделями и методами в связи с их нестрогостыо и нечеткостью.

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