Листинг А.2. Трассировка решения задачи Р4CLIPS> (reset) ==> f-0 (initial-fact) ==> f-1 (world (tag 1) (scope truth) (context 0)) ==> f-2 (statement (speaker A) (claim OR F A T B) (reason 0) (tag 1)) CLIPS> (run) FIRE 1 unwrap-trues f-1,f-2 Assumption A is a knight, so (OR F A T B) is true. ==> f-3 (claim (content OR F A T B) (reason 1) (scope truth) (context 0)) ==> f-4 (claim (content T A) (reason 1) (scope truth) (context 0)) FIRE 2 left-or: f-1,f-3 ==> f-5 (claim (content F A) (reason 1) (scope truth) (context 1)) <== f-1 (world (tag 1) (scope truth) (context 0)) ==> f-6 (world (tag 1) (scope truth) (context 1)) FIRE 3 contra-truth-scope: f-6,f-4,f-5 Disjunct 1 is inconsistent with earlier truth context. <== f-5 (claim (content F A) (reason 1) (scope truth) (context 1)) FIRE 4 right-or: f-6,f-3. ==> f-7 (claim (content Т В) (reason 1) (scope truth) (context 2)) <== f-6 (world (tag 1) (scope truth) (context 1)) ==> f-8 (world (tag 1) (scope truth) (context 2)) FIRE 5 consist-truth: f-8, f-2 Statement is consistent: <== f-8 (world (tag 1) (scope truth) (context 2)) ==> f-9 (world (tag 1) (scope consist) (context 2)) FIRE 6 true-knight: f-9, f-7 В is a knight <== f-7 (claim (content Т В) (reason 1) (scope truth) (context 2)) FIRE 7 true-knight: f-9,f-4 A is a knight <== f-4 (claim (content Т A) (reason 1) (scope truth) (context 0)) CLIPS> A.4.5. Обратное прослеживание и множество контекстов Модифицируем программу таким образом, чтобы она могла справиться и с задачами этого класса в более сложной постановке. Речь идет о задачах, в которых несколько персонажей произносят реплики. Пример такого рода головоломки приведен ниже. Упражнение 3 Р5. Встречаются два человека, А и В, которые заявляют следующее. А: "Я говорю правду, либо В лжец", В: " А говорит правду, либо я лжец". К какой категории следует отнести каждый из персонажей? (Решите эту задачу самостоятельно вручную, используя ту же систему обозначений, которая применялась ранее в этом Приложении.) Задача анализа высказываний нескольких персонажей потребует использования более сложной методики, которая получила наименование "обратное прослеживание на основе анализа зависимостей"(dependency-directed backtracking). От программы потребуется выполнить обратное прослеживание (откат) в следующих ситуациях: · когда обнаружится конфликт между текущим "миром" и ранее существовавшим, причем в ранее существовавшем "мире" предполагается истинность высказывания, но не была проанализирована его лживость; Когда обнаружится конфликт между текущим "миром" и ранее существовавшим, причем в ранее существовавшем "мире" был проанализирован только один операнд в составном дизъюнктивном утверждении. Чтобы смысл этих формулировок стал более понятным, рассмотрим следующий пример. Р6. Встречаются два человека, А и В, которые заявляют следующее. А: "Хотя бы один из нас говорит правду". В: "Хотя бы один из нас лжец". К какой категории следует отнести каждый из персонажей? Высказывания персонажей представим в следующем виде: А: Т(А) v Т(В) В: F(A) v F(B) Начнем с заявления персонажа В 71(5) => F(A) v F(B) и проанализируем левый операнд дизъюнкции. В результате будет сформирована корректная непротиворечивая интерпретация: В — правдолюбец, А — лжец. Получив непротиворечивую интерпретацию высказывания персонажа В, перейдем к анализу высказывания персонажа А: Т(А) => FALSE, поскольку правдивость А противоречит сформированной ранее интерпретации высказывания персонажа В. Предположим, что А — лжец. Тогда: F(A) => -(T(А) v T(B)) => F(A) ^ F(B) => FALSE. Таким образом, оказывается, что это предположение также не работает, поскольку противоречит выбранной ранее интерпретации высказывания персонажа В, из которой следует, что В говорит правду, Но анализ высказывания персонажа В нельзя считать законченным, поскольку не был выполнен анализ правого операнда дизъюнкции N(B) => F(A) v F(B) и не было проанализировано предположение, что В лжец. До тех пор, пока это не будет выполнено, мы не имеем права делать вывод, что высказывания в формулировке задачи противоречат друг другу. Поэтому придется вернуться назад в ту точку процесса логического анализа, где было сделано предположение об истинности левого операнда в дизъюнкции, и проанализировать вместо него правый операнд F(B). При этом сразу же будет обнаружено противоречие между истинностью F(B) и ранее высказанным предположением о правдивости персонажа В, но, не вернувшись назад и не выполнив этот анализ, мы не смогли бы обнаружить это противоречие. Теперь остается проанализировать следствие из предположения, что В — лжец. F(B) => -(F(A) v F(B)) => Т(А) ^T(В) => FALSE. Только теперь можно с чистой совестью утверждать, что не существует непротиворечивой интерпретации высказываний, приведенных в условии задачи. Предположение о правдивости персонажа В приводит к конфликту с высказыванием персонажа А, а предположение о лживости В противоречит его же словам. Чтобы в системе, использующей правила в качестве основного программного компонента, реализовать откат (обратное прослеживание), нужно в первую очередь иметь возможность восстановить тот контекст, который существовал в момент, когда было сформулировано предположение, приведшее к не удовлетворяющему нас результату. Как было показано в главе 5, одно из достоинств продукционных систем, подобных CLIPS, состоит в том, что они способны выполнить такой откат, не сохраняя прежнего состояния процесса вычислений, что коренным образом отличает их от фундаментально рекурсивных языков программирования, таких как LISP и PROLOG. При возникновении необходимости выполнить откат продукционные системы последовательно отменяют в обратном порядке все операции, связанные с добавлением данных в рабочую память, которые были выполнены, начиная с точки возврата, в которую нужно вернуться, вплоть до текущего этапа вычислений. Но таким способом можно реализовать возврат, только предполагая, что в ходе выполнения операций, следующих за точкой возврата, из рабочей памяти не было удалено ничего существенного, а все действия, модифицирующие состояние рабочей памяти, носили исключительно аддитивный характер. Примеры, подобные задаче Р6, существенно усложняют жизнь, поскольку для их решения программа должна выполнять некоторые дополнительные операции, в которых не было необходимости при решении задач с единственным высказыванием. (1) Сохранять информацию о возможных точках возврата. (2) При обнаружении противоречия принимать решение, выполнять или не выполнять откат, а если выполнять, то в какую именно точку. (3) Отменить все изменения, внесенные в состояние рабочей памяти после "прохождения" выбранной точки возврата. (4) Возобновить вычисления начиная с точки возврата. Рассмотрим подробнее каждую из этих операций. Каждый объект world имеет уникальный числовой идентификатор, который хранится в поле tag. Эта информация практически не используется при решении задач с единственным высказыванием, поскольку мы всегда имеем дело с одним и тем же объектом world, связанным с этим высказыванием. Но при решении задач, оперирующих с несколькими высказываниями, нам придется различать утверждения, которые порождены разными высказываниями в разных "мирах". По мере того, как мы будем переходить от анализа одних высказываний к другим, будут формироваться и новые объекты world. Прежние объекты world нужно оставлять в таком состоянии, чтобы при необходимости к ним можно было еще раз вернуться. Это означает, что вектор world, с которым прекращены операции (возможно, временно), содержал всю информацию, которая потребуется программе для возобновления работы с ним. При этом именно та точка, в которой процесс вычислений "переключился" на новый объект world, и будет потенциальной точкой возврата. Информация, сохраняемая в объекте, включает знание о том, какое предположение о правдивости или лживости персонажа было сделано в этом "мире" и какие дизъюнкты (операнды составного дизъюнктивного выражения) в утверждении, содержащемся в высказывании персонажа, уже проанализированы. Поскольку каждый объект world имеет свой уникальный идентификатор и каждое утверждение (объект claim) индексировано определенным объектом world, можно довольно просто выяснить, существует ли противоречие между разными "мирами" (т.е. между утверждениями, связанными с разными объектами world). Остается единственный вопрос — нужно ли возвращаться в ранее покинутый "мир", если в текущем "мире" обнаружено противоречие с ним. Мы будем применять стратегию поиска в глубину, которая состоит в том, что откат нужно выполнять только в том случае, если противоречие сохраняется после полного завершения анализа текущего "мира". Если объекты world нумеруются последовательно, по мере их формирования, то потребуется разработать правило, которое при возвращении в покинутый ранее "мир" уничтожит как текущий объект world, так и все промежуточные объекты такого типа, которые при необходимости затем могут быть воссозданы. Если прежний объект world содержит полную информацию о том, в каком состоянии был покинут "мир", и утверждения в этом "мире" не противоречат этому состоянию, то ничто не мешает нам продолжить вычисления из точки возврата. Начнем модификацию нашей программы с того, что в шаблон объекта world включим слот, в котором будет храниться идентификатор ранее покинутого "мира" (объекта), с которым данный объект конфликтует. Это нужно сделать по двум пр'ичинам. (1)Нам потребуется различать случаи, в которых противоречия возникают в пределах одного и того же "мира", от конфликтов между "мирами". Если текущее высказывание само по себе противоречиво (т.е. является парадоксом), нет смысла выполнять откат в прежний мир и искать в нем разрешения противоречия. (2) Наличие такого слота позволит разработать правило, которое будет выполнять откат прямо в этот покинутый ранее "мир". Ниже будет показано, что для решения проблемы можно обойтись без реализации правила, упомянутого в п.2, хотя это и не так легко сделать, но соображения, высказанные в п.1, в любом случае остаются в силе. Объект world представляет контекст, сформированный определенными предположениями о правдивости или лживости высказывания, принадлежащего некоторому персонажу. Объект имеет уникальный идентификатор в поле tag, а смысл допущения - истинность или лживость -фиксируется в поле scope. Поле prior может содержать идентификатор объекта world, обработанного перед тем, как был создан данный объект, и с которым данный объект может потенциально конфликтовать. В поле context сохраняется текущий контекст анализируемого операнда дизъюнкции, (deftemplate world (field tag (type INTEGER) (default 1)) (field scope (type SYMBOL) (default truth)) (field prior (type INTEGER) (default 0)) (field context (type INTEGER) (default 0) Помимо модификации структуры объекта, для выполнения отката потребуется разработать правила для выполнения некоторых ключевых операций. Эти операции перечислены ниже вместе с ключевыми словами, ассоциированными с каждой из них.
|
