Проблема максимального покрытия

Задача максимального покрытия является классической проблемой в информатике , теории сложности вычислений и исследовании операций . Это задача, которая широко преподается в алгоритмах аппроксимации .

В качестве входных данных вам дается несколько наборов и число . Наборы могут иметь некоторые общие элементы. Вы должны выбрать большинство из этих наборов таким образом, чтобы было покрыто максимальное количество элементов, т.е. объединение выбранных наборов имело максимальный размер. к {\displaystyle к} к {\displaystyle к}

Формально (невзвешенный) максимальный охват

Экземпляр: Число и коллекция множеств . к {\displaystyle к} С = { С 1 , С 2 , … , С м } {\displaystyle S=\{S_{1},S_{2},\ldots ,S_{m}\}}
Цель: найти подмножество множеств, такое, что число покрытых элементов максимально. С ′ ⊆ С {\displaystyle S'\subseteq S} | С ′ | ≤ к {\displaystyle \left|S'\right|\leq k} | ⋃ С я ∈ С ′ С я | {\displaystyle \left|\bigcup _{S_{i}\in S'}{S_{i}}\right|}

Задача максимального покрытия является NP-трудной и не может быть приближена с точностью до стандартных предположений. Этот результат по существу соответствует коэффициенту приближения, достигнутому общим жадным алгоритмом, используемым для максимизации субмодулярных функций с ограничением мощности . [1] 1 − 1 е + о ( 1 ) ≈ 0,632 {\displaystyle 1-{\frac {1}{e}}+o(1)\approx 0,632}

Формулировка ИЛП

Задачу максимального покрытия можно сформулировать в виде следующей целочисленной линейной программы .

максимизировать ∑ е дж ∈ Э у дж {\displaystyle \sum _{e_{j}\in E}y_{j}} (максимизация суммы покрытых элементов)
при условии ∑ х я ≤ к {\displaystyle \sum {x_{i}}\leq k} ( выбрано не более наборов) к {\displaystyle к}
∑ е дж ∈ С я х я ≥ у дж {\displaystyle \sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}} (если то выбран хотя бы один набор ) у дж > 0 {\displaystyle y_{j}>0} е дж ∈ С я {\displaystyle e_{j}\in S_{i}}
у дж ∈ { 0 , 1 } {\displaystyle y_{j}\in \{0,1\}} (если тогда покрывается) у дж = 1 {\displaystyle y_{j}=1} е дж {\displaystyle e_{j}}
х я ∈ { 0 , 1 } {\displaystyle x_{i}\in \{0,1\}} (если то выбрано для обложки) х я = 1 {\displaystyle x_{i}=1} С я {\displaystyle S_{i}}

Жадный алгоритм

Алгоритм жадности для максимального покрытия выбирает наборы в соответствии с одним правилом: на каждом этапе выбирается набор, содержащий наибольшее количество непокрытых элементов. Можно показать, что этот алгоритм достигает коэффициента аппроксимации . [2] Результаты ln-аппроксимации показывают, что алгоритм жадности по сути является наилучшим возможным алгоритмом аппроксимации полиномиального времени для максимального покрытия, если только . [3] 1 − 1 е {\displaystyle 1-{\frac {1}{e}}} П = Н П {\displaystyle P=NP}

Известные расширения

Результаты о неаппроксимируемости применимы ко всем расширениям задачи максимального покрытия, поскольку они рассматривают задачу максимального покрытия как частный случай.

Задача о максимальном покрытии может быть применена к дорожно-транспортным ситуациям; одним из таких примеров является выбор автобусных маршрутов в сети общественного транспорта, которые должны быть оборудованы детекторами выбоин для максимального покрытия, когда доступно лишь ограниченное количество датчиков. Эта задача является известным расширением задачи о максимальном покрытии и впервые была исследована в литературе Джунаде Али и Владимиром Дьё. [4]

Утяжеленная версия

В версии с весом каждый элемент имеет вес . Задача состоит в том, чтобы найти максимальное покрытие, которое имеет максимальный вес. Базовая версия является частным случаем, когда все веса равны . е дж {\displaystyle e_{j}} ж ( е дж ) {\displaystyle w(e_{j})} 1 {\displaystyle 1}

максимизировать . (максимизировать взвешенную сумму охваченных элементов). ∑ е ∈ Э ж ( е дж ) ⋅ у дж {\displaystyle \sum _{e\in E}w(e_{j})\cdot y_{j}}
при условии ; ( выбирается не более наборов). ∑ х я ≤ к {\displaystyle \sum {x_{i}}\leq k} к {\displaystyle к}
∑ е дж ∈ С я х я ≥ у дж {\displaystyle \sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}} ; (если то выбран хотя бы один набор ). у дж > 0 {\displaystyle y_{j}>0} е дж ∈ С я {\displaystyle e_{j}\in S_{i}}
у дж ∈ { 0 , 1 } {\displaystyle y_{j}\in \{0,1\}} ; (если тогда покрывается) у дж = 1 {\displaystyle y_{j}=1} е дж {\displaystyle e_{j}}
х я ∈ { 0 , 1 } {\displaystyle x_{i}\in \{0,1\}} (если то выбрано для обложки). х я = 1 {\displaystyle x_{i}=1} С я {\displaystyle S_{i}}

Жадный алгоритм для взвешенного максимального покрытия на каждом этапе выбирает набор, содержащий максимальный вес непокрытых элементов. Этот алгоритм достигает коэффициента аппроксимации . [1] 1 − 1 е {\displaystyle 1-{\frac {1}{e}}}

Бюджетный максимальный охват

В версии с бюджетным максимальным покрытием не только каждый элемент имеет вес , но и каждый набор имеет стоимость . Вместо того, чтобы ограничивать количество наборов в покрытии, дается бюджет. Этот бюджет ограничивает общую стоимость покрытия, которое можно выбрать. е дж {\displaystyle e_{j}} ж ( е дж ) {\displaystyle w(e_{j})} С я {\displaystyle S_{i}} с ( С я ) {\displaystyle c(S_{i})} к {\displaystyle к} Б {\displaystyle Б} Б {\displaystyle Б}

максимизировать . (максимизировать взвешенную сумму охваченных элементов). ∑ е ∈ Э ж ( е дж ) ⋅ у дж {\displaystyle \sum _{e\in E}w(e_{j})\cdot y_{j}}
при условии ; (стоимость выбранных комплектов не может превышать ). ∑ с ( С я ) ⋅ х я ≤ Б {\displaystyle \sum {c(S_{i})\cdot x_{i}}\leq B} Б {\displaystyle Б}
∑ е дж ∈ С я х я ≥ у дж {\displaystyle \sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}} ; (если то выбран хотя бы один набор ). у дж > 0 {\displaystyle y_{j}>0} е дж ∈ С я {\displaystyle e_{j}\in S_{i}}
у дж ∈ { 0 , 1 } {\displaystyle y_{j}\in \{0,1\}} ; (если тогда покрывается) у дж = 1 {\displaystyle y_{j}=1} е дж {\displaystyle e_{j}}
х я ∈ { 0 , 1 } {\displaystyle x_{i}\in \{0,1\}} (если то выбрано для обложки). х я = 1 {\displaystyle x_{i}=1} С я {\displaystyle S_{i}}

Жадный алгоритм больше не будет выдавать решения с гарантией производительности. А именно, наихудшее поведение этого алгоритма может быть очень далеким от оптимального решения. Алгоритм аппроксимации расширяется следующим образом. Во-первых, определяем модифицированный жадный алгоритм, который выбирает набор, имеющий наилучшее отношение взвешенных непокрытых элементов к стоимости. Во-вторых, среди покрытий кардинальности находим наилучшее покрытие, которое не нарушает бюджет. Называем это покрытие . В-третьих, находим все покрытия кардинальности , которые не нарушают бюджет. Используя эти покрытия кардинальности в качестве отправных точек, применяем модифицированный жадный алгоритм, сохраняя наилучшее покрытие, найденное на данный момент. Называем это покрытие . В конце процесса приблизительное наилучшее покрытие будет либо , либо . Этот алгоритм достигает коэффициента аппроксимации для значений . Это наилучший возможный коэффициент аппроксимации, если только . [5] С я {\displaystyle S_{i}} 1 , 2 , . . . , к − 1 {\displaystyle 1,2,...,k-1} ЧАС 1 {\displaystyle H_{1}} к {\displaystyle к} к {\displaystyle к} ЧАС 2 {\displaystyle H_{2}} ЧАС 1 {\displaystyle H_{1}} ЧАС 2 {\displaystyle H_{2}} 1 − 1 е {\displaystyle 1-{1 \над е}} к ≥ 3 {\displaystyle k\geq 3} Н П ⊆ Д Т я М Э ( н О ( бревно ⁡ бревно ⁡ н ) ) {\displaystyle NP\subseteq DTIME(n^{O(\log \log n)})}

Обобщенный максимальный охват

В обобщенной версии максимального покрытия каждый набор имеет стоимость , элемент имеет разный вес и стоимость в зависимости от того, какой набор его покрывает. А именно, если покрывается набором, то вес равен , а его стоимость равна . Бюджет дается на общую стоимость решения. С я {\displaystyle S_{i}} с ( С я ) {\displaystyle c(S_{i})} е дж {\displaystyle e_{j}} е дж {\displaystyle e_{j}} С я {\displaystyle S_{i}} е дж {\displaystyle e_{j}} ж я ( е дж ) {\displaystyle w_{i}(e_{j})} с я ( е дж ) {\displaystyle c_{i}(e_{j})} Б {\displaystyle Б}

максимизировать . (максимизировать взвешенную сумму покрытых элементов в наборах, в которых они покрыты). ∑ е ∈ Э , С я ж я ( е дж ) ⋅ у я дж {\displaystyle \sum _{e\in E,S_{i}}w_{i}(e_{j})\cdot y_{ij}}
при условии ; (стоимость выбранных комплектов не может превышать ). ∑ с я ( е дж ) ⋅ у я дж + ∑ с ( С я ) ⋅ х я ≤ Б {\displaystyle \sum {c_{i}(e_{j})\cdot y_{ij}}+\sum {c(S_{i})\cdot x_{i}}\leq B} Б {\displaystyle Б}
∑ я у я дж ≤ 1 {\displaystyle \sum _{i}y_{ij}\leq 1} ; (элемент может быть покрыт только одним набором). е дж = 1 {\displaystyle e_{j}=1}
∑ С я х я ≥ у я дж {\displaystyle \sum _{S_{i}}x_{i}\geq y_{ij}} ; (если то выбран хотя бы один набор ). у дж > 0 {\displaystyle y_{j}>0} е дж ∈ С я {\displaystyle e_{j}\in S_{i}}
у я дж ∈ { 0 , 1 } {\displaystyle y_{ij}\in \{0,1\}} ; (если то охватывается множеством ) у я дж = 1 {\displaystyle y_{ij}=1} е дж {\displaystyle e_{j}} С я {\displaystyle S_{i}}
х я ∈ { 0 , 1 } {\displaystyle x_{i}\in \{0,1\}} (если то выбрано для обложки). х я = 1 {\displaystyle x_{i}=1} С я {\displaystyle S_{i}}

Обобщенный алгоритм максимального покрытия

Алгоритм использует концепцию остаточной стоимости/веса. Остаточная стоимость/вес измеряется относительно предварительного решения и представляет собой разницу стоимости/веса от стоимости/веса, полученной с помощью предварительного решения.

Алгоритм состоит из нескольких этапов. Во-первых, найти решение с помощью жадного алгоритма. В каждой итерации жадного алгоритма предварительное решение добавляется к набору, который содержит максимальный остаточный вес элементов, деленный на остаточную стоимость этих элементов вместе с остаточной стоимостью набора. Во-вторых, сравнить решение, полученное на первом шаге, с лучшим решением, которое использует небольшое количество наборов. В-третьих, вернуть лучшее из всех рассмотренных решений. Этот алгоритм достигает коэффициента аппроксимации . [6] 1 − 1 / е − о ( 1 ) {\displaystyle 1-1/eo(1)}

Примечания

  1. ^ ab GL Nemhauser , LA Wolsey и ML Fisher. Анализ приближений для максимизации субмодулярных функций множеств I, Математическое программирование 14 (1978), 265–294
  2. ^ Хохбаум, Дорит С. (1997). «Аппроксимация задач покрытия и упаковки: покрытие множеств, покрытие вершин, независимое множество и связанные с ними проблемы». В Хохбаум, Дорит С. (ред.). Алгоритмы аппроксимации для NP-трудных задач . Бостон: PWS Publishing Company. стр.  94–143 . ISBN 978-053494968-6.
  3. ^ Фейдж, Уриэль (июль 1998 г.). «Пороговое значение ln n для аппроксимации покрытия множеств». Журнал ACM . 45 (4). Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники: 634– 652. doi : 10.1145/285055.285059 . ISSN  0004-5411. S2CID  52827488.
  4. ^ Али, Джунаде; Дё, Владимир (2017). «Покрытие и размещение мобильных датчиков для транспортных средств на предопределенных маршрутах: жадный эвристический подход». Труды 14-й Международной совместной конференции по электронному бизнесу и телекоммуникациям. Том 2: WINSYS. С.  83–88 . doi :10.5220/0006469800830088. ISBN 978-989-758-261-5.
  5. ^ Хуллер, Самир; Мосс, Анна; Наор, Джозеф (Сеффи) (1999). «Проблема максимального покрытия с бюджетом». Information Processing Letters . 70 : 39–45 . CiteSeerX 10.1.1.49.5784 . doi :10.1016/S0020-0190(99)00031-9. 
  6. ^ Коэн, Реувен; Кацир, Лиран (2008). «Обобщенная задача максимального покрытия». Information Processing Letters . 108 : 15–22 . CiteSeerX 10.1.1.156.2073 . doi :10.1016/j.ipl.2008.03.017. 

Ссылки

Взято с "https://en.wikipedia.org/w/index.php?title=Проблема_максимального_покрытия&oldid=1265630441"