Покрытие множества почти последовательными подмножествами: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 40: | Строка 40: | ||
'''Правило доминирования для строк:''' если имеются две строки <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>). Удалить строку <math>r_{i_2}</math> из матрицы A. | '''Правило доминирования для строк:''' если имеются две строки <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>). Удалить строку <math>r_{i_2}</math> из матрицы A. | ||
'''Правило доминирования для столбцов:''' если имеются два столбца | '''Правило доминирования для столбцов:''' если имеются два столбца <math>c_{j_1}, c_{j_2} \in C, w(c_{j_1}) \ge w(c_{j_2})</math>, и <math>\forall r \in R: r \in c_{j_1}</math> влечет <math>r \in c_{j_2}</math>, то <math>c_{j_2}</math> доминирует <math>c_{j_1}</math>. Удалить столбец <math>c_{j_1}</math> из матрицы 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-сложной задачей. Мекке и Вагнер [ ] представили ограниченный вариант обобщенного правила доминирования столбцов. | ||