МИИ_8_17 (C) (лекции)

2020-08-25СтудИзба

Описание презентации

Файл "МИИ_8_17 (C)" внутри архива находится в папке "лекции". Презентация из архива "лекции", который расположен в категории "". Всё это находится в предмете "(мии) методы искусственного интеллекта" из 11 семестр (3 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр презентации онлайн

Текст из слайда

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

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5057
Авторов
на СтудИзбе
455
Средний доход
с одного платного файла
Обучение Подробнее