Термины
Переменная V – то, чему можно присвоить значение
Значение X – то, что можно присвоить переменной
Домен D – набор значений
Ограничение C – условие, наложенное на значения переменных
Задача раскраски карты в 4 цвета:
V – область
X – цвет
D – множество цветов, в которые можно раскрасить область
C – граничащие области не могут быть раскрашены в один цвет
Асирян
1
Алгоритм сокращения
домена
foreach DFS присваивания:
foreach рассматриваемой переменной :
foreach :
foreach ограничения , где :
if такого, что выполняется :
удалить из
if домен пуст:
вернуться
Асирян
2
Алгоритм сокращения
домена. Пример
Рассматриваемые переменные – соседи. Случайный порядок.
1
2
3
5
i
1
2
3
3
4
4
5
5
RGBY
RGBY
BRGY
BRGY
RGBY
RGBY
YBGR
YBGR
4
Асирян
3
Алгоритм сокращения
домена. Пример
Рассматриваемые переменные – соседи. Случайный порядок.
1
2
3
1=�
�
i
5
1
RGBY
2
RGBY
3
BRGY
4
YBGR
5
RGBY
4
Асирян
3
Алгоритм сокращения
домена. Пример
Рассматриваемые переменные – соседи. Случайный порядок.
1
2
3
1=�
�
i
5
1
RGBY
2
RGBY
3
BRGY
4
YBGR
5
RGBY
…
2=�
�
4
Асирян
3
Алгоритм сокращения
домена. Пример
Рассматриваемые переменные – соседи. Случайный порядок.
i
1
2
3
5
1
RGBY
2
RGBY
3
BRGY
4
BYGR
5
RGBY
1=�
�
…
2=�
�
…
3=�
�
4
Асирян
3
Алгоритм сокращения
домена. Пример
Рассматриваемые переменные – соседи. Случайный порядок.
i
1
2
3
4
Асирян
5
1
RGBY
2
RGBY
3
BRGY
4
BYGR
5
RGBY
1=�
�
…
2=�
�
…
3=�
�
…
4=�
�
3
Алгоритм сокращения
домена. Пример
Рассматриваемые переменные – соседи. Случайный порядок.
i
1
2
3
4
Асирян
5
1
RGBY
2
RGBY
3
BRGY
4
BYGR
5
RGBY
1=�
�
…
2=�
�
…
3=�
�
…
4=�
�
4=�
�
3
Алгоритм сокращения
домена. Пример
Рассматриваемые переменные – соседи. Случайный порядок.
i
1
2
3
4
Асирян
5
1
RGBY
2
RGBY
3
BRGY
4
BYGR
5
RGBY
1=�
�
…
2=�
�
…
3=�
�
…
4=�
�
4=�
�
5=�
�
3