4551
правка
Покрытие множества почти последовательными подмножествами: различия между версиями
Перейти к навигации
Перейти к поиску
Покрытие множества почти последовательными подмножествами (посмотреть исходный код)
Версия от 01:56, 29 января 2021
, 29 января 2021→Основные результаты
Irina (обсуждение | вклад) м (→Нотация) |
Irina (обсуждение | вклад) |
||
| Строка 32: | Строка 32: | ||
== Основные результаты == | == Основные результаты == | ||
Правила редукции данных | '''Правила редукции данных''' | ||
| Строка 38: | Строка 38: | ||
Правило доминирования для строк: если имеются две строки | '''Правило доминирования для строк:''' если имеются две строки <math>r_{i_1}, r_{i_2} \in R</math> и <math>\forall c \in C: r_{i_1} \in c</math> влечет <math>r_{i_2} \in c</math>, то <math>r_{i_1}</math> ''доминирует'' <math>r_{i_2}</math> (или, что то же самое, <math>r_{i_2}</math> доминируется <math>r_{i_1}). Удалить строку <math>r_{i_2}</math> из матрицы A. | ||
Правило доминирования для столбцов: если имеются два столбца cj1;cj2 2 C, W(CJ1) > W(CJ2), и 8r 2 R: r 2 cj1 влечет r 2 cj2, то cj2 доминирует cj1. Удалить столбец cj из матрицы A. | '''Правило доминирования для столбцов:''' если имеются два столбца cj1;cj2 2 C, W(CJ1) > W(CJ2), и 8r 2 R: r 2 cj1 влечет r 2 cj2, то cj2 доминирует cj1. Удалить столбец cj из матрицы A. | ||
В дополнение к этим двум правилам, столбец cj € С может также доминироваться подмножеством C0 С C столбцов вместо одного столбца: если имеется подмножество C'CC и w(cj1) — Pc2C0 w(c) и 8r 2 R: r 2 cj1 влечет (9c 2 C0: r 2 c), удалить cj1 из A. К сожалению, поиск доминирующего подмножества C0 для заданного множества cj1 является NP-сложной задачей. Мекке и Вагнер [ ] представили ограниченный вариант обобщенного правила доминирования столбцов. | В дополнение к этим двум правилам, столбец cj € С может также доминироваться подмножеством C0 С C столбцов вместо одного столбца: если имеется подмножество C'CC и w(cj1) — Pc2C0 w(c) и 8r 2 R: r 2 cj1 влечет (9c 2 C0: r 2 c), удалить cj1 из A. К сожалению, поиск доминирующего подмножества C0 для заданного множества cj1 является NP-сложной задачей. Мекке и Вагнер [ ] представили ограниченный вариант обобщенного правила доминирования столбцов. | ||