Недетерминированное программирование

В силу недетерминированного характера программ, отсутствует единственным образом последовательность действий, если программы немысленно писать на другом языке программирования, то здесь это возможно.

При написании используется методика – «образовать и проверить». На современных ЭВМ можно построить аппроксимацию. В частности Пролог – интерпретатор, аппроксимирующий недетерминированное поведение с помощью механизма поиска с возвратом. При этом факт, что недетерминизм не отсутствует, а моделируется, для недетерминированного мышления не существенен. Следовательно, мы можем писать и недетерминированные программы.

Легко создавать логические программы, метод которых «образовать и проверить».

2 посылки …. , …..

/ \

генератор проверяет,

предполагаемых является ли решение

решений приемлемым

find(x)^-generate(x), prover(x).

В качестве генератора – предикат наподобие chlen.

?chlen(x, [a,b,c]).

x=a.

x=b.

x=c.

chlen можно использовать в программах, применяющих этот метод, для недетерминированного выбора элемента из списка.

sort(Xs,Ys):-perest(Xs,Ys), upor(Ys). (perest - генератор, upor - проверочный).

Задача о ферзях

Поле N*N, N ферзей, надо, чтобы ферзи не били друг друга.

Порядковый номер элемента списка Qs определяет N вертикали. Элементы – натуральные числа, и сам элеиент – N горизонтали, на которой находится ферзь.

queen(N,Qs).

queens(N,Qs):-perest(Ns,Qs), safe(Qs), range(1,N,Ns).

safe([Q|Qs]):-safe(Qs), not_attack(Q,Qs).

safe([ ]).

attack(X,Xs):-attack(X,1,Xs).

attack(X,N,[Y|Ys]):-X:=Y+N, X:=Y-N.

attack(X,N,[Y|Ys]):-N1:=N+1, attack(X,N1,Ys).

Отрицание:

not X:-X,!,fail.

not X.

range – генерирунет элементы в диапазоне от 1 до N, записывает в список Ns.

range(M,N,[M|Ns]):-M<N, M1:=M+1, range(M1,N,Ns).

range(N,N,[N]).

- Сначала обрабатывается Ns (от 1 до N).

- Генерируется перестановка Ns, проверяется safe (safe=U (список является решением поставленной задачи)).

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

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

- attack – пример изящного программирования (взаимосвязь диагоналей).

2 ферзя, находящиеся на одной диагонали на расстоянии М вертикали друг от друга, если N горизонталь 1 ферзя на М больше (меньше), чем N горизонтали другого.

Весьма неэффективно ( - не способна распознать симметричное решение;

- генерируются все возможные перестановки, которые не могут быть решением.)

2 вариант задачи:

range ……

range ……

queens(N,Qs):-range(1,N,Ns), queens(Ns,[ ],Qs).

queens(UnlQs,SafeQs,Qs):-vyrez(Q,UnlQs,UnlQs1), not attack(Q,SafeQs), queens(UnlQs1,[Q|SafeQs],Qs).

queens([ ],Qs,Qs).