Труды КНЦ (Технические науки вып. 7/2023(14))

Труды Кольского научного центра РАН. Серия: Технические науки. 2023. Т. 14, № 7. С. 43-51. Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2023. Vol. 14, No. 7. P. 43-51 Рис. 3. Пример сети интервальных ограничений для задачи о действиях Фреда Приведем еще один пример [22], здесь, в отличие от первого, используются не только качественные, но и метрические временные ограничения. Пример 2. Джон и Фред работают в компании, имеющей локальный и главный офисы в Лос-Анджелесе. Обычно они работают в местном офисе, и в этом случае Джону требуется менее 20 мин, а Фреду — 15-20 мин, чтобы добраться до работы. Дважды в неделю Джон работает в главном офисе, и в этом случае его дорога на работу занимает не менее 60 мин. Сегодня Джон ушел из дома с 7:00 до 7:05, а Фред приехал на работу с 7:50 до 7:55. Также известно, что Фред и Джон встретились на светофоре по дороге на работу. Пусть хо будет вещественной переменной, обозначающей «начало времени» (снова 7:00). Пусть J = [xi, Х 2 ] — интервал времени, соответствующий поездке Джона на работу, а F = [хз, Х 4 ] — интервал времени, соответствующий поездке Фреда на работу, где xi, Х 2 , хз, Х 4 — действительные переменные, представляющие конечные точки интервала. На рисунке 4 показана сеть ограничений, фиксирующая временные отношения в приведенном выше тексте. Рис. 4. Пример сети с качественными и метрическими временными ограничениями Алгоритмы распространения темпоральных ограничений Алгоритмы, относящися к классу алгоритмов локальной совместности или просто совместности, преобразуют заданную задачу с ограничениями в эквивалентную задачу, выводя новые ограничения. Сами по себе новые ограничения не обязательно приводят к решению задачи удовлетворения ограничений, но способны существенно сократить пространство поиска решений; эта процедура сужает набор частных решений. В статье [21] Аллен представил алгоритм распространения ограничений для сетей интервальных ограничений, основанный на понятии совместности по путям (Path Consistency), который выполняется за время O(n3), где n — количество интервалов (узлов) в сети. При заданном TCP для n переменных его матрица ограничений M представляет собой матрицу размером n х n , элементами которой являются Mij — ограничения относительно пары переменных ( Xi ’ xj ) (в каждой временной структуре можно свести каждую TCP к эквивалентной, которая имеет ровно одно ограничение между каждой парой переменных). Решением матрицы ограничений М является кортеж («,-■■■ а„ такой, что для каждого (« >«,) удовлетворяет ограничению Mij. Если для некоторых г', J - n , получено М и~ ® , тогда делается вывод, что TCP является несовместной. © Зуенко А. А., Фридман О. В., 2023 47