set cover problem

set cover problem (tsz. set cover problems)

1. (informatika) A Set Cover Problem (halmaz­fedezeti probléma) egy klasszikus kombinatorikus optimalizálási feladat, mely az alábbi általános formában fogalmazható meg:

Adott:

1. Egy univerzumhalmaz ${\textstyle U=\{u_{1},u_{2},\dots ,u_{n}\}}$
2. Egy halmaz­sorozat ${\textstyle {\mathcal {S}}=\{S_{1},S_{2},\dots ,S_{m}\}}$, ahol minden ${\textstyle S_{j}\subseteq U}$.
3. (Opcionális) Minden ${\textstyle S_{j}}$-hez egy költség ${\textstyle c_{j}\geq 0}$ van rendelve.

Feladat: Válasszunk ki egy olyan részhalmazt ${\textstyle {\mathcal {C}}\subseteq {\mathcal {S}}}$, hogy

$${\displaystyle \bigcup _{S\in {\mathcal {C}}}S\;=\;U}$$

és a kiválasztott halmazok össze­költsége minimális legyen:

$${\displaystyle \min _{{\mathcal {C}}\subseteq {\mathcal {S}}}\;\sum _{S_{j}\in {\mathcal {C}}}c_{j}.}$$

Ha minden költség egyenlő (pl. ${\textstyle c_{j}=1}$), akkor minimum-kardinalitású (legkevesebb számú) halmazt keressük, ami lefedi ${\textstyle U}$.

Leggyakrabban 0–1 lineáris programként (ILP) szokás megfogalmazni:

• Döntési változók:

  $${\displaystyle x_{j}={\begin{cases}1,&{\text{ha }}S_{j}{\text{-t kiválasztjuk}},\\0,&{\text{egyébként}}.\end{cases}}}$$

• Célfüggvény:

  $${\displaystyle \min \sum _{j=1}^{m}c_{j}\,x_{j}.}$$

• Korlátok: minden univerzum­elemnek szerepelnie kell legalább egyszer:

  $${\displaystyle \forall \,i\in \{1,\dots ,n\}:\quad \sum _{j\,:\,u_{i}\in S_{j}}x_{j}\;\geq \;1.}$$

• Bináris változók: ${\textstyle \;x_{j}\in \{0,1\}.}$

• A döntési verzió („van-e halmazfedezet költség ≤ ${\textstyle K}$?”) NP-teljes.
• Az optimalizációs verzió NP-nehéz, és erős inapproximálhatósági eredmények is ismertek:
  • Polinomiális idő alatt ${\textstyle O(\log n)}$ faktornál jobb közelítés nem létezik (a probléma NP-teljes), kivéve ha ${\textstyle P=NP}$.
  • A Greedy-algoritmus ad egy ${\textstyle \displaystyle H_{n}=1+1/2+\dots +1/n=O(\ln n)}$ közelítést, ami aszimptotikusan optimális.

A legegyszerűbb és leggyakrabban használt közelítő eljárás:

1. Inicializálás:

   • ${\textstyle {\mathcal {C}}\leftarrow \varnothing }$,
   • ${\textstyle U'\leftarrow U}$ (a még le nem fedett elemek halmaza).

2. Lépések ismétlése, amíg ${\textstyle U'}$ nem üres:

   • Minden ${\textstyle S_{j}}$-hez számoljuk a „hatékonyságot”:

     $${\displaystyle \rho _{j}={\frac {|S_{j}\cap U'|}{c_{j}}}\,.}$$

   • Válasszuk ki azt a ${\textstyle S_{j^{*}}}$-t, amelyre ${\textstyle \rho _{j^{*}}}$ a legnagyobb (legtöbb új elemet fedi fel egységnyi költségért).

   • Tegyük be ${\textstyle {\mathcal {C}}}$-be, és távolítsuk el az általa lefedett elemeket ${\textstyle U'}$-ból.

3. Visszatérés: ${\textstyle {\mathcal {C}}}$.

Jóság A Greedy-algoritmus garantáltan ${\textstyle \displaystyle H_{n}}$-szeres (harmonikus szám) közelítést ad az optimálishoz képest.

• Exakt módszerek:
  • Branch & Bound, akár speciális vágóegyenletek (cutting planes).
  • Sok esetben kis és közepes méretű ${\textstyle n,m}$ problémákra használhatóak szakértői ILP-solverek (CPLEX, Gurobi).
• Heurisztikák és metaheurisztikák:
  • Lokális keresés (hill-climbing), szimulált hőkezelés (simulated annealing), genetikus algoritmusok.
  • Változatok: reál­értékű (LP-relaxáció utáni lekerekítés), kettős heurisztika, stb.

1. Hálózatos lefedettség – Routerek, bázisállomások elhelyezése úgy, hogy minden kliens kapcsolatban legyen.
2. Dokumentumkeresés – Minimális számú dokumentum kiválasztása, mely tartalmaz minden kulcsszót.
3. Tesztelés – Szoftver­tesztek halmazából a legkisebb készlet, amely lefedi az összes kódrészletet vagy funkciót.
4. Erőforrás- és műszerezés-optimalizálás – Szenzorok elhelyezése, hogy minden mérési pontot érzékelőkkel biztosítsunk.
5. Biológia, genomika – Minimális genekkészlet megtalálása, amely lefedi az összes kívánt funkciót vagy expressziós profilt.

• Weighted Set Cover: Az eredeti, költségalapú verzió, melyet fent írtunk le ${\textstyle c_{j}}$ súlyokkal.
• Partial Set Cover: Elég, ha a univerzumból csak legalább ${\textstyle k}$ elemet fedünk le („${\textstyle k}$-cover”).
• Set Multicover: Egyes elemeket többször is le kell fedni (puffer, redundancia miatt).
• Generalizált lefedések: – Pl. kétdimenziós területi lefedettség, piaci lefedettségi modellek („max-cover”).

A Set Cover egy NP-nehéz probléma, amely optimális lefedetést keres minimális költséggel. Bár exak­t megoldása nagy méretekben nem üzemeltethető, a Greedy-algoritmus egyszerű, gyors és ${\textstyle \displaystyle O(\ln n)}$-közelítést ad. Számtalan valós világ­beli alkalmazása van hálózatépítéstől a dokumentum­média-analízisen át a szoftvertesztelésig, ezért a kombinatorikus optimalizálás egyik legfontosabb és legtöbbet tanulmányozott problémája.

• set cover problem - Szótár.net (en-hu)
• set cover problem - Sztaki (en-hu)
• set cover problem - Merriam–Webster
• set cover problem - Cambridge
• set cover problem - WordNet
• set cover problem - Яндекс (en-ru)
• set cover problem - Google (en-hu)
• set cover problem - Wikidata
• set cover problem - Wikipédia (angol)