Problém přesného pokrytí
Pokrytí Přesný problém je NP-úplný kombinatorické optimalizační problém , který je jedním z Karp je 21 NP-úplných problémů .
Státy
Vzhledem k tomu, sadu U a sbírku z podmnožiny z U , An přesný pokrytí z U je podmnožina z taková, že některý prvek z U je součástí právě jednoho ze souborů .
Jinými slovy, přesné kryt U se o subseries z což je přepážka z U : sady prvků jsou disjunktní v párech, a jejich odbor je U .
Přesný Kryt je problém rozhodování o tom, zda je či není exaktní pokrytí množiny U a sbírka podmnožin U .
Přesný problém pokrytí je příkladem problému uspokojení omezení .
Příklad 1
Nechť U = {0, 1, 2, 3, 4} a let = { E , I , P } je kolekce tří sad:
- E = {0, 2, 4};
- I = {1, 3};
- P = {2, 3}.
Pak je dílčí kolekce = { E , I } přesným pokrytím.
Na druhou stranu, { E , P } není přesný obal: dostatečným důvodem je, že 1 není obsažena v žádné z těchto dvou sad, dalším dostatečným důvodem je, že 2 je obsažena v těchto dvou sadách.
Příklad 2
Nechť U = {1, 2, 3, 4, 5, 6, 7} je sada 7 prvků a nechť = { A , B , C , D , E , F } je kolekce 6 podmnožin U :
- A = {1, 4, 7};
- B = {1, 4};
- C = {4, 5, 7};
- D = {3, 5, 6};
- E = {2, 3, 6, 7}; a
- F = {2, 7}.
Potom subkolekce = { B , D , F } je přesným pokrytím U , protože každý prvek je obsažen přesně v jedné ze sad B = {1, 4}, D = {3, 5, 6} nebo F = {2, 7}.
Navíc { B , D , F } je jediné přesné pokrytí, jak ukazuje následující argument: Přesné pokrytí musí pokrývat 1 a A a B jsou jediné sady obsahující 1, takže přesné pokrytí musí obsahovat A nebo B , ale ne oba. Pokud přesný obal obsahuje A , potom neobsahuje B , C , E nebo F , protože každá z těchto sad má s A alespoň jednu společnou věc . Pak D je jediný zbývající sada, která je součástí přesného rozsahu, ale sběr { , D } nezahrnuje prvek 2. V závěru, není přesný kryt obsahující A . Na druhou stranu, pokud přesný obal obsahuje B , pak neobsahuje ani A, ani C , protože každá z těchto sad má s B alespoň jednu společnou věc . Pak D je jediná zbývající sada, která obsahuje 5, takže D musí být součástí přesného pokrytí. Pokud přesné pokrytí obsahuje D , pak neobsahuje E , protože D a E mají společné prvky 3 a 6. Pak F je jedinou zbývající sadou, která je součástí přesného pokrytí, a kolekce { B , D , F } je skutečně přesným pokrytím. Viz Knuthův X algoritmus pro maticovou verzi tohoto argumentu .
Maticová reprezentace
Jestliže = { S 1 , S 2 , ..., S m } je konečná sbírka m množin a U = { x 1 , x 2 , ..., x n } je konečný vesmír n prvků, pak přesné pokrytí problém může být reprezentován jako m x n matrice obsahuje pouze 0 a 1. Práce i -tý řádek matice představuje i -tý množina s i a j -tý sloupec matice představuje j -tý prvek x j . Vstup matrice v i- tém řádku a j- sloupec th je 1 v případě, že množina S i obsahuje prvek x j ; jinak je 0.
Vzhledem k takové matici je přesným pokrytím výběr řádků, takže každý sloupec má 1 přesně v jednom z vybraných řádků.
Jinými slovy, přesné pokrytí je výběr řádků, jejichž součet je řádek, který obsahuje pouze 1 s.
Příklad 3
Pokud v příkladu 2 výše, představujeme 6 sad v = { A , B , C , D , E , F } jako řádky a 7 prvků v U = {1, 2, 3, 4, 5, 6, 7} jako sloupce pak přesný problém pokrytí představuje matice 6 × 7:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|
| NA | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| B | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| VS | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
| D | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
| E | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| F | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
Stejně jako v příkladu 2 je výběr = { B , D , F } řádků řešením tohoto přesného problému pokrytí:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|
| B | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| D | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
| F | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
Zobecnění
Ačkoli standardní přesný problém pokrytí zahrnuje kolekci sad obsahujících prvky ve vesmíru U , struktura problému nezávisí na přítomnosti sad obsahujících prvky. Stejná struktura existuje, pokud mezi nimi existují dvě sady s určitým binárním vztahem .
Vzhledem k množině X , množině Y a binárnímu vztahu R mezi X a Y je přesné (zobecněné) pokrytí podmnožinou X * z X , takže každý prvek Y je R -1 - souvisí s přesně jedním prvkem X * . Zde R -1 je inverzní z R .
Obecně, R -1 omezen na Y x X * je funkce , to znamená, každý prvek Y je R -1 - vztahující se k právě jednoho prvku X * : jediný prvek X * , který „zahrnuje„konkrétní prvek Y .
Kromě toho, pokud R je zcela vlevo, to znamená, je-li každý prvek X je R v souvislosti s alespoň jedním prvkem z Y , pak R -1 omezen na Y x X * je surjektivní . (Stav v generalizované problémem, že R je zcela vlevo odpovídá stavu, ve standardní problém, že každý soubor v je neprázdná . Je zřejmé, že to neznamená, že rozdíl, zda je prázdná množina je součástí pokrytí nebo ne.)
V maticové reprezentaci zobecněného problému je relace R reprezentována maticí, prvky X jsou reprezentovány řádky matice a prvky Y jsou reprezentovány sloupci matice. Potom, stejně jako ve standardním problému, je přesným (zobecněným) pokrytím výběr řádků, takže každý sloupec má 1 přesně v jednom z vybraných řádků.
Standardní problém je speciální případ zobecněného problému, ve kterém množina X je soubor množin, množina Y je vesmír U prvků a binární relace R je „obsažený“ vztah mezi množinami a prvky. Potom R -1 omezeno na Y × X * je funkcí prvků směrem k sadám určujícím jedinečnou sadu v pokrytí, které obsahuje zadaný prvek. Navíc, pokud R je zcela vlevo, tj. pokud žádná sada není prázdná, pak R -1 omezeno na Y × X * je surjektivní funkce, tj. každý prvek v pokrytí obsahuje alespoň jeden prvek.
Příklad 4
Matici v příkladu 3 výše lze znovu interpretovat tak, aby představovala binární vztah „je obsažen v“ mezi množinou X = {1, 2, 3, 4, 5, 6} 6 prvků a kolekcí Y = { A , B , C , D , E , F , G } ze 7 sad:
- A = {1, 2}
- B = {5, 6}
- C = {4, 5}
- D = {1, 2, 3}
- E = {3, 4}
- F = {4, 5}
- G = {1, 3, 5, 6}
Zde platí stejná maticová reprezentace jako v příkladu 3, ale je označena odlišně:
| NA | B | VS | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 2 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
| 4 | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
| 5 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 6 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
Stejně jako v příkladu 3, je jedním z řešení pro výběr 2 nd , 4 th a 6 tého řádky matice:
| NA | B | VS | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| 2 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 4 | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
| 6 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
Ale na rozdíl od příkladu 3 interpretace zde ukazuje, že řešením je sada prvků X * = {2, 4, 6} tak, že každá sada v Y obsahuje přesně jeden prvek X * :
- A = {1, 2 }
- B = {5, 6 }
- C = { 4 , 5}
- D = {1, 2 , 3}
- E = {3, 4 }
- F = { 4 , 5}
- G = {1, 3, 5, 6 }
Jinými slovy, řešením je přesná protínající se množina . Opravdu, přesné problémy s pokrytím a přesné protínající se množinové problémy jsou navzájem dvojí, tj. v podstatě stejné.
Hledejte řešení
Algoritmus X Knuthův je rekurzivní , non-deterministický, do hloubky , brute-force traversal algoritmus , který najde všechna řešení tohoto problému přesném krytí.
Odkazy tanec (v) (v angličtině Tančící Links ), běžně známý jako DLX , je technika navrhla Knuth efektivně realizovat svůj algoritmus X v počítači. Taneční odkazy používají maticovou reprezentaci problému. Implementují matici jako řadu dvojnásobně propojených seznamů 1 v matici: každý prvek 1 má odkaz na 1 nahoře, dole, nalevo a napravo od sebe.
Je známo, že problém přesného pokrytí je NP-úplný .
Podrobnější příklady
Mnoho problémů lze snížit na problémy s přesným pokrytím, které lze poté vyřešit technikami, jako jsou taneční kravaty.
Například problém obkládání dané oblasti pentominy , problém osmi královen a řešení sudoku lze považovat za problém přesného pokrytí a vyřešen pomocí tanečních odkazů.
Dlažba Pentomino
Problém obložení daného povrchu pentominoes je příkladem problému přesného pokrytí.
Problém osmi královen
Problém osmi královen je příkladem problému přesného pokrytí.
Sudoku
Problém v Sudoku spočívá v přiřazení určitého počtu čísel (nebo číslic, hodnot, symbolů) buňkám (nebo čtvercům) v mřížce při splnění určitých omezení.
Ve standardních variantách sudoku 9 × 9 existují čtyři druhy omezení:
Řádek-sloupec: Každý průsečík řádku a sloupce, tj. Každé buňky, musí obsahovat přesně jedno číslo. Číslo řádku : Každý řádek musí obsahovat každé z 9 čísel přesně jednou. Číslo sloupce : Každý sloupec musí obsahovat každé z 9 čísel přesně jednou. Číslo rámečku: Každé políčko musí obsahovat každé z 9 čísel přesně jednou.Ačkoli se první omezení jeví jako triviální, je přesto nutné zajistit, aby na buňku bylo pouze jedno číslo.
Řešení sudoku je problém přesného pokrytí.
Přesněji řečeno, řešení sudoku je problém protínající se množiny, který je ekvivalentní problému přesného pokrytí (jako v příkladu 4 výše), když se na něj dívá jako na problém výběru možnosti, jako je to, že každá sada omezení obsahuje (tj. Je dosaženo) přesně jedna vybraná možnost. Ve výše uvedeném zápisu pro přesný (obecný) problém pokrytí je X množina možností, Y je množina množin omezení a R je binární relace „je obsažena v“.
Každé možné přiřazení konkrétního čísla konkrétní buňce je možností (nebo kandidátem). Když se sudoku hraje s tužkou a papírem, možnosti se často označují jako tužkové značky.
Ve standardních variantách sudoku 9 × 9, ve kterých je každé z buněk 9 × 9 přiřazeno jedno z 9 čísel, existuje 9 × 9 × 9 = 729 možností. Pomocí zřejmého zápisu pro řádky, sloupce a čísla lze možnosti označit takto: R1C1 # 1, R1C1 # 2,…, R9C9 # 9.
Skutečnost, že každý druh omezení zahrnuje přesně jednu věc, je tím, co dělá Sudoku přesným protínajícím se množinovým problémem. Omezení lze reprezentovat sadami omezení . Problém je vybrat možnosti tak, aby každá sada omezení obsahovala (tj. Dosáhla) přesně jednu vybranou možnost.
Ve standardních variantách sudoku 9 × 9 existují čtyři druhy omezení, které odpovídají čtyřem omezením:
Řádek-sloupec: Sada omezení řádků-sloupců obsahuje všechny možnosti pro průnik konkrétního řádku a sloupce, tj. Pro buňku. Například sada omezení pro řádek 1 a sloupec 1, které lze označit jako R1C1, obsahuje 9 možností pro řádek 1 a sloupec 1, ale s různými čísly: R1C1 = {R1C1 # 1, R1C1 # 2, R1C1 # 3, R1C1 # 4, R1C1 # 5, R1C1 # 6, R1C1 # 7, R1C1 # 8, R1C1 # 9}. Číslo řádku: Sada omezení počtu řádků obsahuje všechny možnosti pro konkrétní řádek a číslo. Například sada omezení pro řádek 1 a číslo 1, které lze označit R1 # 1, obsahuje 9 možností pro řádek 1 a číslo 1, ale z různých sloupců: R1 # 1 = {R1C1 # 1, R1C2 # 1, R1C3 # 1, R1C4 # 1, R1C5 # 1, R1C6 # 1, R1C7 # 1, R1C8 # 1, R1C9 # 1}. Číslo sloupce: Sada omezení počtu sloupců obsahuje všechny možnosti pro konkrétní sloupec a číslo. Například sada omezení pro sloupec 1 a číslo 1, které lze označit jako C1 # 1, obsahuje 9 možností pro sloupec 1 a číslo 1, ale z různých řádků: C1 # 1 = {R1C1 # 1, R2C1 # 1, R3C1 # 1, R4C1 # 1, R5C1 # 1, R6C1 # 1, R7C1 # 1, R8C1 # 1, R9C1 # 1}. Číslo krabice : Sada omezení čísla krabice obsahuje všechny možnosti pro konkrétní krabici a číslo. Například sada omezení pro rámeček 1 (v levém horním rohu) a číslo 1, které lze označit jako B1 # 1, obsahuje 9 možností pro buňky v rámečku 1 a číslo 1: B1 # 1 = {R1C1 # 1, R1C2 # 1, R1C3 # 1, R2C1 # 1, R2C2 # 1, R2C3 # 1, R3C1 # 1, R3C2 # 1, R3C3 # 1}.Protože existuje 9 řádků, 9 sloupců, 9 polí a 9 čísel, existuje 9 × 9 = 81 sad omezení řádků a sloupců, 9 × 9 = 81 sad omezení počtu řádků, 9 × 9 = 81 sad omezení sloupců -number and 9 × 9 = 81 sets of box-number constraints: 81 + 81 + 81 + 81 = 324 sets of constraints in all.
Stručně řečeno, standardní varianty sudoku 9 × 9 jsou přesným problémem protínajícím množinu s 729 možnostmi a 324 sadami omezení. Problém tedy může představovat matice 729 × 324.
I když je obtížné představit celou matici 729 × 324, obecnou povahu matice lze vidět z několika snímků:
|
|
|
|
Všimněte si, že soubor možností, R x C y # z, mohou být uspořádány jako 9 x 9 x 9 krychle 3 trojrozměrném prostoru s x , y a z, souřadnic . Takže každý řádek R x , sloupec C y nebo číslo # z je 9 × 9 × 1 „řez“ možností. Každá krabička B w je 9x3 × 3 „tuba“ možností. Každé R x C y řádek-sloupec množiny, R x # Z řádek číslo množiny, nebo C y # z sloupec číslo množiny je 9x1 x 1 „skupina“ možností. Každá sada omezení počtu polí B w # z je 3x3 × 1 „čtverec“ možností. A každá možnost R x C y # z je 1x1 × 1 „mini kostka“ skládající se z jediné možnosti.
Kromě toho je každá sada omezení nebo možností průnikem sad komponent. Například R1C2 # 3 = R1 · C2 · # 3, kde „·“ označuje množinu průsečíků.
Ačkoli jiné varianty sudoku mají různý počet řádků, sloupců, čísel a / nebo různých druhů omezení, všechny zahrnují možnosti a sady omezení, a lze je tedy považovat za přesné protínající se problémy sady.
Důkaz úplnosti NP
Ukázalo se, že přesný problém pokrytí je NP-úplný snížením oproti zabarvení grafu .
Poznámky a odkazy
- Viz například anglický web „Řešení hádanek Pentomino pomocí Backtracking“ (verze z 4. června 2011 v internetovém archivu ) .
Podívejte se také
Související články
externí odkazy
- (en) Michael Garey a David S. Johnson , Počítače a nezjistitelnost: Průvodce po teorii NP-úplnosti , WH Freeman,1979( ISBN 0-7167-1045-5 )A3.1: SP2: PŘESNÝ KRYT NA 3 SADY (X3C), s. 221 .
- (en) Karl Dahlke, „ NP Complete, Exact Cover “ , Math Reference Project (přístup 27. června 2006 )