Графы и автоматы
Семейство ограничений предназначено для задач, в которых решение представляет собой маршрут на графе или последовательность состояний автомата. Ограничения семейства применяются, когда топология решения — какие именно дуги выбраны, в каком порядке проходятся состояния — сама является переменной.
В отличие от семейств «значения» и «булева логика», работающих с числами и истинностью независимых выражений, ограничения этого семейства задают условие связности: условие должно выполняться сразу для всей структуры решения в целом.
Дуги и циклы графа
Базовые объекты семейства — дуги ориентированного графа. Каждая дуга соединяет два узла (узлы идентифицируются порядковым номером) и связана с булевой переменной-индикатором использования. Дуга считается частью маршрута в найденном решении при истинности индикатора.
Дуги().Добавить— создаёт дугу с указанием узла-начала, узла-конца и булевой переменной-индикатора использования.ЦиклГрафа— требует, чтобы выбранные дуги (с истинными индикаторами) образовали гамильтонов цикл графа: последовательность, посещающую каждый узел ровно один раз и возвращающуюся в стартовый узел.МножественныеЦиклыГрафа— допускает несколько отдельных циклов при условии, что все циклы проходят через узел0(маршруты с возвратом в депо).
ИндикаторД1 = Модель.Переменные().ДобавитьБулеву();
ИндикаторД2 = Модель.Переменные().ДобавитьБулеву();
ИндикаторД3 = Модель.Переменные().ДобавитьБулеву();
Дуга1 = Модель.Дуги().Добавить(0, 1, ИндикаторД1);
Дуга2 = Модель.Дуги().Добавить(1, 2, ИндикаторД2);
Дуга3 = Модель.Дуги().Добавить(2, 0, ИндикаторД3);
// Из выбранных дуг должен сложиться цикл по всем узлам
Модель.Ограничения().ЦиклГрафа(
О2.Утилиты().Массив(Дуга1, Дуга2, Дуга3)
);
Решатель определяет значения булевых переменных так, чтобы выполнялись и ЦиклГрафа, и остальные ограничения модели.
Конечные автоматы
Когда решение представляет собой последовательность состояний, в которой переходы между состояниями подчинены правилам, применяется конечный автомат. Такая модель естественна для задач, в которых поведение системы во времени описывается явными правилами:
- запрет двух ночных смен подряд;
- требование выходного дня после двух ночных смен;
- последовательность этапов согласования документа;
- разрешённые переходы между режимами оборудования;
- допустимые комбинации статусов в маршруте обработки заявки.
Правила формализуются через конечный автомат — объект, описываемый набором допустимых переходов. У каждого перехода — начальное состояние, конечное состояние и уникальный номер для идентификации.
ПереходСостояния— создаёт объект-переход, описывающий допустимый переход из одного состояния в другое.КонечныйАвтомат— требует, чтобы последовательность активных переходов выводила автомат из заданного начального состояния в одно из допустимых конечных состояний.
Начальное состояние задаётся параметром ограничения. Решатель подбирает значения переменных-«активных переходов» так, чтобы получилась корректная цепочка от начала до одного из допустимых конечных состояний.
Когда применять автоматы вместо булевой логики
| Сценарий | Что использовать | Причина |
|---|---|---|
| Несколько точечных правил между переменными | Условные ограничения и булева логика | Каждое правило — короткое условие; цепочки не требуются. |
| Правила касаются последовательности — «после X запрещён Y», «через два дня обязателен Z» | Конечный автомат | Цепочка правил естественно описывается набором переходов; одна команда заменяет десяток условных ограничений. |
| Циклическое поведение (день недели, периодический график) | Конечный автомат | Циклы состояний и возвраты в начало — родная семантика автомата. |
Сравнение с моделью маршрутизации
Для классических задач коммивояжёра (TSP) и задач о маршрутах транспортных средств (VRP) с матрицей расстояний, депо, грузоподъёмностью и временными окнами рекомендуется применять модель маршрутизации — специализированную модель, ориентированную на этот класс задач.
Модель маршрутизации работает на более высоком уровне абстракции. Пользователь описывает прикладные сущности — узлы, транспортные средства, матрицы транзитов, размерности-накопители, ограничения, — а внутреннюю комбинаторную задачу решатель формирует автоматически. Поиск ведётся в две фазы: построение первого допустимого решения специализированной эвристикой (PathCheapestArc, Savings, Christofides) и улучшение решения метаэвристикой локального поиска (GuidedLocalSearch, TabuSearch). См. Параметры поиска модели маршрутизации.
Эти алгоритмы используют структурные свойства маршрута на графе и масштабируются до тысяч узлов без существенной потери качества решения. Та же задача, сформулированная средствами модели ограничений через ЦиклГрафа или МножественныеЦиклыГрафа, корректно решается, однако время поиска на промышленных размерностях растёт значительно быстрее. На задачах с десятками узлов разница в скорости обычно несущественна; на сотнях и тысячах узлов модель маршрутизации даёт качественные решения за секунды или минуты, тогда как модель ограничений может потребовать часов или не успеть в отведённое время поиска вовсе.
Модель ограничений на графах целесообразна в нестандартных задачах, не покрываемых моделью маршрутизации: например, маршрут одного объекта сочетается с правилами последовательности состояний (конечным автоматом), с условной активацией работ во времени (опциональными интервалами) или с упаковкой посещаемых грузов в ограниченное пространство.
Иллюстрация: правила автомата для сменного графика
Правила сменного графика недели:
- состояния:
1— день,2— ночь,3— выходной; - разрешены переходы: «день → ночь», «ночь → выходной», «выходной → день»;
- запрещены: переходы, не описанные явно (в частности, «ночь → день» — запрет работы сразу после ночной смены).
Правила формализуются тремя объектами ПереходСостояния. Для каждого дня недели регистрируется переменная — номер активного перехода; на массив этих переменных накладывается ограничение КонечныйАвтомат:
// Описание разрешённых переходов: (начальное_состояние, конечное_состояние, номер)
ДеньВНочь = Модель.Ограничения().ПереходСостояния(1, 2, 1);
НочьВВыходной = Модель.Ограничения().ПереходСостояния(2, 3, 2);
ВыходнойВДень = Модель.Ограничения().ПереходСостояния(3, 1, 3);
ВозможныеПереходы = О2.Утилиты().Массив(
ДеньВНочь,
НочьВВыходной,
ВыходнойВДень
);
// Для каждого дня недели — переменная-номер активного перехода
АктивныеПереходы = Модель.Переменные().ДобавитьМассивИзДиапазона(7, 1, 3, "переход_");
// Цепочка переходов выводит автомат из состояния "день" (1)
// в любое из допустимых конечных состояний {1, 2, 3}
Модель.Ограничения().КонечныйАвтомат(
1, // начальное состояние
О2.Утилиты().Массив(1, 2, 3), // допустимые конечные состояния
ВозможныеПереходы,
АктивныеПереходы
);
В найденном решении значения АктивныеПереходы определят последовательность переходов недели. Готовый рабочий пример сменного графика приведён на странице Составление графика работы сотрудников. Для классических задач обхода графа — Поиск оптимального маршрута (TSP).
Полный перечень методов
Полный набор методов работы с графами и автоматами приведён в разделах Программный интерфейс — Графы и Программный интерфейс — Автоматы.