Специальные системы продукций

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

Рассмотренные системы продукций всегда начинали поиск от исходного состояния и работали до тех нор, пока в результате не получали целевое состояние. Такие системы продукций обычно (см. начало параграфа 2.2) называются прямыми. Логично поступать и наоборот — применять обратные правила и двигаться от целевого состояния к исходному. Такие системы часто называют обратными. Возможны случаи, когда обратная система более эффективна, возможны случаи, когда эффективнее прямая (рис. 2.12). Образно говоря, это зависит от того, где цель больше — в большую мишень легче попасть.

Рис. 2.12. Прямые и обратные системы продукций.

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

Пусть целевое число равно 60, а множители — 2, 3, 5.

Прямая система выглядит таким образом:

d0 := {2,3/5}, t (d) := 60ed.

R := if xed & yed & xygd & xy<61 then d:= du{xy}.

Поиск в ширину дает следующие результаты (19 применений правил):

• 235 (исходные множители)
• 4 6 9 10 15 25 (попарные произведения)
• 8 12 18 20 30 50 (вторая строка *2)
• 27 45 (вторая строка *3)
• (вторая строка *5 — нет новых)
• 16 24 36 40 60 (третья строка *2 — достигнута цель)

Поиск в глубину дает следующие результаты (четыре применения правил):

• 2 3 5
• 15 45 30 60

Обратная система будет такой.

d0 := {60}, t (d) := led.

R := {if xed & x:2 then d := d{x}u{x/2} if xed St x:3 then d := d{x}u{x/3} if xed St x:5 then d := d{x}u{x/5}}.

Поиск в глубину дает следующие результаты (четыре применения правил):

• 60
• 30 15 5 1

Поиск в ширину дает такие результаты (11 применений правил):

• 60
• 30 20 12
• 15 10 6 4
• 5 3 2
• 1

Здесь цель — единственная, а данных — три, поэтому, как и следовало ожидать, обратная система дает чуть лучшие, чем прямая, но сопоставимые результаты.

Однако если поставить другую, более расплывчатую цель: какие числа, меньшие или равные 60, можно получить из множителей 2, 3, 5, то сравнение систем покажет совсем другую картину. Действительно, прямая система при этом отличается отсутствием условия окончания и должна работать, пока не остановится ввиду отсутствия применимых правил. Накопленное состояние базы данных будет ответом на вопрос задачи:

d0 := {2,3,5}.

R := if xed & yed & xygd & xy<61 then d:= du{xy}.

Поиск в ширину дает следующие результаты (22 применения правил):

• 235 (исходные множители)
• 4 6 9 10 15 25 (попарные произведения)
• 8 12 18 20 30 50 (вторая строка *2)
• 27 45 (вторая строка *3)
• (вторая строка *5)
• 16 24 36 40 60 (третья строка *2)
• 54 (третья строка *3)
• 32 48 (шестая строка *2)

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

Теперь постараемся ответить на вопрос, какие числа, меньшие или равные 60, можно получить из множителей 2, 3, 5, используя обратную систему продукций. Сразу ясно, что придется 60 раз задать вопрос, представимо ли очередное число. При этом, используя, например, поиск в глубину, будет найден ответ для каждого числа, причем число применений правил минимум равно нулю (если проверяемое число простое), максимум равно пяти. В среднем — около двух применений правил для проверки одного числа. Это означает, что обратная система в данном случае на порядок хуже, и нет необходимости загромождать книгу утомительным описанием ее работы, — столбцами ненужных чисел. В то же время, если потребовать просто разложить число 60 на множители, то обратная система, очевидно, будет более эффективна.

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

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

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

Рис. 2.13. Преимущество двусторонней системы продукций

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

Рис. 2.14. Двусторонняя система с направленными эвристиками

Система продукций с множеством правил R называется коммутативной, если выполнены следующие три условия:

— если два правила применимы, то при применении одного, другое остается применимым;

— если цель достигнута, то навсегда, применение правил не отменяет достижения цели;

— если два правила применимы, то их можно применять в любом порядке.

Рассмотренная в п. 2.3.1 система продукций для чисел является коммутативной. Другой пример коммутативной системы продукций — игра в «восемь», а задача о крестьянине, волке, козе и капусте — это некоммутативная система.

Заметим, что третье условие, условие коммутативности, не означает, что можно произвольно переупорядочить последовательность правил, т. е. утверждение VdeD (r2.f (r.f (d)) = rl. f (?'2.f (d))), вообще говоря, неверно. Но те правила, которые применимы в данный момент, можно применять в любом порядке.

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

Теорема 2.1. Всякую систему продукций можно преобразовать в коммутативную.

Доказательство. Пусть задана система продукций S = с начальным состоянием базы d₀. Рассмотрим ее граф поиска G. Построим новую систему продукций S' =< D R С >. Базой данных системы У будет граф поиска системы S. Правила R' новой системы — это различные способы преобразования графа поиска, которое можно делать с помощью стратегии С в старой системе (раскрытие узла). Новая система продукций коммутативна. Действительно:

• • если в старой системе два узла находятся в списке О, то раскрытие одного узла не препятствует раскрытию второго узла, так что первое условие коммутативности выполнено;
• • если в старой системе в графе поиска построен терминальный узел, то раскрытие других узлов не исключит из графа терминального узла, так что второе условие коммутативности выполнено;
• • если в старой системе два узла находятся в списке О, то их можно раскрывать в любом порядке, получится один и тот же результат, так что третье условие коммутативности выполнено, ч.т.д.

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

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

• 1. Раскрыть скобки.
• 2. Привести подобные.
• 3. Упорядочить по степеням.

Эти правила всем известны со школы, поэтому мы не стали записывать их формально. Попытаемся упростить выражение 1 + х (1 + х (3 + х + х)) (рис. 2.15).

Рис. 2.15. Упрощение выражений.

Если правило что-то меняет — применяем его. Для полиномов окончательный результат не зависит от порядка применения правил. Фактически здесь система продукций не содержала условий — это пример системы подстановки термову или системы правил переписывания у которые относятся к однородным системам продукций.

Система правил переписывания (Tenns rewriting system) — конечное множество правил переписывания /?, определяющее на множестве термов бинарное отношение —> (отношение редукции).

Говорят, что система правил переписывания R обладает свойством Черча — Россера_у если для любых термов t_x и t₂ выполняется равносильность? j = t₂ в том и только в том случае, когда существует единственный терм t₃y такой, что t_x —> t₃ и t₂ —> t₃. В этом случае система правил переписывания называется полной или канонической_у а результат применения правил R к исходной формуле — канонической формой.

В данном случае система обладает свойством Черча — Россера. Эго очень сильное, полезное и редкое свойство, которое позволяет легко решить автоматически многие задачи, такие как проверка равенств, решение уравнений и т. д. Однако канонические формы существуют не для всех классов алгебраических выражений. Наверняка читателю известны канонические формы для полиномов одной переменной и для булевых формул. В то же время, например, для элементарных функций математического анализа (дробно-рациональные функции, логарифм, экспонента и их суперпозиции) нормальной формы не существует^[1].

Покажем существенность свойства Черча — Россера путем, на первый взгляд, незначительного усложнения рассматриваемого примера упрощения алгебраических выражений. Попытаемся упростить выражение х ( 1 + + 1/х), которое в результате должно превратиться в х + 1. Для этого в наш пример необходимо добавить операцию деления и два следущих правила.

• 4. Привести к общему знаменателю.
• 5. Сократить числитель и знаменатель.

Очевидно, что теперь результат зависит от порядка применения правил. Иными словами, система продукций уже не является коммутативной, более того, в некоторых случаях возможны тупики в поиске. В результате один из путей не редуцируется правилами 1—5 (рис. 2.16).

Рис. 2.16. Тупики при поиске.

Для решения этой проблемы, связанной с образованием тупиковых ветвей, добавим обратные операции.

6. Вынести за скобки.

Если ввести только правило 6 (вынесение за скобки), то будут два взаимообратных правила: раскрытие скобок и вынесение за скобки, а это значит, что возможно зацикливание, т. е. свойство Черча — Россера не выполняется по-прежнему. Чтобы тупик на рис. 2.16 сделать редуцируемым, необходимо добавить правило 7.

7. Разложить дробь

Но тогда может появиться бесконечное зацикливание, такое, которое при безвозвратном поиске невозможно распознать (на рис. 2.17 один из возможных циклов обведен овалом).

Рис. 2.17. Циклы при поиске.

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

• [1] Это объясняет, почему задачи, предлагаемые на экзаменах по элементарной математике («решить уравнение», «упростить выражение»), действительно иногда являются задачами, которые для своего решения требуют изобретательности и фантазии, а нс только механического применения заученных правил. Доказательство отсутствия канонической формыдля выражений в элементарных функциях было найдено сравнительно недавно и принадлежит к числу важных математических результатов последнего времени.