Понятие разностного списка (Difference Lists)

Неполные и разностные списки

Неполные списки

Неполным списком называется список, который заканчивается свободной переменной
(а не пустым списком, как обычно).

Эта, казалось бы, искусственно выдуманная вещь получается, например, предикатом member при запросах вида:

?- member(1,L).

L = [1|_G208];

L = [_G207, 1|_G211];

L = [_G207, _G210, 1|_G214]

Yes

?- member(1,L), member(2,L).

L = [1, 2|_G226];

L = [1, _G225, 2|_G229];

L = [1, _G225, _G228, 2|_G232]

Yes

Объяснение же их практического применения можно извлечь из двух таких унификаций.

?- [1,2,3|[4,5]] = Y.

Y = [1, 2, 3, 4, 5];

No

?- [1,2,3|X] = [1, 2, 3, 4, 5].

X = [4, 5]

Yes

Понятие разностного списка (Difference Lists)

Разностным списком называется список A - B,
т.е. получающийся при «вычитании» из списка A списка B

И тогда, например,

[1,2,3,4,5]-[4,5] и [1,2,3]-[]

будут представлять один и тот же список [1,2,3].

Можно предложить такую запись:

[1,2,3|X] - X

(при этом X – должен быть списком).

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

8.3 Задача о раскраске карты

Замечательным примером использования разностных списков
является решение известной задачи о раскраске карты.

Имеется географическая карта и набор цветов. Надо раскрасить
карту так, чтобы соседние области были раскрашены в разные цвета.

Существует утверждение:

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

Предлагаемое решение будет основано на переборе с возвратами, т.е. для каждой области выбирается цвет, а затем выбираются (или проверяются) цвета для ее соседей.

8.3.1 Сначала решим задачу с помощью «привычных» списков

Определение любой области:

region(название_области, Цвет_Области, Цвета_Соседей)

где

название_области – это буква(константа), её обозначающая;

Цвет_Области – этот переменная, которой присвоен какой-то цвет раскраски;

Цвета_Соседей – это список раскрашенных соседей.

Примеры:

Область B: region(b, В, [А,С,E])

Область C: region(с, С, [A,B,D,E,F])

Цикл раскраски:

paint_map([ ], Список_Цветов).

Процесс раскрашивания останавливается, когда список для раскраски пуст.

paint_map([Region | Regions], Список_Цветов):-

paint_region(Region, Список_Цветов),

paint_map(Regions, Список_Цветов).

Переменная Cписок_Цветов - список перечисления всех цветов для раскраски.
(Задаётся для раскрашивания конкретной карты при вызове.)

Процедура раскраски каждой области:

paint_region(region(Название_области, Цвет_Области,Цвета_Соседей),Список_Цветов):-

select(Цвет_Области, Список_Цветов, Palette),

members(Цвета_Соседей, Palette).

Функция select при каждом вызове из Cписок_Цветов выбирает цвет, которым закрашивается по-порядку выбранная область (он присваивается переменной Цвет_Oбласти, оставляя для следующих «раскрасок» список цветов Palette.

Предикат members(List1,List2) выдаёт true, если каждый элемент из первого списка List1 является элементом второго списка (раскрашены цветами, разрешёнными для раскраски соседей). В противном случае – false.

members([],Palette).

members([X|Y],Palette):- member (X,Palette), members(Y,Palette).

Пример раскраски.

paint_map([ region(а, A, [B, C, D]),

region(b, B, [A, C, E]),

region(с, C, [A, B, D, E, F]),

region(d, D, [A, C, F]),

region(e, E, [B, C, F]),

region(f, F, [C, D, E]) ],

[синий, красный, зеленый, желтый]).

Первый ответ (их должно быть много) таков:

A = синий,

B = красный,

C = зеленый,

D = красный,

E = синий,

F = желтый;

Дата добавления: 2015-09-07