4551
правка
Покрытие множества почти последовательными подмножествами: различия между версиями
Перейти к навигации
Перейти к поиску
м
Покрытие множества почти последовательными подмножествами (посмотреть исходный код)
Версия от 01:48, 29 января 2021
, 29 января 2021→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 11: | Строка 11: | ||
Дано: бинарная матрица A размера m x n и весовая функция w над столбцами A. | Дано: бинарная матрица A размера m x n и весовая функция w над столбцами A. | ||
Требуется: выбрать некоторые столбцы A с минимальным весом так, чтобы подматрица | Требуется: выбрать некоторые столбцы A с минимальным весом так, чтобы подматрица A' матрицы A, порождаемая этими столбцами, имела по крайней мере одно значение 1 в каждой строке. | ||
В общем случае задача SET COVER является NP-сложной [ ], однако она может быть решена за полиномиальное время для экземпляров, столбцы которых можно переставить таким образом, чтобы единицы в каждой строке появлялись последовательно – иначе говоря, для экземпляров, удовлетворяющих свойству последовательных единиц (C1P). | В общем случае задача SET COVER является NP-сложной [4], однако она может быть решена за полиномиальное время для экземпляров, столбцы которых можно переставить таким образом, чтобы единицы в каждой строке появлялись последовательно – иначе говоря, для экземпляров, удовлетворяющих ''свойству последовательных единиц'' (C1P). | ||
''[Свойство C1P может быть симметричным образом определено для столбцов, однако в данной статье рассматриваются строки. Задачу SET COVER над экземплярами со свойством C1P можно решить за полиномиальное время – например, при помощи подхода линейного программирования – поскольку соответствующие матрицы коэффициентов являются полностью унимодулярными | ''[Свойство C1P может быть симметричным образом определено для столбцов, однако в данной статье рассматриваются строки. Задачу SET COVER над экземплярами со свойством C1P можно решить за полиномиальное время – например, при помощи подхода линейного программирования – поскольку соответствующие матрицы коэффициентов являются полностью унимодулярными | ||
(см. [9])]'' | (см. [9])]'' | ||
Вдохновленные задачами, возникающими в связи с оптимизацией железнодорожного транспорта, Мекке и Вагнер [ ] рассматривают случай с экземплярами SET COVER, обладающими свойством «почти C1P». Наличие свойства «почти С1Р» означает, что соответствующие матрицы похожи на матрицы, сгенерированные следующим образом: начиная с матрицы, обладающей свойством С1Р, и случайным образом заменяя определенный процент единиц на нули [ | Вдохновленные задачами, возникающими в связи с оптимизацией железнодорожного транспорта, Мекке и Вагнер [7] рассматривают случай с экземплярами SET COVER, обладающими свойством «почти C1P». Наличие свойства «почти С1Р» означает, что соответствующие матрицы похожи на матрицы, сгенерированные следующим образом: начиная с матрицы, обладающей свойством С1Р, и случайным образом заменяя определенный процент единиц на нули [ 7. Напротив, с точки зрения Руфа и Шобель [8], наличие свойства «почти С1Р» означает, что среднее количество блоков последовательных единиц в строке значительно меньше количества столбцов матрицы. В данной статье будут приведены некоторые полученные ими результаты. | ||
== Нотация == | == Нотация == | ||