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

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

Большинство примеров появления недетерминизма с произвольным выбором альтернативы не представляет интереса для программирующих на Прологе. Иллюстративный пример недетерминизма с произвольным выбором альтернативы дает программа 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) ].

Дата добавления: 2014-01-07