Cодержание

1. Введение

2. Раскрашивание плоской карты

1. Введение

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

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

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

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

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

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

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

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

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

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

2. Раскрашивание плоской карты

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

color_map([Region|Regions],Colors) :-
color_region(Region,Colors),
color_map(Regions,Colors).
color_map([],Colors).
 
color_region(region(Name,Color,Neighbors),Colors) :-
select(Color,Colors,Colors1),
members(Neighbors,Colors1).
 
select(X,[X|Xs],Xs).
select(X,[Y|Ys],[Y|Zs]) :- select(X,Ys,Zs).
 
members([X|Xs],Ys) :- member(X,Ys), members(Xs,Ys).
members([],Ys).
 
test_color(Name,Map) :-
map(Name,Map),
colors(Name,Colors),
color_map(Map,Colors).
 
map(test,[region(a,A,[B,C,D]), region(b,B,[A,C,E]),
region(c,C,[A,B,D,E,F]), region(d,D,[A,C,F]),
region(e,E,[B,C,F]), region(f,F,[C,D,E])]).
 
map(west_europe,
[ region(portugal,P,[E]), region(spain,E,[F,P]),
region(france,F,[E,I,S,B,WG,L]), region(belgium,B,[F,H,L,WG]),
region(holland,H,[B,WG]), region(west_germany,WG,[F,A,S,H,B,L]),
region(luxembourg,L,[F,B,WG]), region(italy,I,[F,A,S]),
region(switzerland,S,[F,I,A,WG]), region(austria,A,[I,S,WG])]).
 
colors(X,[red,yellow,blue,white]).

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

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

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

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

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

region(a, A, [B, C, D]), region(b, B, [A, C, E]),
region(c, C, [A, B, D, E, F]), region(d, D, [A, C, F]),
region(e, E, [B, C, F]), region(f, F, [C, D, E]).

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

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

color_region(region(Name, Color, Neighbors), Colors) ╛

select(Color, Coors, Colors1),

member(Neighbors, Colors1).

Цели select и members в зависимости от того, конкретизированы или нет их аргументы, могут либо производить генерацию вариантов, либо выполнять проверку.

Итогом выполнения программы о раскрашивании карты является конкретизация структуры данных - карты. Вызовы предикатов select и members могут рассматриваться как описания локальных ограничений. Предикаты либо генерируют предполагаемое решение посредством конкретизации элементов структуры, либо проверяют, удовлетворяют ли конкретизированные значения локальным ограничениям.

(c) M.N.Morozov, 1999.