Глава 11. ЭВРИСТИЧЕСКИЕ ПРОГРАММЫ РЕШЕНИЯ ЗАДАЧ

11.0. Общие замечания

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

В идеальном случае нам хотелось бы получить универсально приемлемую эвристическую функцию, связанную непосредственно с Практически этого сейчас нет, и вряд ли когда-нибудь станет возможным. Эвристические функции и методы определения подзадач почти неизбежно зависят от характера задачи — метод, хороший в шахматах, может быть совсем непохож на хороший метод для алгебры. В этой главе обсуждаются три программы решения задач, претендующие на некоторую степень общности — универсальный решатель задач Ньюэлла, Саймона и их сотрудников, наша программа, названная „Фортранная дедуктивная система" (FDS), и система управления роботом под названием STRIPS, созданная в Станфордском исследовательском институте. GPS — это классическая программа искусственного интеллекта, в которой были введены многие основные понятия эвристического решения задач. FDS представляет собой развитие некоторых механизмов GPS, а в STRIPS делается попытка осуществить планирование при решении задач. И FDS и GPS были написаны до того, как появились известные теперь методы поиска на графе, поэтому ясно, что трудно установить между ними непосредственную связь. В системе STRIPS связь с поиском на графе гораздо яснее.

11.1. Терминология

При обсуждении интересующих нас программ можно пользоваться очень общей терминологией. Практически все что угодно можно рассматривать как объект, различные характеристики которого имеют заданные значения. Баскетбольную команду можно описать при помощи ее стиля нападения и защиты, а государство можно охарактеризовать совокупностью пар вида: экономика — индустриальная, население — 200 миллионов, политическая организация — демократическая республика. Соответствующая структура описания для ЭВМ одна и та же. Определенная задача возникает в том случае, если есть расхождение между описаниями существующего объекта и желаемого. Это расхождение можно ликвидировать, применяя операторы к имеющемуся объекту и к объектам, произошедшим от него, пока их описание не придет в соответствие с желаемым объектом. Каждый оператор должен иметь входную и выходную форму. Входная форма — это множество ограничений на значения характеристик, которые должны удовлетворяться перед применением оператора. Выходная форма — это определение значений, которые будут иметь некоторые характеристики (обычно не все) объекта после применения оператора..

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

Врач определяет, что главные симптомы, изменения которых нужно добиться, это жар и головная боль. Оператор очевиден — аспирин, его выходная форма:

Входная форма аспирина — определение тех людей, которым можно его принимать:

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

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