11.4. Планирование

11.4.0. Общая часть

Во всех методах решения задач, которые мы здесь обсуждали, каждый следующий шаг выбирался исходя из локальных критериев независимо от того, будет ли он соответствовать всей последовательности шагов. Нам кажется, что люди при решении задач часто обращают больше внимания на глобальные представления о прогрессе в решении. Вернемся к часто используемому примеру: при планировании маршрута путешествия мы прежде всего решаем, какие города мы хотели бы посетить. Расписание движения самолетов, такси и автобусов также составляются в соответствии с глобальным планом. Можно ли каким-нибудь образом обеспечить глобальное планирование при решении задач на ЭВМ? Ответ будет утвердительным. В литературе предложены два весьма различных метода планирования. Ньюэлл и Саймон (1972) предложили расширение GPS, в котором задача сначала решается в упрощенной области планирования, а затем делается попытка уточнить решение в этой области применительно к исходной, более детальной проблемной области. Файкс, Харт и Нильсон (1972) пользовались совершенно иным подходом, в котором они показали, как обобщенные планы можно абстрагировать из решений конкретных задач. После этого обобщенные планы пригодны для дальнейшего использования.

11.4.1. Планирование в GPS

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

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

Некоторые правила отображают пары полученных выражений в единые выражения. Одно из этих правил

устанавливает, что если цепочки А и В уже были получены, то цепочку можно добавить к списку полученных цепочек. В табл. 11.5 перечисляются операторы GPS, которые Ньюэлл и Саймон использовали при работе с исчислением высказываний. Каждый оператор записывался в виде правила переписывания. Кроме этих операторов, Ньюэлл и Саймон определили шесть классов различий между выражениями. Они приведены в табл. 11.6. Эти различия вместе с операторами табл. 11.5 определяют матрицу операторов и различий (см. табл. 11.7(a)). Эта матрица используется для управления решением задачи в исходной области поиска. Представим себе, что программе GPS предложили доказать, что переписывание

Таблица ll.5. (см. скан) Исходные и абстрактные логические операторы планирования (Ньюэлл и Саймон, 1972)

допустимо. Применяя методы разд. 11.2, программа GPS обнаружила бы, что левая и правая части (30) различаются рядом термов и знаком Учитывая табл. 11.7(a), можно выделить правила в качестве кандидатов для уменьшения этих различий. Хотя это и определяет исходную точку, задача представляет значительную трудность для GPS. Чтобы применить метод планирования к задаче (30), мы сначала строим абстрактную, упрощенную область поиска, в которой при сравнении двух выражений рассматриваются только различия в термах, числе вхождений переменных и группировании Задача (30) становится абстрактной задачей

Операторы переписывания следует соответственно перестроить, чтобы исключить различия всех видов, кроме использующихся в

Таблица 11.6. (см. скан) Различия, использованные Ньюэллом и Саймоном в исследованиях решения логических задач программой

данной упрощенной области. Например, правило

переходит в

В результате необходимых преобразований такого рода некоторые операторы исходной области в абстрактной области пропадают. Правило

Таблица 11.7. (см. скан) Матрица операторов и различий для логических задач в GPS

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

Теперь снова рассмотрим задачу (30) и ее абстрактную интерпретацию (31). Сравнивая правую и левую части (31), GPS обнаруживает между ними различие После ряда попыток GPS решает абстрактную задачу за несколько шагов: Отметим, что каждый шаг определяет правильное переписывание исходной цепочки.

Затем GPS пытается применить к исходной задаче. Обозначим соответствующие шаги чтобы отличить их от шагов в абстрактной задаче.

В этом месте план требует применения Однако форма не соответствует входной форме в исходной области. Сравните а также

Терм занимает неправильное положение в поэтому ставится подзадача уменьшения позиционного различия. После обращения к матрице операторов и различий осуществляется шаг

Снова пытаемся применить на этот раз к Достигаем успеха, получая

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

можно применить к в результате получим

Это и есть требуемое целевое состояние.

В GPS для постановки подзадач используется план, который после выполнения может не дать решения для исходной задачи, но „обычно" приводит к состоянию достаточно близкому к искомому целевому состоянию. Нет никаких гарантий того, что планирование всегда оправдает надежды, но все же опыт дает основания считать его полезным методом.