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

Для набора отношений на интервалах можно вывести самую сильную подразумеваемую связь an a a„ a между 0 и n , исследуя все возможные цепочки вывода между 0 и n выполнив пересечение всех результирующих композиций цепочек отношений. Каждая цепочка выводов накладывает ограничение на отношение, поэтому выводы объединяются путем их пересечения. Количество возможных цепочек растет очень быстро по мере увеличения количества отношений в коллекции. Темпоральные задачи удовлетворения ограничений Начало исследований, посвященных темпоральным CSP, было положено Джеймсом Алленом в его основополагающей статье [21]. Он предложил представлять качественные временные знания с помощью сетей интервальных ограничений. Сеть интервальных ограничений (рис. 3) представляет собой ориентированный граф, узлы которого — интервалы и ребра — помечены векторами, задающими ту или иную комбинацию из основных 13 бинарных качественных интервальных отношений. Введем некоторые определения и обозначачения, необходимые при дальнейшем изложении. Используем dom ( xi ) для обозначения области определения переменной xi . Определение 1. Пусть C — множество ограничений на переменные x\, ... , Xn. Множество решений C , обозначаемое Sol ( C ), представляет собой следующее множество: {(v 1 ,...,vn) Е dom(x 1 )x----xdom(xn): для любого c Е C, (v 1 ,...,vn) удовлетворяет условию c}. Каждый элемент Sol ( C ) называется решением множества ограничений C . Определение 2. Набор ограничений называется совместным или удовлетворяемым тогда и только тогда, когда множество его решений непусто. Определим стандартные понятия i-совместности, строгой i-совместности и глобальной совместности (или разложимости). Пусть C — множество ограничений на переменные x 1 , ... , хп. Для любого i такого, что 1 < i < n, обозначим множество ограничений в C как C(x 1 , ... , Xi), включающих только переменные x 1 , ... , Xi. Определение 3. Пусть C — множество ограничений на переменные x 1 , ... , Xn и 1 < i < n. C называется i-совместным тогда и только тогда, когда для каждого множества i — 1 различных переменных x 1 , ... , x^, все присваивания u = {x 1 ^ v 1 , ... , x z-1 ^ vz- 1 } такие, что v 1 Е dom(x\),..., v z-1 Е dom (x -), удовлетворяют ограничениям C(x 1 , ... , хм), и для каждой переменной xi, отличной от x^ ... , хм, существует значение viEdom(xi) такое, что u можно расширить до присваивания u' = u U {xi ^ vi}, удовлетворяющего ограничениям C(x 1 , ... , xm, xi). Говорят, что C строго i-совместно, если оно j -совместно для каждого j, 1 < j < i. C называется глобально совместным или разложимым тогда и только тогда, когда оно i - совместно для каждого i , 1 < i < n . Теперь определим стандартное понятие минимального набора ограничений. Минимальные наборы ограничений особенно важны для темпоральных CSP, потому что они делают явными все подразумеваемые бинарные ограничения. В сетевом представлении бинарных ограничений понятие минимального набора ограничений эквивалентно понятию минимальной сети. Определение 4. Множество ограничений C будет называться минимальным, если любое означивание двух переменных, которое удовлетворяет ограничениям, включающим только эти переменные, может быть расширено до решения C . В темпоральных CSP переменные используются для представления временных элементов (точек или интервалов), домены представляют собой временные структуры (обычно Z, Q или ^ д л я временных точек и набор интервалов над Z, Q или R для временных интервалов), а ограничения представляют собой временные отношения. Следуя по статье [21], многие исследователи сосредоточились на CSP (или, что то же самое, на сетях ограничений) как на средстве представления и рассуждений о темпоральных знаниях. Рассмотрим следующий пример [7]. Пример 1. «Фред читал газету во время завтрака. Он отложил газету и допил кофе. После завтрака он пошел гулять». Если мы используем «завтрак», «бумагу», «прогулку» и «кофе», чтобы описать соответствующие временные интервалы, то вся информация о действиях Фреда описывается сетью, представленной на рис. 3. Труды Кольского научного центра РАН. Серия: Технические науки. 2023. Т. 14, № 7. С. 43-51. Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2023. Vol. 14, No. 7. P. 43-51. © Зуенко А. А., Фридман О. В., 2023 46