Методы решения задач

Функционирование многих ИС носит целеустремлён-ный характер (например, автономные интеллектуальные ро-боты). Такое функционирование сводится к решению зада-чи планирования пути достижения нужной цели из некото-рой фиксированной начальной ситуации. Результатом реше-ния задачи будет план действий– частично-упорядоченная совокупность действий. Такой план напоминает сценарий, где в качестве отношения между вершинами выступают от-ношения типа: "цель-подцель" "цель-действие", "действие-результат" и т.п. Любой путь в этом сценарии, ведущий от вершины, соответствующей текущей ситуации, в любую из целевых вершин, определяет план действий (разные пути к одной цели).

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

В первом случае считается заданным некоторое прост-ранство ситуаций. Описание ситуаций включает состояние внешнего мира и состояние ИНТСИС, характеризуемые рядом параметров. Ситуации образуют некоторые обобщён-ные состояния, а действия ИНТСИС или изменения во внешней среде приводят к изменению активных в данный момент состояний.

Среди обобщённых состояний выделены начальные состоя-ния (обычно одно) и конечные (целевые) состояния. SS-про-блема состоит в поиске пути, ведущего из начального состо-яния в одно из конечных.

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

При планировании в пространстве задач ситуация нес-колько иная. Пространство образуется в результате введе-ния на множестве задач отношения типа: "часть-целое", "задача-подзадача", "общий случай-частный случай" и т.п. Другими словами, пространство задач отражает декомпози-цию задач на подзадачи (цели на подцели). PR-проблема состоит в поиске декомпозиции исходной задачи на подза-дачи, приводящей к задачам, решение которых системе известно. Например, ИНТСИС известно, как вычисляются значения sin x и cos x для любого значения аргумента и как производится операция деления. Если необходимо вычис-лить ctg x, то решением PR-проблемы будет представление этой задачи в виде декомпозиции ctg x=cos x/sin x (кроме х=π/2+k π).

Решение задач методом поиска
в пространстве состояний

Представление задач в пространстве состояний предпо-лагает задание ряда описаний: состояний, множества опе-раторов и их воздействий на переходы между состояния-ми, целевых состояний. Описания состояний могут пред-ставлять собой строки символов, векторы, двухмерные массивы, деревья, списки и т.п. Операторы переводят одно состояние в другое. Иногда они представляются в виде продукций A=>B, означающих, что состояние А преобра-зуется в состояние В.

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

Таким образом, проблема поиска решения задачи <А,В> при планировании по состояниям представляется как про-блема поиска на графе пути из А в В. Обычно графы не задаются, а генерируются по мере надобности.

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

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

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

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

Примерами других алгоритмов методов поиска в прост-ранстве состояний являются: Алгоритм кратчайших путей Мура; Алгоритм Дейкстры (обобщение алгоритма Мура); Алгоритм Дорана и Мичи поиска с низкой стоимостью; Алгоритм Харта, Нильсона и Рафаэля.