4430
правок
Покрытие множества почти последовательными подмножествами: различия между версиями
Материал из WEGA
Покрытие множества почти последовательными подмножествами (посмотреть исходный код)
Версия от 17:01, 5 февраля 2021
, 5 февраля 2021→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 45: | Строка 45: | ||
Для каждой строки r | Для каждой строки <math>r \in R</math> обозначим за <math>c_{min}(r)</math> столбец в C, который покрывает r и имеет минимальный вес при соблюдении этого свойства. Для двух столбцов <math>c_{j_1}, c_{j_2} \in C</math> определим <math>X(c_{j_1}, c_{j_2}) := \{ c_{min}(r) | r \in c_{j_1} \and r \notin c_{j_2} \}</math>. Новое правило редукции данных будет выглядеть следующим образом. | ||
Усовершенствованное правило доминирования для столбцов: Пусть имеются два столбца | '''Усовершенствованное правило доминирования для столбцов:''' Пусть имеются два столбца <math>c_{j_1}, c_{j_2} \in C</math> и строка, которую покрывают оба столбца <math>c_{j_1}</math> и <math>c_{j_2}</math>, и если <math>w(c_{j_1}) \ge w(c_{j_2}) + \sum_{c \in X (c_{j_1}, c_{j_2}) w(c)}</math>, то <math>c_{j_1}</math> ''доминируется'' <math>\{ c_{j_2} \} \cup X(c_{j_1}, c_{j_2})</math>. Удалить столбец <math>c_{j_1}</math> из матрицы A. | ||
