Эффективный прямой логический вывод
Алгоритм прямого логического вывода, приведенный в листинге 9.2, был спроектирован не с целью обеспечения эффективного функционирования, а, скорее, с целью упрощения его понимания. Существуют три возможных источника осложнений в его работе. Во-первых, "внутренний цикл" этого алгоритма предусматривает поиск всех возможных унификаторов, таких, что предпосылка некоторого правила унифицируется с подходящим множеством фактов в базе знаний. Такая операция часто именуется согласованием с шаблоном и может оказаться очень дорогостоящей. Во-вторых, в этом алгоритме происходит повторная проверка каждого правила в каждой итерации для определения того, выполняются ли его предпосылки, даже если в базу знаний в каждой итерации вносится лишь очень немного дополнений. В-третьих, этот алгоритм может вырабатывать много фактов, которые не имеют отношения к текущей цели. Устраним каждый из этих источников неэффективности по очереди.
Согласование правил с известными фактами
Проблема согласования предпосылки правила с фактами, хранящимися в базе знаний, может показаться достаточно простой. Например, предположим, что требуется применить следующее правило:
Missile(x) => Weapon (х)
Для этого необходимо найти все факты, которые согласуются с выражением Missile(x); в базе знаний, индексированной подходящим образом, это можно выполнить за постоянное время в расчете на каждый факт. А теперь рассмотрим правило, подобное следующему:
Missile (х) л Owns {Nono, х) => Sells ( West, х, Nono)
Найти все объекты, принадлежащие государству Ноуноу, опять-таки можно за постоянное время в расчете на каждый объект; затем мы можем применить к каждому объекту проверку, является ли он ракетой. Но если в базе знаний содержится много сведений об объектах, принадлежащих государству Ноуноу, и лишь немного данных о ракетах, то было бы лучше вначале найти все ракеты, а затем проверить, какие из них принадлежат Ноуноу. Это — проблема упорядочения конъюнктов: поиск упорядочения, позволяющего решать конъюнкты в предпосылке правила таким образом, чтобы общая стоимость решения была минимальной. Как оказалось, задача поиска оптимального упорядочения является NP-трудной, но имеются хорошие эвристики. Например, эвристика с наиболее ограниченной переменной, применявшаяся при решении задач CSP в главе 5, подсказывает, что необходимо упорядочить конъюнкты так, чтобы вначале проводился поиск ракет, если количество ракет меньше по сравнению с количеством всех известных объектов, принадлежащих государству Ноуноу.
Между процедурами согласования с шаблоном и удовлетворения ограничений действительно существует очень тесная связь. Каждый конъюнкт может рассматриваться как ограничение на содержащиеся в нем переменные; например, Missile(x) — это унарное ограничение на х. Развивая эту идею, можно прийти к выводу, что существует возможность представить любую задачу CSP с конечной областью определения как единственное определенное выражение наряду с некоторыми касающимися ее базовыми фактами. Рассмотрим приведенную на рис. 5.1 задачу раскраски карты, которая снова показана на рис. 9.3, а. Эквивалентная формулировка в виде одного определенного выражения приведена на рис. 9.3, б. Очевидно, что заключение Colorable() можно вывести из этой базы знаний, только если данная задача CSP имеет решение. А поскольку задачи CSP, вообще говоря, включают задачи 3-SAT в качестве частных случаев, на основании этого можно сделать вывод, что задача согласования определенного выражения с множеством фактов является NP-трудной.
То, что во внутреннем цикле алгоритма прямого логического вывода приходится решать NP-трудную задачу согласования, может показаться на первый взгляд довольно неприятным. Тем не менее, есть следующие три фактора, благодаря которым эта проблема предстает немного в лучшем свете.
• Напомним, что большинство правил в базах знаний, применяемых на практике, являются небольшими и простыми (подобно правилам, используемым в примере доказательства преступления), а не большими и сложными (как в формулировке задачи CSP, приведенной на рис. 9.3). В мире пользователей баз данных принято считать, что размеры правил и арности предикатов не превышают некоторого постоянного значения, и принимать во внимание только сложность данных, т.е. сложность логического вывода как функции от количества базовых фактов в базе данных. Можно легко показать, что обусловленная данными сложность в прямом логическом выводе определяется полиномиальной зависимостью.
Могут рассматриваться подклассы правил, для которых согласование является наиболее эффективным. По сути, каждое выражение на языке Datalog может рассматриваться как определяющее некоторую задачу CSP, поэтому согласование будет осуществимым только тогда, когда соответствующая задача CSP является разрешимой. Некоторые разрешимые семейства задач CSP описаны в главе 5. Например, если граф ограничений (граф, узлами которого являются переменные, а дугами — ограничения) образует дерево, то задача CSP может быть решена за линейное время. Точно такой же результат остается в силе для согласования с правилами. Например, если из карты, приведенной на рис. 9.3, будет удален узел SA, относящийся к Южной Австралии, то результирующее выражение примет следующий вид:
Diff{wa,nt) л Diff{nt,q) л Diff(q,nsw) л Diff(nsw,v) => ColorableO
что соответствует сокращенной задаче CSP, показанной на рис. 5.7. Для решения задачи согласования с правилами могут непосредственно применяться алгоритмы решения задач CSP с древовидной структурой.
• Можно приложить определенные усилия по устранению излишних попыток согласования с правилами в алгоритме прямого логического вывода, что является темой следующего раздела.