Введение
Тип вычислительной задачи
В комбинаторике и информатике задачи покрытия — это вычислительные задачи, которые спрашивают, покрывает ли некоторая комбинаторная структура другую, или каков должен быть размер структуры для этого. Задачи покрытия являются задачами минимизации и обычно представляются целочисленным линейным программированием, двойственными задачами к которым являются задачи упаковки. Наиболее известными примерами задач покрытия являются задача о покрытии множества, эквивалентная задаче о множестве-попадании, и её частные случаи — задача о покрытии вершин и задача о покрытии рёбер. Задачи покрытия допускают перекрытие покрывающих элементов. Если требуется покрыть что-либо элементами, не допускающими перекрытия, это называется разложением (уточнение).
In combinatorics and computer science, covering problems are computational problems that ask whether a certain combinatorial structure 'covers' another, or how large the structure has to be to do that. Covering problems are minimization problems and usually integer linear programs, whose dual problems are called packing problems. The most prominent examples of covering problems are the set cover problem, which is equivalent to the hitting set problem, and its special cases, the vertex cover problem and the edge cover problem. Covering Problems allows the covering primitives to overlap, If you want to cover something with primitives that don't overlap is called Decomposition (disambiguation)
Формулировка линейного программирования
В контексте линейного программирования любую задачу линейного программирования на минимизацию можно рассматривать как задачу покрытия, если коэффициенты в матрице ограничений, целевой функции и правой части неотрицательны. Более точно, рассмотрим следующую общую задачу целочисленного линейного программирования:
минимизировать при условиях
Такая задача целочисленного линейного программирования называется задачей покрытия, если для всех и
Интуиция: Предположим, что существует типов объектов, и каждый объект типа имеет связанную стоимость . Число указывает, сколько объектов типа мы приобретаем. Если ограничения удовлетворены, говорят, что получено покрытие (структуры, которые покрываются, зависят от комбинаторного контекста). Наконец, оптимальное решение вышеуказанной задачи целочисленного линейного программирования является покрытием минимальной стоимости.
minimize subject to Such an integer linear program is called a covering problem if for all and
Intuition: Assume having types of object and each object of type has an associated cost of The number indicates how many objects of type we buy. If the constraints are satisfied, it is said that is a covering (the structures that are covered depend on the combinatorial context). Finally, an optimal solution to the above integer linear program is a covering of minimal cost.
Виды проблем покрытия
Существуют различные типы задач о покрытии в теории графов, вычислительной геометрии и других областях; см. Категория: Задачи о покрытии. Также можно найти другие стохастические варианты этой задачи.
Покрытие сетями Петри
Для сетей Петри проблема покрытия определяется как вопрос о том, существует ли для заданной маркировки траектория сети, позволяющая достичь некоторой маркировки, большей или равной данной. "Более крупная" означает, что все компоненты не меньше соответствующих компонентов заданной маркировки, и хотя бы один из них строго больше.
Радужная покрышка
В некоторых задачах покрытия требуется, чтобы покрытие удовлетворяло дополнительным условиям. В частности, в задаче радужного покрытия каждый из исходных объектов имеет "цвет", и требуется, чтобы покрытие содержало ровно один (или не более одного) объект каждого цвета. Радужное покрытие исследовалось, например, для покрытия точек интервалами:
Дано множество J из n цветных интервалов на вещественной прямой и множество P точек на вещественной прямой. Подмножество Q множества J называется радужным, если оно содержит не более одного интервала каждого цвета. Множество интервалов J называется покрытием множества P, если каждая точка из P содержится хотя бы в одном интервале из Q. Задача радужного покрытия заключается в поиске радужного множества Q, являющегося покрытием для P.
Эта задача является NP-трудной (доказано сведением из линейной SAT).
Покрытие без конфликтов
Более общим понятием является покрытие без конфликтов. В этой задаче:
Есть множество O из m объектов и граф конфликтов GO на O. Подмножество Q множества O называется свободным от конфликтов, если оно является независимым множеством в GO, то есть никакие два объекта в Q не соединены ребром в GO. Радужное множество – это множество без конфликтов в особом случае, когда GO состоит из непересекающихся клик, где каждая клика представляет цвет. Задача покрытия множеством без конфликтов – это задача нахождения свободного от конфликтов подмножества O, являющегося покрытием P. Баник, Панолан, Раман, Сахлот и Саурабх доказывают следующее для специального случая, когда граф конфликтов имеет ограниченную древовидность:
Если задача геометрического покрытия является фиксированно-параметрически разрешимой (FPT), то задача геометрического покрытия без конфликтов также является FPT. Если задача геометрического покрытия допускает r-аппроксимационный алгоритм, то задача геометрического покрытия без конфликтов допускает аналогичный аппроксимационный алгоритм за FPT-время.