Кіріспе
Бастапқы жиынның әрбір элементі дәл бір кіші жиынға кіретін кіші жиындар жиынтығы. Комбинаторика саласында, егер жиынның кіші жиындарының жиынтығы берілсе, нақты жабу – бұл жиынның әрбір элементі дәл бір кіші жиынға кіретін кіші жиындардың ішкі жиыны. Бұл детерминистік емес полиномиалдық уақытта (NP) шешілетін толық проблема және әуе компанияларының рейстер кестелерін оңтайландыру, бұлтты есептеу және электрондық тізбектерді жобалау сияқты әртүрлі қолданыстарға ие. Басқаша айтқанда, нақты жабу – бұл жиынның кіші жиындарынан тұратын бөлінісі, олардың әрқайсысы жиынға кіреді. Нақты жабуды табу мәселесі – бұл шектеулерді қанағаттандыру мәселесінің бір түрі. Жиынның элементтері таңдауларды, ал жиынның элементтері шектеулерді көрсетеді. Нақты жабу мәселесі кіші жиындар мен элементтер арасындағы «кіреді» қатынасын қамтиды. Бірақ нақты жабу мәселесі таңдаулар және шектеулер жиыны арасындағы кез келген әртүрлі қатынас арқылы бейнеленуі мүмкін. Мысалы, нақты жабу мәселесі нақты соққы жиынтығы мәселесіне, инциденттік матрицаға немесе екі бөлікті графқа эквивалентті. Компьютер ғылымында нақты жабу мәселесі – нақты жабудың бар-жоғын анықтауға арналған шешімдік мәселе. Нақты жабу мәселесі NP-толық және Карптың 21 NP-толық мәселесінің бірі болып табылады. Бұл мәселе әр кіші жиында дәл үш элемент болған кезде де NP-толық болып қалады; бұл шектеулі мәселе 3 жиынмен нақты жабу деп аталады және көбінесе X3C деп белгіленеді. Егер белгілі бір кандидаттық шешімде белгілі бір қосымша баған қанағаттандырылса, онда қосылған қатар қажет емес. Бірақ егер қосымша баған қанағаттандырылмаса, бұл жалпыланған мәселеде рұқсат етілгенімен, стандартты мәселеде рұқсат етілмегенімен, онда баған қанағаттандырылсын үшін қосылған қатарды таңдауға болады. Бірақ Кнут жалпыланған мәселемен тікелей жұмыс істеудің жақсы екенін түсіндіреді, өйткені жалпыланған алгоритм қарапайым және жылдам: оның X алгоритміне жасалған қарапайым өзгеріс қосымша бағандарды тікелей өңдеуге мүмкіндік береді. N патшайымдар мәселесі – жалпыланған нақты жабу мәселесінің мысалы, өйткені шахмат тақтасының диагональдарына сәйкес келетін шектеулер нақты патшайымдар санына емес, ең көп патшайымдар санына қатысты.
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 класындағы кез келген мәселені дәл жабу проблемаларына келтіруге болады, олар Dancing Links сияқты техникалармен шешіледі. Дегенмен, кейбір белгілі мәселелер үшін келтіру өте тікелей болады. Мысалы, пентоминолармен тақтаны мозаикалау және Судокуды шешу мәселелері дәл жабу проблемалары ретінде қарастырылуы мүмкін.
N квин проблемасы
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.