Constraints:
Search, Domain
Reduction
Мищенко Николай
Содержание
Описание основных определений
Алгоритм сокращения области
Варианты выбора следующей вершины в поиске в
глубину
Распространение через уменьшенные области
Распространение через области, размер которых
уменьшен до одного значения
Различные ухищрения при выборе стартовой точки
Мищенко
2
Глоссарий
Domain — область принимаемых значений
Domain reduction algorithm — алгоритм сокращения
области
Constraint — ограничение (которое накладывается
на выбор области/значения)
Constraint propagation — ограничение,
накладываемые при распространении
Resource allocation problem — проблема
распределения ресурсов
Мищенко
3
Алгоритм сокращения
области
При рассмотрении следующей вершины в
DFS’е, на область принимаемых значений
могут накладываться ограничения
Таким образом область значений может
сокращаться
Если в итоге нет ни одного
удовлетворяющего значения, то мы выходим
из текущей ветки рекурсии
Мищенко
4
Виды ограничений
Никаких ограничений
Ограничение из-за соседства областей
Ограничение при распространении
Выбор уменьшенных областей
Выбор тех областей, размер которых был
уменьшен до 1
Мищенко
5
Соседские ограничения
При таком способе получается много
«тупиковых» ситуаций
Долгий поиск решения
Мищенко
6
Ограничение при
распространении
Выбираем сокращенные
области
Значительно уменьшает
время поиска решения
Малое количество
«тупиковых» ситуаций
Мищенко
7
Возможные «трюки»
Выбор стартовой точки поиска решения
может быть
Случайный
Выбирать область c минимальным количеством
ограничений
Выбирать область с максимальным количеством
ограничений
Как оказалось — самым удачным получился
последний вариант
Мищенко
8
Области применения
Основной областью применения являются
задачи, у которых есть проблема
распределения ресурсов
Например, задача о составлении расписания
полетов авиакомпании, когда количество
самолетов ограниченно
Мищенко
9
Спасибо за внимание!
