4551
правка
Декомпозиция на значительно удаленные пары: различия между версиями
Материал из WEGA
Декомпозиция на значительно удаленные пары (посмотреть исходный код)
Версия от 12:02, 6 марта 2018
, 6 марта 2018→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 21: | Строка 21: | ||
'''Метрическое пространство''' | '''Метрическое пространство''' | ||
Рассмотрим метрическое пространство <math>(S, \pi) \;</math>, где <math>S \;</math> – множество элементов, а <math>\pi \;</math> – функция расстояния, определенная на <math>S \times S \;</math>. Для любого подмножества <math>S_1 \subseteq S \;</math> [[диаметр]] <math>D_{\pi}(S_1) \;</math> (или <math>D(S_1) \;</math>, если <math>\pi \;</math> очевидно из контекста) множества <math>S \;</math> определяется как <math>max_{s_1, s_2 \in S_1} \; \pi (s_1, s_2)</math>. Расстояние <math>\pi(S_1, S_2) \;</math> между двумя множествами <math>S_1, S_2 \subseteq S \;</math> определяется как <math>max_{s_1 \in S_1, s_2 \in S_2} \; \pi (s_1, s_2)</math>. | Рассмотрим метрическое пространство <math>(S, \pi) \;</math>, где <math>S \;</math> – множество элементов, а <math>\pi \;</math> – функция расстояния, определенная на <math>S \times S \;</math>. Для любого подмножества <math>S_1 \subseteq S \;</math> [[диаметр]] <math>D_{\pi}(S_1) \;</math> (или <math>D(S_1) \;</math>, если <math>\pi \;</math> очевидно из контекста) множества <math>S \;</math> определяется как <math>max_{s_1, s_2 \in S_1} \; \pi (s_1, s_2)</math>. ''Расстояние'' <math>\pi(S_1, S_2) \;</math> между двумя множествами <math>S_1, S_2 \subseteq S \;</math> определяется как <math>max_{s_1 \in S_1, s_2 \in S_2} \; \pi (s_1, s_2)</math>. | ||
'''Декомпозиция значительно удаленных пар''' | '''Декомпозиция значительно удаленных пар''' | ||
В метрическом пространстве (S, | В метрическом пространстве <math>(S, \pi) \;</math> два непустых подмножества <math>S_1, S_2 \subseteq S \;</math> называются ''значительно удаленными с коэффициентом c'', если <math>\pi (S_1, S_2) \ge c \cdot max(D_{\pi}(S_1), D_{\pi} (S_2)) \;</math>. | ||
Согласно определению в [ ], для любых двух множеств A и B множество пар P = { | Согласно определению в [3], для любых двух множеств A и B множество пар <math>\mathcal{P} = \{ P_1, P_2, ..., P_m ]} \;</math>, где <math>P_i = (A_i, B_i) \;</math>, называется попарной [[Decomposition|декомпозицией]] (A, B) (или A, если A = B) в случае, если | ||
• Для всех значений индексов i верно Ai С A и Bi С B. | • Для всех значений индексов i верно Ai С A и Bi С B. | ||
