Problém pokrytí sadami
V teoretické informatice je problém set cover ( Set Cover problem v angličtině) problémem algoritmického obzvláště důležitého, protože je jedním z 21 NP-úplných problémů Karpa ( Karp 1972 ).
Vzhledem k tomu, set , můžeme říci, že prvek e je pokryt A pokud E patří do A . Vzhledem k množině U a rodině S podmnožin U je problém pokrýt všechny prvky U nejmenší možnou
podrodinou S.
Obecnější verzí je přiřadit váhy prvkům S a najít podrodinu minimální hmotnosti.
Úvodní příklad
Vezměme si soubor pěti prvků na víku . Zvažujeme podmnožiny: a . Snažíme se pokrýt všechny prvky podmnožinami. Například je to pokrytí, protože každý prvek je alespoň v jedné z podmnožin. Pokrytí, které používá nejméně podmnožin, je , takže právě toto pokrytí se snažíme vypočítat.
U={1,2,3,4,5}{\ displaystyle U = \ {1,2,3,4,5 \}}
{1,2},{3,4},{4,5}{\ displaystyle \ {1,2 \}, \ {3,4 \}, \ {4,5 \}}
{1,2,3}{\ displaystyle \ {1,2,3 \}}
{1,2},{3,4},{4,5}{\ displaystyle \ {1,2 \}, \ {3,4 \}, \ {4,5 \}}
{4,5},{1,2,3}{\ displaystyle \ {4,5 \}, \ {1,2,3 \}}![\ {4,5 \}, \ {1,2,3 \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6538a3947297113a0063a2527066656c4c436909)
Formální definice
Rozhodovací problém je následující:
Vstup: celé číslo , konečná množina a podmnožina množiny částí
k{\ displaystyle k}
U{\ displaystyle U}
S{\ displaystyle S}
U{\ displaystyle U}![U](https://wikimedia.org/api/rest_v1/media/math/render/svg/458a728f53b9a0274f059cd695e067c430956025)
Otázka: Je tam podmnožina z , o velikosti menší, než tak, že sjednocení elementů přítomných v podskupin se rovná ?
T{\ displaystyle T}
S{\ displaystyle S}
k{\ displaystyle k}
T{\ displaystyle T}
U{\ displaystyle U}
Přidružený problém s optimalizací spočívá v minimalizaci počtu použitých podmnožin.
V obecnější formě problému je každá sada spojena s váhou a cílem je minimalizovat součet hmotností přikrývky.
S{\ displaystyle S}
vs.(S){\ displaystyle c (S)}![c (S)](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a021deb4c9fafdf35d9cba096f724c4ce8ae604)
Algoritmické vlastnosti a složitost
NP-úplnost
Nastavený problém pokrytí je NP-hard (a NP-complete ve své rozhodovací formě). Jedním z klasických důkazů je snížení problému pokrytí vrcholů .
Formulace jako lineární program
Je plodné vyjádřit tento problém jako problém lineární optimalizace celého čísla .
Při převzetí proměnné pro každou podmnožinu je přirozený lineární program následující:
XS{\ displaystyle x_ {S}}![x_ {S}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b92b8756566d67fcc699fd6d3dc94b078dd18482)
minimalizovat:
|
∑S∈SXS{\ displaystyle \ sum _ {S \ v {\ mathcal {S}}} x_ {S}}
|
|
(Minimalizujte počet podmnožin)
|
jako :
|
∑S:E∈SXS⩾1{\ displaystyle \ sum _ {S \ tlustého střeva \ v S} x_ {S} \ geqslant 1}
|
∀E∈U{\ displaystyle \ forall e \ in {\ mathcal {U}}}
|
(Všechny položky jsou pokryty)
|
|
XS∈{0,1}{\ displaystyle x_ {S} \ v \ {0,1 \}}
|
∀S∈S{\ displaystyle \ forall S \ in {\ mathcal {S}}} .
|
(Každá podmnožina je buď v obálce, nebo ne)
|
Pokud ke každé sadě přiřadíme váhu , problém se stane:
vs.(S){\ displaystyle c (S)}![c (S)](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a021deb4c9fafdf35d9cba096f724c4ce8ae604)
minimalizovat:
|
∑S∈Svs.(S)⋅XS{\ displaystyle \ sum _ {S \ v {\ mathcal {S}}} c (S) \ cdot x_ {S}}
|
|
(Minimalizujte celkovou hmotnost podsestav)
|
jako :
|
∑S:E∈SXS⩾1{\ displaystyle \ sum _ {S \ tlustého střeva \ v S} x_ {S} \ geqslant 1}
|
∀E∈U{\ displaystyle \ forall e \ in {\ mathcal {U}}}
|
(Všechny položky jsou pokryty)
|
|
XS∈{0,1}{\ displaystyle x_ {S} \ v \ {0,1 \}}
|
∀S∈S{\ displaystyle \ forall S \ in {\ mathcal {S}}} .
|
(Každá podmnožina je buď v obálce, nebo ne)
|
Vztahy s dalšími algoritmickými problémy
Algoritmy
Aproximační algoritmy
Protože problém pokrytí sady je NP-úplný, bylo vynalezeno mnoho aproximačních algoritmů . Jako příklad můžeme uvést chamtivý algoritmus , algoritmus dvojího přizpůsobení, algoritmus zaokrouhlování z lineárního programu a schéma prvotního dvojího zapojení . Můžeme analyzovat chamtivý algoritmus pomocí metody multiplikativních vah . Celá mezera LP je logaritmická.
K dispozici jsou výsledky na obtíže sblížení problém, kvůli první až Lund a Yannakakis
pak FEIGE , pak Raz (en) , Safra , Alon a Moshkovitz. Tento poslední výsledek dává dolní mez , kde je konstanta, za předpokladu P odlišného od NP . Tyto výsledky jsou založeny na interaktivních důkazech a teorému PCP .
vs.⋅lnne{\ displaystyle c \ cdot \ ln {n}}
vs.{\ displaystyle c}![vs.](https://wikimedia.org/api/rest_v1/media/math/render/svg/86a67b81c2de995bd608d5b2df50cd8cd7d92455)
Heuristické algoritmy
Techniky řešení problémů pokrytí zahrnují přesné metody, matematické programování a heuristické a metaheuristické metody, genetické nebo memetické algoritmy . Mezi těmito metodami mohou některé metaheuristické algoritmy vyřešit velké případy problému pokrytí v rozumném čase. Jejich hybridizace s jinými technikami přináší ještě lepší výsledky, a to jak v referenčních aplikacích, tak v reálném světě.
Důležitost problému a historie
Tento kombinatorický optimalizační problém může souviset s širokou škálou aplikací v reálném světě, například s plánováním směn, umístěním zařízení, problémy městské logistiky a optimálním umístěním kamery.
Vijay Vazirani ve své knize ( Vazirani 2001 ) uvádí , že „studium tohoto problému umožnilo vývoj technik, které byly poté použity v celé oblasti [aproximačních algoritmů]“.
Bibliografie
- (en) Vijay Vazirani , Aproximační algoritmy , Springer Verlag , 2001 (poté 2003), 380 s. ( ISBN 978-3-540-65367-7 )
- (en) Richard M. Karp , „Reducibility Among Combinatorial Problems“ , Raymond E. Miller a James W. Thatcher, Complexity of Computer Computations , Plenum,1972( ISBN 978-1-4684-2003-6 , DOI 10.1007 / 978-1-4684-2001-2_9 , číst online ) , s. 85-103
- (en) Václav Chvátal , „ Chamtivá heuristika pro problém překrývání. ” , Mathematics of Operations Research , sv. 4, n o 3,1979, str. 233-235
-
Noga Alon , Dana Moshkovitz a Shmuel Safra , „ Algoritmická konstrukce souprav pro omezení k “, ACM Trans. Algoritmy , ACM, sv. 2 n o 22006, str. 153-177 ( ISSN 1549-6325 , DOI 10.1145 / 1150334.1150336 ).
-
Uriel Feige , „ Prahová hodnota ln n pro přiblížení zakrytí sady “, Journal of the ACM , vol. 45, n O 4,1998, str. 634-652 ( ISSN 0004-5411 , DOI 10.1145 / 285055.285059 ).
-
Carsten Lund a Mihalis Yannakakis , „ O tvrdosti aproximace minimalizačních problémů “, Journal of ACM , ACM, sv. 41, n o 5,1994, str. 960-981 ( ISSN 0004-5411 , DOI 10.1145 / 185675.306789 ).
-
Ran Raz a Shmuel Safra , „Test nízkého stupně pravděpodobnosti subkonstantní chyby a charakterizace PCP subkonstantní chyby pravděpodobnosti NP“ , v STOC '97: Sborník dvacátého devátého ročníku sympozia ACM o teorii výpočetní technika , ACM,1997( ISBN 978-0-89791-888-6 ) , str. 475-484.
Poznámky a odkazy
-
tento francouzský překlad je zejména přítomen v překladu ( Vazirani 2001 ) (viz obsah na stránce Nicolase Schabanela (překladatele) )
-
(in) Vijay Vazirani , aproximační algoritmy , Springer Verlag , 2001 (a 2003), 380 s. ( ISBN 978-3-540-65367-7 ), kap. 2, 13, 14 a 15.
-
Sanjeev Arora , Elad Hazan a Satyen Kale, „ Metoda aktualizace multiplikativní váhy: meta-algoritmus a aplikace “, Theory of Computing , sv. 8, n o 1,
2012, str. 121-164 ( číst online )
-
Lund a Yannakakis 1994
-
Feige 1998
-
Raz a Safra 1997
-
Alon, Moshkovitz a Safra 2006
-
Viz například úvod k článku Lunda a Yannakakise.
-
Mathieu Brévilliers , Julien Lepagnot , Lhassane Idoumghar , Maher Rebai a Julien Kritter , „ Algoritmy hybridní diferenciální evoluce pro optimální problém s umístěním kamery “, Journal of Systems and Information Technology , sv. 20, n O 4,2018, str. 446–467 ( ISSN 1328-7265 , DOI 10.1108 / JSIT-09-2017-0081 )
-
Maxime Pinard , Laurent Moalic , Mathieu Brévilliers , Julien Lepagnot a Lhassane Idoumghar , „ Memetická přístup pro Unicost který pokrývá problém “, Lecture Notes in Computer Science , sv. 12096 „Učení a inteligentní optimalizace (LION 2020)“,
2020, str. 233–248 ( ISSN 0302-9743 , DOI 10.1007 / 978-3-030-53552-0_23 )
-
E. Balas, „Třída problémů s umístěním, distribucí a plánováním: metody modelování a řešení“ , ve sborníku čínsko-amerického symposia o systémové analýze , Wiley, kol. "Wiley Series on Systems Engineering and Analysis",1983( ISBN 978-0-471-87093-7 ).
-
Reza Zanjirani Farahani , Nasrín Asgari , Nooshin Heidari , Mahtab Hosseininia a Mark Goh , „ pokrývat problémy v místě objektu: recenze “, Počítače & Industrial Engineering , vol. 62, n o 1,2012, str. 368-407 ( ISSN 0360-8352 , DOI 10.1016 / j.cie.2011.08.020 )
-
Marco Boschetti a Vittorio Maniezzo , „ Sada zahrnující matheuristiku pro problém logistiky města v reálném světě “, International Transactions in Operational Research , sv. 22, n o 1,2015, str. 169–195 ( ISSN 0969-6016 , DOI 10.1111 / itor.12110 )
-
Julien Kritter , Mathieu Brévilliers , Julien Lepagnot a Lhassane Idoumghar , „ O optimálním umístění kamer pro sledování a základním problému s krytem sady “, Applied Soft Computing , sv. 74,2019, str. 133–153 ( ISSN 1568-4946 , DOI 10.1016 / j.asoc.2018.10.025 )
-
V angličtině: problém, jehož studium vedlo k vývoji základních technik pro celý obor .
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">