Теперь для задачи раскраски карты применим разностные списки.

Карту представим полным разностным списком пар вида

название области – [список её соседей]

Пример карты:

[ A -[B,C,D], B -[A,C,E], C -[A,B,D,E,F], D -[A,C,F], E -[B,C,F], F -[E,C,D]]

Или, если не указывать раскрашенного (слева) соседа

[ A -[B,C,D], B -[C,E], C -[D,E,F], D -[F], E -[F]].

Программа перепишется:

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

paint_map([Цвет_Области - Цвета_Соседей|Незакрашенный_Остаток],

Список_Цветов):-

paint_region(Цвет_Области, Цвета_Соседей, Список_Цветов),

paint_map(Незакрашенный_Остаток, Список_Цветов).

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

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

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

Вызов для раскраски:

?- paint_map([A-[B,C,D], B-[A,C,E], C-[A,B,D,E,F], D-[A,C,F],
E-[B,C,F], F-[E,C,D]],[синий, красный, зеленый, желтый]).

A = синий,

B = красный,

C = зеленый,

D = красный,

E = синий,

F = желтый.

Другой вызов, когда нужно закрасить и обрамляющую область:

?- paint_map([M-[A,B,D,E,F], A-[B,C,D], B-[C,E], C-[D,E,F],
D-[F], E-[F]],[синий, красный, зеленый, желтый]).

M = синий,

A = красный,

B = D, D = зеленый,

E = красный,

F = желтый,

C = синий.

Разностные списки – другой взгляд на представление данных в прологе

Задачи для упражнений в раскраске

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