Расслабленный перекресток

Расслаблено пересечение в м множества соответствует классическому пересечению множеств , за исключением того , что разрешено отдохнуть несколько комплектов, чтобы избежать пустого пересечения. Это понятие можно использовать для решения несовместимых проблем удовлетворения ограничений путем ослабления небольшого количества ограничений . Когда для оценки параметров рассматривается подход с ограниченной ошибкой , ослабленное пересечение позволяет быть устойчивым по отношению к некоторым выбросам .

Определение [ править ]

Д -relaxed пересечение т подмножеств из , обозначаемых является множеством всех , которые принадлежат ко всем -х, за исключением того , самым большим. Это определение проиллюстрировано на рисунке 1.${\ Displaystyle X_ {1}, \ точки, X_ {m}}$${\ displaystyle R ^ {n}}$${\ Displaystyle X ^ {\ {q \}} = \ bigcap ^ {\ {q \}} X_ {i}}$${\ Displaystyle х \ в R ^ {п}}$${\ displaystyle X_ {i}}$${\ displaystyle q}$

Рисунок 1. q -пересечение 6 наборов для q = 2 (красный), q = 3 (зеленый), q = 4 (синий), q = 5 (желтый).

Определять${\ displaystyle \ lambda (x) = {\ text {card}} \ left \ {i \ | \ x \ in X_ {i} \ right \}.}$

У нас есть${\ displaystyle X ^ {\ {q \}} = \ lambda ^ {- 1} ([mq, m]).}$

Таким образом, характеристика q-релаксированного пересечения является проблемой обращения множества .^[1]

Пример [ править ]

Рассмотрим 8 интервалов:${\ Displaystyle X_ {1} = [1,4],}$${\ Displaystyle X_ {2} = \ [2,4],}$${\displaystyle X_{3}=[2,7],}$${\displaystyle X_{4}=[6,9],}$${\displaystyle X_{5}=[3,4],}$${\displaystyle X_{6}=[3,7].}$

У нас есть

${\displaystyle X^{\{0\}}=\emptyset ,}$${\displaystyle X^{\{1\}}=[3,4],}$${\displaystyle X^{\{2\}}=[3,4],}$${\displaystyle X^{\{3\}}=[2,4]\cup [6,7],}$${\displaystyle X^{\{4\}}=[2,7],}$${\displaystyle X^{\{5\}}=[1,9],}$${\displaystyle X^{\{6\}}=]-\infty ,\infty [.}$

Расслабленное пересечение интервалов [ править ]

Расслабленное пересечение интервалов не обязательно интервал. Таким образом, мы берем интервальную оболочку результата. Если это интервалы, расслабленное пересечение может быть вычислено со сложностью m .log ( m ) с использованием алгоритма Марзулло . Для представления функции достаточно отсортировать все нижние и верхние границы m интервалов . Тогда легко получаем набор${\displaystyle X_{i}}$${\displaystyle \lambda }$

${\displaystyle X^{\{q\}}=\lambda ^{-1}([m-q,m])}$

что соответствует объединению интервалов. Затем мы возвращаем наименьший интервал, содержащий это объединение.

На рисунке 2 показана функция, связанная с предыдущим примером.${\displaystyle \lambda (x)}$

Рисунок 2. Функция принадлежности к множеству, связанная с 6 интервалами.

Расслабленное пересечение прямоугольников [ править ]

Чтобы вычислить q -релаксированное пересечение m блоков , мы спроецируем все m блоков относительно n осей. Для каждой из n групп по m интервалов мы вычисляем q -релаксированное пересечение. Мы возвращаем декартово произведение n результирующих интервалов.^[2] На рис. 3 показано 4-релаксирующее пересечение 6 прямоугольников. Каждая точка красного квадрата принадлежит 4 из 6 квадратов.${\displaystyle R^{n}}$

Рис. 3. Красный прямоугольник соответствует 4-ослабленному пересечению 6 прямоугольников.

Расслабленный союз [ править ]

Д -relaxed объединение определяется${\displaystyle X_{1},\dots ,X_{m}}$

${\displaystyle {\overset {\{q\}}{\bigcup }}X_{i}=\bigcap ^{\{m-1-q\}}X_{i}}$

Обратите внимание, что когда q = 0, расслабленное объединение / пересечение соответствует классическому объединению / пересечению. Точнее, у нас есть

${\displaystyle \bigcap ^{\{0\}}X_{i}=\bigcap X_{i}}$

и

${\displaystyle {\overset {\{0\}}{\bigcup }}X_{i}=\bigcup X_{i}}$

Закон Де Моргана [ править ]

Если обозначает дополнительный набор , мы имеем${\displaystyle {\overline {X}}}$${\displaystyle X_{i}}$

${\displaystyle {\overline {\bigcap ^{\{q\}}X_{i}}}={\overset {\{q\}}{\bigcup }}{\overline {X_{i}}}}$

${\displaystyle {\overline {{\overset {\{q\}}{\bigcup }}X_{i}}}=\bigcap ^{\{q\}}{\overline {X_{i}}}.}$

Как следствие

${\displaystyle {\overline {\bigcap \limits ^{\{q\}}X_{i}}}={\overline {{\overset {\{m-q-1\}}{\bigcup }}X_{i}}}=\bigcap ^{\{m-q-1\}}{\overline {X_{i}}}}$

Расслабление подрядчиков [ править ]

Пусть будет m контракторов для множеств , тогда${\displaystyle C_{1},\dots ,C_{m}}$ ${\displaystyle X_{1},\dots ,X_{m}}$

${\displaystyle C([x])=\bigcap ^{\{q\}}C_{i}([x]).}$

является подрядчиком и${\displaystyle X^{\{q\}}}$

${\displaystyle {\overline {C}}([x])=\bigcap ^{\{m-q-1\}}{\overline {C}}_{i}([x])}$

является подрядчиком , где${\displaystyle {\overline {X}}^{\{q\}}}$

${\displaystyle {\overline {C}}_{1},\dots ,{\overline {C}}_{m}}$

являются подрядчиками для

${\displaystyle {\overline {X}}_{1},\dots ,{\overline {X}}_{m}.}$

В сочетании с алгоритмом ветвей и границ , таким как SIVIA (Set Inversion Via Interval Analysis), можно вычислить q- релаксирующее пересечение m подмножеств .${\displaystyle R^{n}}$

Приложение для оценки ограниченной ошибки [ править ]

Д -relaxed пересечение может быть использовано для надежной локализации ^{[3] [4]} или для отслеживания.^[5]

Устойчивые наблюдатели также могут быть реализованы с использованием ослабленных пересечений, чтобы быть устойчивыми по отношению к выбросам.^[6]

Мы предлагаем здесь простой пример ^[7], чтобы проиллюстрировать метод. Рассмотрим модель, выход i- й модели которой определяется выражением

${\displaystyle f_{i}(p)={\frac {1}{\sqrt {2\pi p_{2}}}}\exp(-{\frac {(t_{i}-p_{1})^{2}}{2p_{2}}})}$

где . Предположим, что мы имеем${\displaystyle p\in R^{2}}$

${\displaystyle f_{i}(p)\in [y_{i}]}$

где и даны следующим списком${\displaystyle t_{i}}$${\displaystyle [y_{i}]}$

${\displaystyle \{(1,[0;0.2]),(2,[0.3;2]),(3,[0.3;2]),(4,[0.1;0.2]),(5,[0.4;2]),(6,[-1;0.1])\}}$

Наборы для разных изображены на рисунке 4.${\displaystyle \lambda ^{-1}(q)}$${\displaystyle q}$

Ссылки [ править ]