Search,
Domain
Reduction:
Contributors’
Slides
Термины и
основные понятия
2
TERMS
Boundary – граница
Adjacent – смежный
Overlapping – перекрытие
Domain reduction – снижение размерности
Constraint – ограничение
Propogation – распространение
Savostin Peter
3
Глоссарий
Map coloring problem – задача о раскраске
карты
Depth first search – поиск в глубину
Constraint propagation – распространение
ограничений
To rotate the colour choices – выбирать цвета
по очереди
Domain reduction – сокращение домена
Галкина
4
Vocabulary
Depth first search – алгоритм поиска в
глубину
Enumerate – перечислять, точно
подсчитывать
Assignment – присваивание
Constraint – ограничение
Randomly generated example – пример,
сгенерированный случайным образом
Булгакова
5
Terms
map coloring – проблема раскраски карты в 4
цвета
local constraints – локальные ограничения
limit of the propagation – предел
распространения
demand reduction algorithm – алгоритм
уменьшения ограничений
domain reduction algorithm – алгоритм
сокращения областей
minimumА.В.
ground time – минимальное время,
Михайлишин
которое должен самолет провести на земле
Термины
Constraint - ограничения
Domain – множество возможных значений
Depth first search – поиск в глубину
Propagate – распространять
Струянский
7
Terms
Domain
Propagation - распространение
Constraint - ограничение
Елонов
8
Glossary
Constraint - ограничение
Domain reduction – уменьшение размерности
Essence of the idea – суть идеи
Propagation – распространение
Мартиросян
9
Domain reduction
algorithm
10
Термины
Переменная V – то, чему можно присвоить значение
Значение X – то, что можно присвоить переменной
Домен D – набор значений
Ограничение C – условие, наложенное на значения переменных
Задача раскраски карты в 4 цвета:
V – область
X – цвет
D – множество цветов, в которые можно раскрасить область
C – граничащие области не могут быть раскрашены в один цвет
Асирян
11
Glossary
Variable V: something that can have assignment
Value X: something that can be in assignment
Domain D: bag of values
Constraint C: limit on variable values
In example with states:
Variables = States
Values = Colors
Domains = Remaining color possibilities
Constraints = No states that share a boundary can have the same
color
Попов К.
12
VOCABULARY
VARIABLE V: something that can have an assignment
VALUE X: something that can be an assignment
DOMAIN D: bag of values
CONSTRAINT C: limit on variable values
EXAMPLE:
Variables: States
Values: colors
Domains: remaining color possibilities on a particular State
Constraint: no States with the same color can share a boundary
Кузьмин
13
Сокращение доменов.
Определения
Variable (v) – переменная: объект, которому
можно что-то присвоить
Value (x) – значение, которое можно
присвоить переменной
Domain (d) – домен, некоторый набор
значений
Constraint (c) – ограничение, налагаемое на
значения переменной
Галкина
14
Задача о раскраске
карты в 4 цвета
Переменные – штаты
Значения – цвета
(RGBY)
Домены – цвета, в
которые ещё можно
раскрасить штат
Ограничения –
соседние штаты
должны быть разного
цвета
Галкина
15
Domain reduction
algorithm terminology
Алгоритм сокращения доменов подходит для решения многих
задач (например, раскраска карт или управление ресурсами) и
потому оперирует абстрактными сущностями: переменными,
значениями, доменами и условиями.
Эти сущности можно наглядно показать на примере задачи
раскраски карты штатов в 4 цвета:
Условие: соседние
штаты должны
иметь разные цвета
Переменная
(= штат)
Шрамов
2
1
R
G
3
B
4
5
RGBO
Значения
(= цвета)
O
R
Backup (попали в
тупик => надо
попробовать другой
цвет на одном из
уровней выше)
Домен (= набор
доступных цветов)
16
Domain reduction
algorithm
FOR EACH DFS ASSIGNMENT
FOR EACH VARIABLE Vi CONSIDERED
FOR EACH Xi IN Di
FOR EACH CONSTRAINT C(Xi, Xj) WHERE Xj
Dj
IF ∄ Xj: C(Xi, Xj) SATISFIED
REMOVE Xi FROM Di
Попов К.
IF Di EMPTY BACKUP
17
Domain reduction
algorithm
Vocabulary:
Variable V: something that can have assignment
Value X: something that can be in assignment
Domain D: bag of values
Constraint C: limit on variable values
Pseudocode:
for each depth first search assignment
for each variable Vi considered
for each Xi in Di
for each constraint C (Xi, Xj) where Xj ϵ Dj
if ∄ Xj, such that, C (Xi, Xj) is satisfied
remove Xi from Di
if Di is empty
back up
Savostin Peter
18
Алгоритм сокращения
домена
Асирян
19
Procedure of coloring
states
For each DFS assignment
For each variable considered
For each
in
(domain)
For each constraint c ( , ) where
If satisfed
Remove from
If
is empty
Backup
Цзян Лэй
Domain Reduction algorithm
FOR EACH DFS ASSIGNMENT
FOR EACH VARIABLE Vi CONSIDERED
FOR EACH Xi IN Di
FOR EACH CONSTRAINT C (Xi,Xj) WHERE Xi∈Dj
IF ¬ ∃ Xj : C(Xi,Xj) SATISFIED
REMOVE Xi FROM Di
IF Di EMPTY – BACK UP
Variable V - something that can have assignment
Value X - something that can be in assignment
Domain D – bag of values
Constraint C – limit on variable values
Мартиросян
21
Domain Reduction
For each DFS assignment
For each variable vi considered
For each xi in Di
For each constraint C(xi, xj) where xj belongs Dj
If not exists xj satisfied C(xi, xj)
Remove xi from Di
R
G
Елонов
R
(RGBY)
G
(GBY)
B
(BY)
Y
(Y)
22
Алгоритм сокращения
домена. Пример
Асирян
23
Алгоритм сокращения
домена. Пример
Асирян
24
Алгоритм сокращения
домена. Пример
Асирян
25
Алгоритм сокращения
домена. Пример
Асирян
26
Алгоритм сокращения
домена. Пример
Асирян
27
Алгоритм сокращения
домена. Пример
Асирян
28
Алгоритм сокращения
домена. Пример
Асирян
29
Раскраска карты
Задача: дана карта штатов США, необходимо
закрасить каждый штат таким образом, чтобы
соседние штаты имели разный цвет.
Подходы к решению:
1) Раскрашивать, не обращая внимания на
цвет соседних штатов.
+: быстро
-: неправильно
Сальников
30
Раскраска карты
2) Раскрашивать, рассматривая возможные
цвета всех остальных штатов.
+: гарантирована корректность результата
-: требует миллиарды лет на выполнение
3) Раскрашивать, рассматривая возможные
цвета соседних штатов.
Результат: 9139 проверок.
Сальников
31
Раскраска карты
4) Раскрашивать, рассматривая соседние
штаты, у которых множество возможных
цветов меньше рассмотренных ранее.
Результат: 2623 проверок.
5) Раскрашивать, рассматривая соседние
штаты, у которых множество возможных
цветов уменьшилось до 1.
Результат: 980 проверок.
Сальников
32
Which variables to be considered in
domain reduction algorithm
1. Nothing
2. Assignment
3. Neighbors (9139 dead ends)
4. Propagate checking through V with D reduced
to 1 value (best in example)
5. Propagate checking through V with reduced D
6. Everything
Попов К.
33
DOMAIN REDUCTION ALGORITHM
for each DFS assignment
for each variable V considered
What to consider:
× Nothing => no checks => no results
× Everything => a lot of extra work => practically impossible
× Assignment => also practically impossible
~ Neighbors => a lot of work, but do good
✓ Propagate checking:
through V with reduced D => OK
through V with D reduced to 1 value => EVEN BETTER
Кузьмин
34
Ways to consider
Nothing
Assignment
Neighbors
Domain reduced to 1 value
Propagate checking through v with reduced D
Everything
Елонов
35
Способы учета
ограничений
Не учитывать ограничения
Учитывать уже присвоенные значения
Учитывать ограничения соседних
переменных
Распространение ограничений
Присваивание значений сначала
наиболее ограниченным переменным
Струянский
36
Порядок обхода переменных
Скорость работы алгоритма сокращения доменов может
сильно зависеть от порядка обхода переменных. Существует
три основных подхода:
в алфавитном порядке;
в порядке возрастания ограничений, накладываемых на
переменные (в случае раскраски карты – с краев);
в порядке убывания ограничений, накладываемых на
переменные (в случае раскраски карты – из центра).
На практике лучшее время показывает третий метод – следует
начинать с переменных, на которые накладывается больше
всего ограничений.
Шрамов
37
ПРИМЕР
ПРИМЕНЕНИЯ
38
Random Flight Example
Resource
s
Current
assignments
Dead
ends
Constraints
checked
No checks
10
20
0
0
Assignments
only
10
20
541
0
Neighbors only
10
20
0
200
Propagate
through
singleton
domains
10
20
0
210
Propagate
through reduced
domains
10
20
0
370
Булгакова
39
Random Flight Example
No checks
Assignments only
Neighbors only
Propagate through singleton domains
Propagate through reduced domains
Булгакова
40
Plane schedule problem
GT in
M stra
n
co
F1
BOS JFK
JFK BOS
F4
F5
GT in
M tr a
ns
co
not same time
constrain
F3
GT in
M tra
ns
co
F2
BOS JFK
JFK BOS
BOS
LAX
Михайлишин А.В.
*MGT - minimal
ground time
Составление
расписания
F1
BOS
JFK
минимальное время
на земле
JFK
F2
не в то же
самое время
F3
BOS
BOS
JFK
F4
F5
JFK
BOS
Рой
BOS
LAX
42
Составление
расписания
F1
BOS
JFK
минимальное время
на земле
JFK
F2
не в то же
самое время
F3
Самолет №1
Самолет №2
Самолет №3
BOS
BOS
JFK
JFK
F4
BOS
F5
Рой
BOS
LAX
43
Сравнение подходов
Рой
44
Сравнение подходов
Условия:
расписание самолетов
6 самолетов
невозможно выполнить
Neighbors
only
Propagate
through
singleton
domains
Propagate
through
reduced
domains
Тупики
1477
1477
1477
Проверки
38388
39108
67068
Рой
45
Сравнение подходов
Условия:
расписание самолетов
8 самолетов
Neighbors
only
Propagate
through
singleton
domains
Propagate
through
reduced
domains
Тупики
0
0
0
Проверки
170
182
319
Рой
46
Результат
Рой
47
Good resource allocation
Use most constraint first
Propagate through domains produced to a single
algorithm
If you want to figure out what the minimum
number of resources needed is, converge to a
narrow range where the search is taking a long
time, the number lies within the narrow range
Цзян Лэй
Вопросы
49
QUESTIONS
Should we arrange the states for our depth in the
order of least constrained to most constrained or
most constrained to least constrained?
Is resource planning problem is analogous to the map
coloring problem?
Savostin Peter
50
Questions
Should we arrange the states in the order of
least constrained to most constrained, or
most constrained to least constrained?
What constraint for states is used in
example?
Мартиросян
51
ВСЕМ БОЛЬШОЕ
СПАСИБО!
52