Введение
Коллекция подмножеств, таких что каждый элемент исходного множества содержится ровно в одном подмножестве. В математической области комбинаторики, при заданном наборе подмножеств множества , точное покрытие – это поднабор этих подмножеств, в котором каждый элемент содержится ровно в одном подмножестве. Точное покрытие является разновидностью покрытия. Оно является задачей класса NP (недетерминированным полиномиальным временем) и имеет множество применений, от оптимизации расписаний авиарейсов и облачных вычислений до проектирования электронных схем. Другими словами, является разбиением множества на подмножества, содержащиеся в . Задача поиска точного покрытия является разновидностью задачи удовлетворения ограничений. Элементы множества представляют собой варианты выбора, а элементы множества – ограничения. Задача точного покрытия включает в себя отношение принадлежности между подмножествами и элементами, но может быть представлена любым неоднородным отношением между набором вариантов выбора и набором ограничений. Например, задача точного покрытия эквивалентна задаче точного покрытия минимальным набором, матрице сопряженности или двудольному графу. В информатике задача точного покрытия – это задача принятия решения, определяющая, существует ли точное покрытие. Задача точного покрытия является NP-полной и входит в число 21 NP-полных задач Карпа. Она остаётся NP-полной даже в случае, когда каждое подмножество содержит ровно три элемента; эта ограниченная задача известна как точное покрытие тремя множествами, часто сокращаемое как X3C. Если в конкретном решении определённый вторичный столбец уже удовлетворён, то добавленная строка не требуется. Однако, если вторичный столбец не удовлетворён (что допустимо в обобщённой задаче, но не в стандартной), то добавленная строка может быть выбрана для обеспечения его удовлетворения. Но Кнут объясняет, что лучше работать непосредственно с обобщённой задачей, поскольку обобщённый алгоритм проще и быстрее: простое изменение его алгоритма X позволяет обрабатывать вторичные столбцы напрямую. Задача о восьми ферзях является примером обобщённой задачи точного покрытия, поскольку ограничения, соответствующие диагоналям шахматной доски, требуют максимального, а не точного количества ферзей.
In the mathematical field of combinatorics, given a collection of subsets of a set , an exact cover is a subcollection of such that each element in is contained in exactly one subset in One says that each element in is covered by exactly one subset in An exact cover is a kind of cover. It is non deterministic polynomial time (NP) complete and has a variety of applications, ranging from the optimization of airline flight schedules, cloud computing, and electronic circuit design. In other words, is a partition of consisting of subsets contained in
The exact cover problem to find an exact cover is a kind of constraint satisfaction problem. The elements of represent choices and the elements of represent constraints. An exact cover problem involves the relation contains between subsets and elements. But an exact cover problem can be represented by any heterogeneous relation between a set of choices and a set of constraints. For example, an exact cover problem is equivalent to an exact hitting set problem, an incidence matrix, or a bipartite graph. In computer science, the exact cover problem is a decision problem to determine if an exact cover exists. The exact cover problem is NP complete and is one of Karp's 21 NP complete problems. It is NP complete even when each subset in contains exactly three elements; this restricted problem is known as exact cover by 3 sets, often abbreviated X3C. If in a particular candidate solution a particular secondary column is satisfied, then the added row isn't needed. But if the secondary column isn't satisfied, as is allowed in the generalized problem but not the standard problem, then the added row can be selected to ensure the column is satisfied. But Knuth goes on to explain that it is better working with the generalized problem directly, because the generalized algorithm is simpler and faster: A simple change to his Algorithm X allows secondary columns to be handled directly. The N queens problem is an example of a generalized exact cover problem, as the constraints corresponding to the diagonals of the chessboard have a maximum rather than an exact queen count.
Примечательные примеры
Благодаря NP-полноте, любая задача из класса NP может быть сведена к задаче точного покрытия, которую затем можно решить с помощью методов, таких как алгоритм «Танцующие ссылки». Однако для некоторых известных задач сведение особенно простое. Например, задачу о покрытии доски пентамино и решение судоку можно рассматривать как задачи точного покрытия.
Проблема королевы Н.
Проблема N королев является примером обобщенной задачи точного покрытия. Задача включает в себя четыре типа ограничений:
Ранг: для каждого из N рангов должна быть ровно одна королева. Столбец: для каждого из N столбцов должна быть ровно одна королева. Диагонали: для каждой из 2N − 1 диагоналей должна быть не более одной королевы. Обратные диагонали: для каждой из 2N − 1 обратных диагоналей должна быть не более одной королевы. Следует отметить, что 2N рангов и столбцов формируют основные ограничения, а 4N − 2 диагоналей и обратных диагоналей формируют вторичные ограничения. Более того, поскольку каждая из первых и последних диагоналей и обратных диагоналей содержит только один квадрат на шахматной доске, их можно исключить, и таким образом можно уменьшить количество вторичных ограничений до 4N − 6. Матрица для задачи N королев тогда имеет N2 строк и 6N − 6 столбцов, каждая строка соответствует возможному размещению королевы на каждом поле шахматной доски, а каждый столбец – каждому ограничению.
Rank: For each of the N ranks, there must be exactly one queen. File: For each of the N files, there must be exactly one queen. Diagonals: For each of the 2N − 1 diagonals, there must be at most one queen. Reverse diagonals: For each of the 2N − 1 reverse diagonals, there must be at most one queen. Note that the 2N ranks and files form the primary constraints, while the 4N − 2 diagonal and reverse diagonals form the secondary constraints. Further, because each of first and last diagonals and reverse diagonals involves only one square on the chessboard, these can be omitted and thus one can reduce the number of secondary constraints to 4N − 6. The matrix for the N queens problem then has N2 rows and 6N − 6 columns, each row for a possible queen placement on each square on the chessboard, and each column for each constraint.