Программа 14.4. Раскрашиваниекарты

Словарь

существительное (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.

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

Отношением верхнего уровня рассматриваемой программы является со1оr_ тар (Map,Colors), где Map – карта, представляемая описанным выше способом, Colors- список цветов, используемых для раскрашивания карты. Выберем цвета: красный, желтый, голубой и белый. Ядро алгоритма – определение отношения color_ region (Region, Colors):

color__region (region (Name, Color, Neighbors), Colors)¬

select (Color, Colors, Colors 1),