Недетерминизм с произвольным выбором альтернативы и недетерминизм с неизвестным выбором альтернативы

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

Большинство примеров появления недетерминизма с произвольным выбором альтернативы не представляет интереса для программирующих на Прологе. Иллюстративный пример недетерминизма с произвольным выбором альтернативы дает программа minimum (см. программу 3.7). В случае когда Х и У совпадают, программа

minimum (X,Y.X)X  Y.

minimum (X,Y,Y)Y  X,

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

С другой стороны, программы, демонстрирующие недетерминизм с неизвестным выбором альтернативы, являются вполне обычными. Рассмотрим программу для проверки изоморфности двух бинарных деревьев. Такая проверка обеспечивается программой 3.25, которая выглядит следующим образом:

isotree (void, void).

isotree (tree (X,L1,R1), tree (X.L2,R2)) isotree (L1, R1), isotree (L2, R2).

isotree (tree <X,L1,R1), tree (X. L2, R2))  isotree (LI, R2), isotree (L2,R1).

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

Процесс разработки Пролог-программ с любой формой недетерминизма может и не отличаться от процесса разработки детерминированных программ. Каждое предложение пишется независимо от другого. Для программиста безразлично, одному или нескольким предложениям сопоставляются входные данные. Действительно, это проявляется во множественных применениях Пролог-программ. Программа с аргументами одного вида может быть детерминированной, с аргументами другого вида-недетерминированной, как, например, append.

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

Рассмотрим эту точку зрения более подробно на примере задачи определения связности двух вершин в графе. На рис. 14.3 изображены два графа, которые будут использованы при обсуждении предлагаемых идей. Слева изображено дерево, а справа-граф с циклом. Деревья, или ориентированные ациклические графы, как будет видно из примеров наших программ, позволяют получать более простые решения, чем графы с циклами,

Наша первая программа представляет собой незначительную модификацию программы, представленной в разд. 2,3, Программа 14.8 определяет отношение connected (X,Y), которое истинно, если вершины Х и Y графа связны. Ребра графа ориентированы, факт edge (X, Y) устанавливает существование ориентированного ребра из Х и У. Декларативно эта программа представляет собой сжатое рекурсивное описание связности вершин графа. Операционная интерпретация в виде Пролог-программы состоит в том, что это – реализация алгоритма поиска в глубину для определения наличия связи двух вершин графа.

Вопрос connected (а, X) для графа, изображенного слева на рис. 14.3, приводит к следующим решениям: b,c,f,h,i,g,d,j,e и k. Их порядок определяется алгоритмом обхода дерева в глубину.

Программа 14.9 для поиска пути между двумя вершинами является расширением этой простой программы. Предикат path (X, Y,Path) истинен, если Path – путь в графе из вершины Х в вершину Y. Обе концевые точки включаются в путь.

Рис. 14.3. Ориентированные графы.

connected(X,Y)

вершина Х связана с вершиной У, определено некоторое отношение edge/2. описывающее ориентированный ациклический граф.

connected (А, А).

connected(A,B) edge(A,N), connected (N, В).

Данные

edge(a,b). edge (а,с), edge (a,d). edge(a,e).

edge(d,j). edge(c,f). edge(c,g). edge(f,h).

edge(e,k). edge(f,i). edge(x,y). edge(y,z).

edge(z,x). edge(y,u). edge(z,v).

Программа 14.8. Определение связности конечного ориентированного ациклического графа.

path (X,Y, Path )

Path - путь между двумя вершинами Х и Y в ориентированном ациклическом графе, определенном отношением edge/2.

path(X,X,[X]).

path(X,Y,[X | P]) edge(X,N), path(N,Y,P).

Программа 14.9. Определение пути в графе методом поиска в глубину.

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

С помощью поиска в глубину осуществляется корректный обход любого конечного дерева или ориентированного ациклического графа. Однако встречаются задачи, в которых требуется производить обход графа с циклами, В процессе вычислений может образоваться бесконечный (буквально!) программный цикл по одному из циклов графа. Например, на вопрос connected (x. Node)? для графа, изображенного справа на рис. 14.3, будет дано решение y, z и х, которое бесконечно повторяется, и никогда не будут достигнуты вершины и и v.

Неприятностей с зацикливанием можно избежать подходящей модификацией отношения connected. К аргументам отношения добавляется дополнительный аргумент, используемый для накопления уже пройденных при обходе вершин. Для исключения повторного просмотра одного и того же состояния применяется проверка. Указанные изменения введены в программе 14.10.

connected ( Х ,Y) 

Вершина Х связана с вершиной Y в графе, определенном отношением edge/2.

connected(X,Y)  connected(X,Y,[X]).

connected (A, A, Visited). connectcd(A,В, Visited) 

edge(A,N), not member(N, Visited),

connected (N, R. [N j Visited]).

Программа 14.10. Определение связности графа.

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

Программа не гарантирует достижения каждой вершины в бесконечном графе. Для обеспечения такой возможности необходимо использовать при обходе поиск в ширину. Этот вопрос будет обсуждаться в разд. 17.2.

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

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

Имеются три кубика: а, b и с и три места р q и r. Разрешенными являются два действия: перемещение верхнего в конструкции кубика на свободное место и перемещение верхнею в конструкции кубика на другой кубик. Для корректных действий необходимо, чтобы была свободна верхняя грань перемещаемого кубика? и свободны были место или кубик, на которые устанавливается перемещаемый кубик.

В программе 14.11, предназначенной для решения рассматриваемой задачи, на верхнем уровне определена процедура transform (State1,State2, Plan). Аргумент Plan определяет план действий, преобразующих состояние State1 в состояние State2.

Состояния представляются списком отношений вида on(X,Y), где Х – кубик, а Y – кубик или место, на котором стоит кубик. Они представляют факты, истинные в этом состоянии. Например, исходное и конечное состояния, показанные на рис. 14.4, представляются списками [oп (а,b).оп (b,р),оп(с,r)] и [on (a,b),on (b,с),оп (с,r)] соответственно. Отношение on для а предшествует отношению on для b, которое, в свою очередь предшествует отношению on для с. Такие описания состояний позволяют легко проверить, является ли в данный момент свободным кубик или место X. Для этого достаточно убедиться, что отношение оп(А,Х) ложно. В предикатах clear/2 и оп/3 программы 14.11 использованы преимущества такого представления.

Использованное в программе планирования действий рекурсивное предложение transform/4 определяет недетерминированный алгоритм:

пока желаемое состояние не достигнуто,

найти допустимое действие,

изменить текущее состояние,

проверить, что это состояние ранее не встречалось.

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

Рис 14.4. Начальное и конечное состояния в задаче сооружения из кубиков.

Программа 14.11 успешно решает простую задачу, представленную программой 14.12. Первый выбранный ею план просто нелеп, однако это все-таки план:

to_place (a, b, q), to_block (a, q, с), to_place(b, p, q),

to_place(a, с, p), to_block (a, p, b), to_place(c, г, p),

to_lace (a, b, r), to.block (а, г. с), to_piace (b, q, г),

to_.place (а, с, q), to_.block (a, q, b), to_place (с, p, q),

to_place (a, b, p), to_block (а. p, с), to_place (b, г, p),

to_place (а, с, г), to_block (b, p, a), to_place (с, q, p)

,to_block (b, а, с), to .place (a, r, q), to_block (b, с, а).

to_place (с, p, r), to_block (b, а, с), to_place (а, q, p),

to_block (a, p, b).

transform (State !.S{ate2,Plan) 

План Plan действий для преобразования состояния State1 в состояние State2

transform (State I,State2, Plan)

transform (State 1, State2, [State 1], Plan).

transform(State, State, Visited, [ ]).

transform (Statel, State2, Visited, [Action | Actions]) 

legal_action (Action, State1),

updete (Action, State1, State),

not member(State, Visited),

transform(State, State2, [State | Visited], Actions).

legal_action(to_place(Block,Y,Place),State)

on (Block, Y, State), clear(BIock, State),

place(Place),clear(Place, State).

legal_action (to block (Block1,Y,Block2), State) 

on(Blockl,Y,State),clear(Blockl, State), block(BIock2),

Block 1  Block2,clear(Block2, State).

clear(X,State) not member(on(A,X),State).

on(X,Y, State) member(on(X,Y), State).

update(to_block(X,Y,Z),State, State1) 

substitute(on(X,Y),on(X,Z),State,State1). update(to_place(X,Y,Z),State, Statel) 

substitute(on(X,Y),on(X,Z),State,State1), substitute(X,Y,Xs,Ys)Cм. упражнение 3.3(1).

Программа 14.11. Программа планирования с использованием поиска в глубину.

Предложения и данные для тестирования

test_plan (Name, Plan) 

initial_state(Name,I),final_state(Name,F), transform (I, F, Plan),

initial_state(test,[on(a,b),on(b,p),on(c,r)]).

final_state (test, [on (a, b), on (b,c), on (c, r)]).

block (a). block(b). block(c).

place(p), place(q). place(r).

Программа 14.12. Программа и данные для тестирования программы 14.11.

Сначала кубик а перемещается на место q,затем ставится на кубик с. После того как кубик b перемещается на место q. кубик а перемещается на место р и затем ставится на кубик b и после двадцати еще более хаотичных перемещений достигается окончательная конфигурация.

Легко привнести в алгоритм чуточку интеллекта, пытаясь сразу достичь одного из целевых состояний. Предикат legal_action можно заменить предикатом choose_action(Action,Slatel,State2), с помощью которого производится выбор действия. Следующего простого определения достаточно для более разумного поведения программы при решении нашей задачи:

choose_action (Action. State 1, State2) 

suggest (Action, State2), legal_action (Action, State 1). choose_action (Action, State l,Stale2) 

legal_action (Action, State 1).

suggest (to_place (X, Y, Z), State) 

member (on (X, Z), State), place (Z) suggest (to_block (X, Y, Z),State)

member (on (X, Z), State), block (Z).

Теперь будет получен первый план следующего вида: [to_place (a.b.q), to_block (b, p, с), to_block (a. q, b) ].

Моделирование недетерминированных вычислений.

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

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

Рассмотрим недетерминированный конечный автомат (НКА), определяемый пятеркой <Q,S,D,I,F>, где Q – множество состояний, S – множество символов, D – отображение из Q x S в Q, I – начальное состояние и F – множество конечных состояний автомата. Если отображение является функцией, то рассматриваемый автомат оказывается детерминированным.

В Прологе конечный автомат может быть описан тремя наборами фактов: initial (Q), истинным, если Q – начальное состояние автомата; final (Q), истинным, если Q – конечное состояние автомата; delta (Q, A, Q1), истинным, если НКА переходит из состояния Q в состояние Q1 при получении символа А. Множество состояний и множество входных символов определяются неявно как константы, входящие в предикаты.

Программа 14.13 является абстрактным интерпретатором НКА, Основной предикат программы – accept (S) истинен, если строка символов S, представляемая списком символов, допускается НКА.

Чтобы воспользоваться интерпретатором для имитации поведения определенного конечного автомата, этот автомат следует специфицировать. Это влечет за собой определение его начального состояния, конечного состояния и отношения переходов delta. Программа 14.14 определяет НКА, распознающий язык (аb)*. Этот автомат изображен на рис. 14.5. Он имеет два состояния: q0 и q1. Если автомат находится в состоянии q0 и считывается символ а. то автомат переходит в состояние q1; переход из состояния q1 в состояние q0 происходит при считывании символа b.

Другая базовая модель вычислений представляется магазинным автоматом, который распознает языки из класса контекстно-свободных языков. Недетерминированный магазинный автомат (НМА) получается посредством расширения модели НКА добавлением магазинной памяти для внутреннего состояния автомата. Формально НМА представляется семеркой <Q,S,G,D,I,Z,F>, где Q,S,I и F определяются так же, как и для НКА, G – список символов, которые можно поместить в стек, Z – начальный символ, содержащийся в стеке, D (дельта-функция) – функция переходов, учитывающая состояние стека, текущий символ и внутреннее состояние автомата.

Рис.14.5. Простой автомат.

accept(S) 

Строка символов, представленная списком S, принимается НКА, определенным предикатами initial/1, delta/3 и final/1.

accept(S) initial(Q), accept(Q,S)

accept (Q.[X | Xs])  deita(Q,X,Ql),accept (Ql,Xs).

accept (Q,[ ])  finа1(Q).

Программа 14.13 Интерпретатор для недетерминированного конечного автомата.

initial(q0).

final (q0).

delta(q0,a,q1)

delta(ql,b,q0).

Программа 14.14. НКА, распознающий язык (ab)*.

Функционирование НМА с заданной функцией D определяется его состоянием, первым символом во входной строке и элементом в вершине стека. За одну операцию НМА может поместить в стек или вытолкнуть из стека один символ.

Абстрактный интерпретатор НМА (программа 14.15) сходен с интерпретатором НКА, представленным программой 14.13. Как и в случае НКА, для имитации действия НМА необходимы предикаты, определяющие начальное и конечное состояния автомата. Множества символов определяются неявно. В программе 14.15 предполагается, что первоначально стек пуст. Отношение delta(Q,,A,S,Q1,S1) имеет незначительные отличия от аналогичного отношения для НКА. Оно истинно, если, находясь в состоянии Q при входном символе А и состоянии стека S, НМА переходит в состояние Q1 и переводит стек в состояние S1.

Частный случай НМА представлен программой. Этот автомат распознает палиндромы над конечным алфавитом. Палиндромом называется непустая строка, которая слева направо и справа налево читается одинаково. Например, строки abba и abaahaaba – палиндромы. Рассматриваемый автомат имеет два состояния: состояние q0, в котором символы помещаются в стек, и состояние q1, в котором символы выталкиваются из стека и сравниваются с символами входного потока. Решения о завершении записи в стек и о начале считывания из стека принимаются недетерминированно. В программе определены два факта delta, которые соответствуют переходам из состояния q0 в состояние q1 и учитывают, что палиндромы могут иметь нечетную или четную длину.

accept(S)

Строка, представленная списком S. принимается НМД, определенным предикатами initial/1, delta/5 и final/1.

accepl(Xs)  inilial(Q). accept(Q,Xs.[ ]).

accept(Q,[X | Xs],S)delta(Q,X.S,Ql,Sl), accept(QI,Xs,Sl).

accept (Q,[ ],[ ])  final (Q).

Программа 14.15 Интерпретатор недетерминированного магазинного автомата.

Интерпретатор и программу, определяющую автомат, можно представить в виде одной программы. В частности, программа 14.17 получена в результате объединения программ 14.15 и 14.16. В ней определено отношение palindrome (Xs), используемое для проверки того, является ли строка Xs палиндромом.

initial(q0). final(ql).

delta(q0,X,S,q0,[X | S]). delta (q0,X,S,ql,[X | S]). dclta(q0,X,S,ql,S).

deita(ql,X,[X | S],ql,S).

Программа 14.16. Определение НМА для палиндромов над конечным алфавитом.

palindrome ( Xs) 

Строка, представленная списком Xs, –- палиндром.

palindrome(Xs)  palindrome(q0,Xs,[ ]).

palindrome(q0, [X | Xs],S)  palindrome(qO,Xs,[X | S]). palindrome(qO,[X | Xs],S)palindrome(ql,[X | Xs],S).

palindrome (qO,[X | Xs],S)  palindrome (ql,Xs,S).

palindrome(ql,[X | Xs],[X | S])  paIindrome(ql,Xs,S).

pa!indrome(ql,[ ].[ ]).

Программа 14.17. Программа, распознающая палиндромы.

В процессе преобразования программ 14.15 и 14.16 в программу 14.17 использован метод раскрытие целей Раскрытие – полезный прием преобразования программ, используемый и в других местах книги. Сделаем небольшое отступление, чтобы дать определение этому методу.

Рассмотрим некоторую цель A в предложении НА ...,Аи предложениеС = (А B,...,B), такие, что А и А унифицируемы с наиболее общим унификатором . Раскрытие цели А относительно ее определения С дает предложение (HА...,A,B,...,B,А,...A).

Это определение аналогично определению раскрытия в языках функционального программирования.

Например, раскрытие цели initial (Q) в предложении

accept (X)  initial (Q),accept(Q,X,[ ]).

с использованием ее определения initial (q0) дает предложение

accept (X)  accept(q0,X,[ ]).

Если цель определяется несколькими предложениями, то раскрытие даст столько предожений, сколько их было в определении цели. Например, раскрытие цели delta в предложении

accept(Q,[X | Xs],S)delta(Q,X.S,Ql,Sl), accept(Q1,Xs,Sl).

с использованием определения цели delta в программе 14.16 приведет к четырем предложениям.

Теперь должно быть понятно, каким образом была получена программа 14.17:

раскрытием целей initial и delta в первых двух предложениях программы 14.15 и раскрытием цели final в оставшемся предложении. Кроме того, предикат accept был заменен в новой программе предикатом palindrome.

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