4551
правка
Покрытие множества почти последовательными подмножествами: различия между версиями
Перейти к навигации
Перейти к поиску
м
Покрытие множества почти последовательными подмножествами (посмотреть исходный код)
Версия от 19:55, 21 января 2021
, 21 января 2021→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Множество представителей == Постановка задачи == Задача пок…») |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача покрытия множества SET COVER получает на вход множество R, состоящее из m элементов, множество C из n подмножеств R и весовую функцию w: C | Задача покрытия множества SET COVER получает на вход множество R, состоящее из m элементов, множество C из n подмножеств R и весовую функцию <math>w: C \to \mathbb{Q}</math>. Задача заключается в выборе подмножеств <math>C' \subseteq C</math> с минимальным весом, объединение которых содержит все элементы R. | ||
Множества R и C могут быть представлены в виде бинарной матрицы A размера m x n, включающей строку для каждого элемента в R и столбец для каждого подмножества R в C, где значение ячейки | Множества R и C могут быть представлены в виде бинарной матрицы A размера m x n, включающей строку для каждого элемента в R и столбец для каждого подмножества R в C, где значение ячейки <math>a_{i, j}</math> равно 1 в случае, если i-й элемент R является частью j-го подмножества C. Таким образом, задачу SET COVER можно сформулировать следующим образом. | ||