4551
правка
Покрытие множества почти последовательными подмножествами: различия между версиями
Перейти к навигации
Перейти к поиску
Покрытие множества почти последовательными подмножествами (посмотреть исходный код)
Версия от 02:21, 29 января 2021
, 29 января 2021→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 42: | Строка 42: | ||
'''Правило доминирования для столбцов:''' если имеются два столбца <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. | '''Правило доминирования для столбцов:''' если имеются два столбца <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. | ||
В дополнение к этим двум правилам, столбец | В дополнение к этим двум правилам, столбец <math>c_{j_1} \in C</math> может также доминироваться подмножеством <math>C' \subseteq C</math> столбцов вместо одного столбца: если имеется подмножество <math>C' \subseteq C</math> и <math>w(c_{j_1}) \ge \sum_{c \in C'} w(c)</math>, и <math>\forall r \in R: r \in c_{j_1}</math> влечет <math>(\exist c \in C': r \in c)</math>, удалить <math>c_{j_1}</math> из A. К сожалению, поиск доминирующего подмножества C' для заданного множества <math>c_{j_1}</math> является NP-сложной задачей. Мекке и Вагнер [7] представили ограниченный вариант обобщенного правила доминирования столбцов. | ||