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

Лекция №9

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

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

Метод «образовать и проверить»

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

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

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

find(X)¬generate(X), test(X).

Эта Пролог-программа действует подобно обычной процедурной программе, выполняющей генерацию вариантов и их проверку. Если при решении вопроса find(X)?, успешно выполняется цель generate(X) с выдачей некоторого X, то затем выполняется проверка test(X). Если проверка завершается отказом, то производится возвращение к цели generate, с помощью которой генерируется следующий элемент. Процесс продолжается итерационно до тех пор, пока при успешной проверке не будет найдено решение с характерными свойствами или генератор не исчерпает все альтернативные решения.

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

В качестве генератора обычно используется программа для предиката member (программа 3.12), порождающая множество решений. На вопрос member(X[a,b,c])? будут даны в требуемой последовательности решения Х = а, Х = b и Х = с. Таким образом, предикат member можно использовать в программах, реализующих метод «образовать и проверить» для недетерминированного выбора корректного элемента из некоторого списка.

Программа 14.1 представляет собой простой пример реализации метода «образовать и проверить» с использованием в качестве генератора предиката member. Эта программа предназначена для идентификации частей речи предложения. Предполагается, что предложение представлено списком слов и существует база данных фактов, задающих части речи для определенных слов. Для задания частей речи используются унарные предикаты, аргументами которых являются слова, например, предикат существительное (man) указывает, что man – существительное, Отношение глагол(Предложение, Слово) истинно, если Слово в предложении Предложение является глаголом. Аналогичный смысл имеют предикаты существительное/2 и артикль/2. На вопрос глагол([а,man,loves,a,woman),V)? методом «образовать и проверить» будет дан ответ V= loves. Слова предложения генерируются с помощью предиката member, и затем проверяется, являются ли они глаголами.

глагол (Предложение, Глагол) ¬

Глагол – глагол в спискеслов Предложение.

глагол (Предложение, Слово) ¬

member (Слово, Предложение), глагол (Слово).

существительное (Предложение, Слово)

member (Слово, Предложение), существительное(Слово).

артикль (Предложение, Слово)

member (Слово, Предложение), артикль (Слово).

Словарь

существительное (man). существительное(woman).

артикль(а). глагол (loves).

Программа 14.1. Отыскание частей речи в предложении.

Другой простой пример-проверка существования в двух списках общего элемента. Рассмотрим предикат intersect (Xs,Ys), который истинен, если списки Xs и Ys имеют общий элемент. Определим его предложением

intersect(Xs.Ys) ¬ member(X,Xs), member(X,Ys).

Первая цель member в теле этого предложения генерирует элементы из первого списка, а с помощью второй цели member проверяется, входят ли эти элементы во второй список. Описывая эту программу как недетерминированную, можно говорить, что первая цель делает предположение о том, что Х содержится в списке Хs, а вторая цель проверяет, является ли Х элементом списка Ys.

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

Следующее определение предиката member с использованием предиката append

member(X,Xs) ¬append(As,[X | Bs],Xs)

само по существу является программой, в которой реализуется принцип «образовать и проверить». Однако в этой программе два шага метода сливаются в процессе унификации. С помощью цели append производится расщепление списка и тут же выполняется проверка, является ли Х первым элементом второго списка.

Остановимся на вопросе оптимизации программ, реализующих принцип «образовать и проверить» посредством внедрения шага проверки в генератор предполагаемых решений. Рассмотрим еще один пример применения обсуждаемого прин­ципа программу 3.20 для сортировки перестановками. Предложение верхнего уровня программы имеет вид

sort(Xs,Ys) ¬permutation(Xs,Ys), ordered(Ys).

Абстрактно эта программа, действуя недетерминированно, генерирует с помощью цели permutation(Xs,Ys) предположительно корректную перестановку, а с помощью цели ordered проверяет, действительно ли эта перестановка упорядочена должным образом.

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

Сортировка перестановками – крайне неэффективный алгоритм сортировки, имеющий экспоненциальную по размеру сортируемого списка сложность. Более приемлемый алгоритм получается,если внедрить проверку в часть алгоритма, ответственную за генерацию. Тогда генератор permutation выбирает из списка произвольный элемент и рекурсивно выполняет перестановку остальных элементов списка. Предикат ordered проверяет упорядоченность первых двух элементов этой перестановки, затем рекурсивно проверяет остальные элементы списка. Если рассматривать объединение рекурсивных целей permutation и ordered как рекурсивный процесс сортировки, то последний составляет основу алгоритма сортировки вставками (см. программу 3.21). Для сортировки списка сортируется его хвост, а головка списка вставляется на место, сохраняющее порядок расположения элементов. Выбор произвольного элемента должен быть заменен выбором первого элемента.

Еще один пример преимущества «сплетения» процессов генерации и проверки дает программа для решения задачи об N ферзях.

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

Эта задача была хорошо изучена в литературе по занимательной математике. Для N = 2 и N = 3 решения не существует; единственное, без учета симметричного, решение при N=4 показано на рис. 14.1. Для N=8 существует 88 (а с учетом симметричных – 92) решений этой задачи.

Программа 14.2-упрощенная программа для решения задачи об N ферзях. Отношение queen(N, Qs) истинно, если Qs – решение задачи об N ферзях. Решение представляется некоторой перестановкой списка от 7 до N. Порядковый номер элемента этого списка определяет номер вертикали, а сам элемент-номер горизонтали, на пересечении которых стоит ферзь. Так, решение [ 2,4,1, 3] задачи о четырех ферзях соответствует решению, изображенному на рис. 14.1. Подобное описание решений и программа их генерации неявно предполагают, что в любом решении задачи о N ферзях на каждой горизонтали и на каждой вертикали будет находиться по одному ферзю.

		Q
Q
			Q
	Q

Рис. 14.1. Решение задачи о четырех ферзях.

queens(N, Queens) ¬

Queens размещение ферзей, которое является решением задачи о N ферзях, представляемое перестановкой списка чисел [1,2,..,N].

queens(N,Qs) ¬

range(1,N,Ns), pemiutation(Ns,Qs), safe(Qs)

safe(Qs) ¬

Qs - безопасное размещение ферзей.

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).

permutation(Xs,Ys)¬См. программу 3.20. range(l,N,Ns)¬См. программу 8.12.

Программа 14.2. Простая программа для решения задачи о N ферзях с использованием метода «образовать и проверить».

Программа 14.2 выполняется следующим образом. Сначала с помощью предиката range образуется список Ns, содержащий числа от 1 до N. Затем начинается выполнение цикла «образовать и проверить». Посредством предиката permutation генерируется перестановка Qs элементов списка Ns, которая затем проверяется предикатом safe(Qs), принимающим значение «истинно», если перестановка Qs является решением задачи. Поскольку на одной и той же вертикали или горизонтали одновременно не могут размещаться два ферзя, этот предикат должен обеспечить лишь проверку того, не угрожают ли друг другу два ферзя по какой-нибудь диагонали. Предикат safe имеет рекурсивное определение. Размещение ферзей безопасно, если ферзи, представляемые хвостом этого списка, не атакуют друг друга, а ферзь, представляемый головой этого списка, не атакует никакого другого ферзя. В определении предиката attack (Q,Qs) использована изящная инкапсуляция взаимосвязи диагоналей. Два ферзя находятся на одной и той же диагонали на расстоянии М вертикалей друг от друга, если номер горизонтали одного ферзя на М больше или на М меньше, чем номер горизонтали другого ферзя. В программе 14.2 это выражается первым предложением attack/3. Смысл предиката attack (Q,Qs) можно выразить словами: «Ферзь Q атакует некоторого ферзя из списка Qs». Диагонали проверяются итерационно до тех пор, пока не будет достигнут конец доски,

Программа 14.2 не способна распознавать симметричные решения. Например, на вопрос queens (4, Qs)? она дает два ответа, а именно решения: Qs =[2,4.1,3] и [ 3,1,4,2].

Хотя логическая программа 14.2 написана грамотно, она весьма неэффективна. В ней генерируется много перестановок, которые заведомо не могут быть решениями. Как и в случае с программой сортировки перестановками, рассматриваемая про­грамма может быть улучшена внедрением проверки, в данном случае предиката safe, в генератор перестановок.

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

queens(N.Queens)¬

Queens -размещение ферзей, которое является решением -задачи о N ферзях, представляемое перестановкой списка чисел [1,2,..,N].

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

queens(UnplacedQs,SafeQs,Qs) ¬

select (Q, Unplaced Qs, Unplaced Qs1),

not attack (Q, Safe Qs),

queens(UnplacedQs1,[Q | SafeQs],Qs).

queens([ ],Qs,Qs).

select (X l Xs,Ys)¬См. программу 3.19.

attack(A, Xs)¬Cм. программу 14.2.

Программа 14.3. Программа для решения задачи о N ферзях посредством последовательного размещения ферзей.

Генератором в рассматриваемой программе является предикат select, проверка реализуется предикатом attack, или, более точно, его отрицанием.

Чтобы проверить, в безопасном ли положении находится новый ферзь, необходимо знать позиции ранее размещенных ферзей. Следовательно, искомое решение строится по принципу снизу вверх с применением накопителя. Здесь используется базовый метод, описанный в разд. 7.5. Использование накопителя приводит к размещению ферзей, начиная с правой границы доски. Программа 14.3 на вопрос queens (4,Qs) дает два решения в порядке, обратном порядку решений по программе 14.2.

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

В программе 14.4, предназначенной для решения задачи о раскрашивании карты, также использован принцип «образовать и проверить». Программа реализует следующий недетерминированный алгоритм:

для каждой области карты

- выбрать цвет,

- выбрать из оставшихся цветов (или проверить) цвета соседних областей

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

region (а. А, [В, С, D]). region(b,B,[A,C,E]),

region (с. С, [А, В, D, Е, F]), region (d, D, [А, С, F]), region(e,E,[B,C,F]), region(f,F[C,D,E])].

a
b	c	d
e	f

Рис. 14.2. Paскрашивание карты четырьмя цветами.

color _map(Map,Colors) ¬

Плоская карта Map раскрашивается красками Colors так, чтобы никакие две соседние области не были окрашены в одинаковый цвет. Карта представляется списком смежных областей region (Name,Color,Neighbors), где Name имя области. Color -ее цвет. Neighbors- цвета раскраски соседних областей. Программа может быть использована без начальной конкретизации всех цветов.

color_map([Region | Regions], Colors) ¬

color_region (Region, Colors),

coIor_map(Regions,Colors). color_map([ ], Сolors).

color_region (Region. Colors) ¬

Область Region и смежные с ней области окрашиваются в цвета Colors так, чтобы цвет этой области отличался от цвета, в который окрашены соседние области.

color_region(region(Name, Col or, Neighbors), Colors)¬

select(Color, Colors, Colors 1),

members (Neighbors, Colors 1).

select(X,Xs,Ys)¬Cм. программу 3.19. rnembers(Xs,Ys)¬См. программу 7.6.

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