14. Правила выбора подцелей. Деревья вычислений логических программ. Стратегии вычисления логических программ (1158027), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

на каждом шаге обхода из текущей вершины Gосуществляется переходIIлибо в новую вершину-потомок G 0 , которая являетсяSLD-резольвентой запроса G и первого по порядкупрограммного утверждения D, ранее не использованногодля этой цели;либо в ранее построенную родительскую вершину G 00(откат), если все программные утверждения уже былиопробованы для построения SLD-резольвент запроса G .СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;?P(U,V ), R(U)tСТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t?P(U,V ), R(U)tСТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}?Q(Y1 ), R(b) ?t?P(U,V ), R(U)tСТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}?Q(Y1 ), R(b) ?t(4), {Y1 /c}?R(b) ?t?P(U,V ), R(U)tСТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}?Q(Y1 ), R(b) ?t(4), {Y1 /c}?R(b) ?t(3), ε?t??P(U,V ), R(U)tСТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}?Q(Y1 ), R(b) ?t(4), {Y1 /c}?R(b) ?t6(3), ε?t??P(U,V ), R(U)tСТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}?Q(Y1 ), R(b) ?t(4), {Y1 /c}6?R(b) ?t6(3), ε?t??P(U,V ), R(U)tСТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}?P(U,V ), R(U)t6?Q(Y1 ), R(b) ?t(4), {Y1 /c}6?R(b) ?t6(3), ε?t?СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}?P(U,V ), R(U)t6?Q(Y1 ), R(b) ?t(4), {Y1 /c}6?R(b) ?t6(3), ε?t?СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}6?Q(Y1 ), R(b) ?t(4), {Y1 /c}6?R(b) ?t(3), ε6?t??P(U,V ), R(U)t@ (2), {U/X1 , V /X1 } @R t?Q(X1 ), R(X1 )@СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );?P(U,V ), R(U)tR(b) ←;@(1), {U/X1 , V /Y1 } @(2), {U/X1 , V /X1 }Q(c) ←;@ t?Q(X1 ), R(X1 )R?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}6?Q(Y1 ), R(b) ?t(4), {Y1 /c}6?R(b) ?t(3), ε6?t?(2), {X1 /c}?t?R(c)СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );?P(U,V ), R(U)tR(b) ←;@(1), {U/X1 , V /Y1 } @(2), {U/X1 , V /X1 }Q(c) ←;@ t?Q(X1 ), R(X1 )R?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}6?Q(Y1 ), R(b) ?t(4), {Y1 /c}6?R(b) ?t6(3), ε?t?6(2), {X1 /c}?t?R(c)failureСТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );?P(U,V ), R(U)tR(b) ←;@(1), {U/X1 , V /Y1 }(2), {U/X1 , V /X1 }@I@@Q(c) ←;R t?Q(X1 ), R(X1 )?R(X1 ), Q(Y1 ), R(X1 ) t@@(3), {X1 /b}6?Q(Y1 ), R(b) ?t(4), {Y1 /c}6?R(b) ?t6(3), ε?t?6(2), {X1 /c}?t?R(c)failureСТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММСтратегия обхода в глубину с возвратомIимеет эффективную реализацию: в памяти нужно хранитьлишь запросы той ветви, по которой идет обход, и каждыйзапрос должен вести учет использованных программныхутверждений;Iявляется, к сожалению, вычислительно неполной.ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Обратимся к примеру 2.t?P(X Y ).P : P(X L) ← P(L), R(X );P(nil) ←;R(a) ←;R(c) ←;(1), {X1 /X , L1 /Y }(1), {Y /X2(1), {L2 /X3(1), {L3 /X4(1), {L4 /X5....?t?P(Y ), R(X )L2 }t?P(L2 ), R(X2 ), R(X )L3 }t?P(L3 ), R(X3 ), R(X2 ), R(X )L4 }t?P(L4 ), R(X4 ), R(X3 ), R(X2 ), R(X )L5 }∞ Обход дерева TG ,P уходит в глубинупо бесконечной ветви и не может возвратиться,чтобы обнаружить успешное вычисление.СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММСтратегия обхода в глубину с возвратом чувствительна кпорядку расположения программных утверждений в логическихпрограммах.

Результат вычисления запроса может существенноизмениться при перестановке программных утверждений.ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММЕще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;..t?P(X Y )ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }?t?P(Y ), R(X )ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }?t?P(Y ), R(X )(1), {Y /nil}?R(X ) tДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }?t?P(Y ), R(X )(1), {Y /nil}?R(X ) t(3), {X /a}t?ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }?t?P(Y ), R(X )(1), {Y /nil}?R(X ) t(3), {X /a}t?ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }?t?P(Y ), R(X )(1), {Y /nil}?R(X ) t(3), {X /a}t?(4), {X /c}t??ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }?t?P(Y ), R(X )(1), {Y /nil}?R(X ) t6(4), {X /c}tt?(3), {X /a}??ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }??P(Y ), R(X )t*(1), {Y /nil}?R(X ) t6(3), {X /a}t?(4), {X /c}t??ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }??P(Y ), R(X )t* (2), {Y /X2 L2 }t??P(L2 ), R(X2 ), R(X )(1), {Y /nil}?R(X ) t6(3), {X /a}t?(4), {X /c}t??.ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }??P(Y ), R(X )t* (2), {Y /X2 L2 }t??P(L2 ), R(X2 ), R(X )(1), {Y /nil}(1), {L2 /nil} ?R(X2 ), R(X ) t?R(X ) t6(3), {X /a}t?(4), {X /c}t??.ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }??P(Y ), R(X )t* (2), {Y /X2 L2 }t??P(L2 ), R(X2 ), R(X )(1), {Y /nil}(1), {L2 /nil} ?R(X2 ), R(X ) t?R(X ) t(3), {X2 /a}6?R(X ) t(3), {X /a}t?(4), {X /c}t??.ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }??P(Y ), R(X )t* (2), {Y /X2 L2 }t??P(L2 ), R(X2 ), R(X )(1), {Y /nil}(1), {L2 /nil} ?R(X2 ), R(X ) t?R(X ) t(3), {X2 /a}6?R(X ) t(3), {X /a}t?(4), {X /c}t?(3), {X /a}?t?.ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.t?P(X Y )P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.(2), {X1 /X , L1 /Y }??P(Y ), R(X )t* (2), {Y /X2 L2 }t??P(L2 ), R(X2 ), R(X )(1), {Y /nil}(1), {L2 /nil} ?R(X2 ), R(X ) t?R(X ) t(3), {X2 /a}6?R(X ) t(3), {X /a}t?.И Т.

Д.(4), {X /c}t?(3), {X /a}?t?СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПоскольку соображения эффективности превалируют надтребованиями вычислительной полноты, в качествестандартной стратегии вычисления логических программбыла выбрана стратегия обхода в глубину с возвратом.Программист должен сам позаботиться о надлежащем порядкерасположения программных утверждений, чтобы стандартнаястратегия вычисления позволяла отыскать все вычисленныеответы.КОНЕЦ ЛЕКЦИИ 14..

Характеристики

Список файлов лекций