Maximális lefedettségi probléma - Maximum coverage problem

A maximális lefedettségi probléma klasszikus kérdés a számítástechnikában , a számítási komplexitás elméletben és a műveletek kutatásában . Ez egy közelítő algoritmusokban széles körben tanított probléma .

Bemenetként több halmazt és egy számot kap . A készletekben lehetnek közös elemek. A legtöbb ilyen halmazt úgy kell kiválasztania , hogy a maximális számú elem le legyen fedve, azaz a kiválasztott halmazok egyesítése maximális méretű legyen. ${\ displaystyle k}$${\ displaystyle k}$

Formálisan (súlyozatlan) maximális lefedettség

Példa: Szám és halmazok gyűjteménye .${\ displaystyle k}$${\ displaystyle S = \ {S_ {1}, S_ {2}, \ ldots, S_ {m} \}}$

Cél: Keresse meg a halmazok olyan részhalmazát , amely és a fedett elemek száma maximalizált.${\ displaystyle S '\ subseteq S}$${\ displaystyle \ bal | S '\ jobb | \ leq k}$${\ displaystyle \ left | \ bigcup _ {S_ {i} \ in S '} {S_ {i}} \ right |}$

A maximális lefedettségi probléma NP-kemény , és nem feltételezhető normál feltételezéseken belül . Ez az eredmény lényegében megegyezik a szubmoduláris függvények maximalizálására használt általános mohó algoritmus által elért közelítési aránnyal . ${\ displaystyle 1-{\ frac {1} {e}}+o (1) \ kb 0.632}$

ILP készítmény

A maximális lefedettségi probléma a következő egész lineáris programként fogalmazható meg .

maximalizálni	${\ displaystyle \ sum _ {e_ {j} \ itt: E} y_ {j}}$	(a fedett elemek összegének maximalizálása)
alávetve	${\ displaystyle \ sum {x_ {i}} \ leq k}$	(legfeljebb halmazok vannak kiválasztva) ${\ displaystyle k}$
	${\ displaystyle \ sum _ {e_ {j} \ in S_ {i}} x_ {i} \ geq y_ {j}}$	(ha legalább egy halmaz van kiválasztva) ${\ displaystyle y_ {j}> 0}$${\ displaystyle e_ {j} \ in S_ {i}}$
	${\ displaystyle y_ {j} \ in \ {0,1 \}}$	(ha majd fedi) ${\ displaystyle y_ {j} = 1}$${\ displaystyle e_ {j}}$
	${\ displaystyle x_ {i} \ in \ {0,1 \}}$	(ha a borítóhoz ezt választotta) ${\ displaystyle x_ {i} = 1}$${\ displaystyle S_ {i}}$

Mohó algoritmus

A mohó algoritmus a maximális lefedettséghez egy szabály szerint választ halmazokat: minden szakaszban válasszon egy halmazt, amely a legtöbb fedetlen elemet tartalmazza. Kimutatható, hogy ez az algoritmus közelítő arányt ér el . Az ln-közelítési eredmények azt mutatják, hogy a mohó algoritmus lényegében a lehető legjobb polinomiális idő-közelítő algoritmus a maximális lefedettséghez, hacsak nem . ${\ displaystyle 1-{\ frac {1} {e}}}$${\ displaystyle P = NP}$

Ismert kiterjesztések

A megközelíthetetlenségi eredmények a maximális lefedettségi probléma minden kiterjesztésére vonatkoznak, mivel a maximális lefedettségi problémát speciális esetként tartják fenn.

A maximális lefedettségi probléma alkalmazható a közúti közlekedési helyzetekre; az egyik ilyen példa annak kiválasztása, hogy a tömegközlekedési hálózat mely buszjáratait kell telepíteni kátyúérzékelőkkel a lefedettség maximalizálása érdekében, ha csak korlátozott számú érzékelő áll rendelkezésre. Ez a probléma a maximális lefedettség problémájának ismert kiterjesztése, és először Junade Ali és Vladimir Dyo vizsgálta meg az irodalomban.

Súlyozott változat

A súlyozott változatban minden elemnek van súlya . A feladat az, hogy keressen egy maximális fedést, amelynek maximális súlya van. Az alapverzió egy speciális eset, amikor minden súly megvan . ${\ displaystyle e_ {j}}$${\ displaystyle w (e_ {j})}$${\ displaystyle 1}$

maximalizálni . (a fedett elemek súlyozott összegének maximalizálása).${\ displaystyle \ sum _ {e \ in E} w (e_ {j}) \ cdot y_ {j}}$

alávetve ; (legfeljebb halmazok vannak kiválasztva). ${\ displaystyle \ sum {x_ {i}} \ leq k}$${\ displaystyle k}$

${\ displaystyle \ sum _ {e_ {j} \ in S_ {i}} x_ {i} \ geq y_ {j}}$; (ha legalább egy halmaz van kiválasztva).${\ displaystyle y_ {j}> 0}$${\ displaystyle e_ {j} \ in S_ {i}}$

${\ displaystyle y_ {j} \ in \ {0,1 \}}$; (ha majd fedi)${\ displaystyle y_ {j} = 1}$${\ displaystyle e_ {j}}$

${\ displaystyle x_ {i} \ in \ {0,1 \}}$(ha a borítóhoz ezt választotta).${\ displaystyle x_ {i} = 1}$${\ displaystyle S_ {i}}$

A súlyozott maximális lefedettség mohó algoritmusa minden szakaszban olyan készletet választ, amely a fedetlen elemek maximális súlyát tartalmazza. Ez az algoritmus közelítő arányt ér el . ${\ displaystyle 1-{\ frac {1} {e}}}$

Költségvetett maximális fedezet

A költségvetés szerinti maximális lefedettségű változatban nem csak minden elemnek van súlya , hanem minden készletnek ára is van . E korlátozások helyett a fedezetben szereplő halmazok száma költségvetést kap. Ez a költségvetés korlátozza a választható fedezet teljes költségét. ${\ displaystyle e_ {j}}$${\ displaystyle w (e_ {j})}$${\ displaystyle S_ {i}}$${\ displaystyle c (S_ {i})}$${\ displaystyle k}$${\ displaystyle B}$${\ displaystyle B}$

maximalizálni . (a fedett elemek súlyozott összegének maximalizálása).${\ displaystyle \ sum _ {e \ in E} w (e_ {j}) \ cdot y_ {j}}$

alávetve ; (a kiválasztott készletek költsége nem haladhatja meg ). ${\ displaystyle \ sum {c (S_ {i}) \ cdot x_ {i}} \ leq B}$${\ displaystyle B}$

${\ displaystyle \ sum _ {e_ {j} \ in S_ {i}} x_ {i} \ geq y_ {j}}$; (ha legalább egy halmaz van kiválasztva).${\ displaystyle y_ {j}> 0}$${\ displaystyle e_ {j} \ in S_ {i}}$

${\ displaystyle y_ {j} \ in \ {0,1 \}}$; (ha majd fedi)${\ displaystyle y_ {j} = 1}$${\ displaystyle e_ {j}}$

${\ displaystyle x_ {i} \ in \ {0,1 \}}$(ha a borítóhoz ezt választotta).${\ displaystyle x_ {i} = 1}$${\ displaystyle S_ {i}}$

A mohó algoritmus többé nem fog teljesítménygaranciával rendelkező megoldásokat előállítani. Nevezetesen, ennek az algoritmusnak a legrosszabb viselkedése nagyon messze lehet az optimális megoldástól. A közelítési algoritmus a következő módon bővül. Először definiáljon egy módosított mohó algoritmust, amely kiválasztja azt a halmazt , amely a legjobb arányban tartalmazza a fedetlen elemeket a költségekhez. Másodszor, a kardinalitás fedezetei között keresse meg a legjobb fedezetet, amely nem sérti a költségvetést. Hívja ezt a borítót . Harmadszor, keresse meg a kardinalitás minden olyan borítóját, amely nem sérti a költségvetést. A kardinalitás ezen fedőlapjait kiindulópontként használva alkalmazza a módosított mohó algoritmust, megőrizve az eddigi legjobb fedezetet. Hívja ezt a borítót . A folyamat végén a hozzávetőlegesen legjobb borító vagy vagy . Ez az algoritmus közelítő arányt ér el a (z) értékekhez . Ez a lehető legjobb közelítési arány, hacsak nem . ${\ displaystyle S_ {i}}$${\ displaystyle 1,2, ..., k-1}$${\ displaystyle H_ {1}}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle H_ {2}}$${\ displaystyle H_ {1}}$${\ displaystyle H_ {2}}$${\ displaystyle 1- {1 \ over e}}$${\ displaystyle k \ geq 3}$${\ displaystyle NP \ subseteq DTIME (n^{O (\ log \ log n)})}$

Általános maximális lefedettség

Az általánosított maximális lefedettségű változatban minden készletnek költségei vannak , az elemek súlya és költsége eltérő, attól függően, hogy melyik készlet fedezi. Nevezetesen, ha borítja beállítva súlya jelentése és annak költsége . A megoldás teljes költségére költségvetést adnak. ${\ displaystyle S_ {i}}$${\ displaystyle c (S_ {i})}$${\ displaystyle e_ {j}}$${\ displaystyle e_ {j}}$${\ displaystyle S_ {i}}$${\ displaystyle e_ {j}}$${\ displaystyle w_ {i} (e_ {j})}$${\ displaystyle c_ {i} (e_ {j})}$${\ displaystyle B}$

maximalizálni . (a fedett elemek súlyozott összegének maximalizálása a lefedett halmazokban).${\ displaystyle \ sum _ {e \ in E, S_ {i}} w_ {i} (e_ {j}) \ cdot y_ {ij}}$

alávetve ; (a kiválasztott készletek költsége nem haladhatja meg ). ${\ displaystyle \ sum {c_ {i} (e_ {j}) \ cdot y_ {ij}}+\ összeg {c (S_ {i}) \ cdot x_ {i}} \ leq B}$${\ displaystyle B}$

${\ displaystyle \ sum _ {i} y_ {ij} \ leq 1}$; (az elemet legfeljebb egy halmaz fedheti le).${\ displaystyle e_ {j} = 1}$

${\ displaystyle \ sum _ {S_ {i}} x_ {i} \ geq y_ {ij}}$; (ha legalább egy halmaz van kiválasztva).${\ displaystyle y_ {j}> 0}$${\ displaystyle e_ {j} \ in S_ {i}}$

${\ displaystyle y_ {ij} \ in \ {0,1 \}}$; (ha akkor lefedi a készlet )${\ displaystyle y_ {ij} = 1}$${\ displaystyle e_ {j}}$${\ displaystyle S_ {i}}$

${\ displaystyle x_ {i} \ in \ {0,1 \}}$(ha a borítóhoz ezt választotta).${\ displaystyle x_ {i} = 1}$${\ displaystyle S_ {i}}$

Általános maximális lefedettségi algoritmus

Az algoritmus a maradványköltség/súly fogalmát használja. A maradványköltséget/tömeget egy kísérleti megoldáshoz mérik, és ez a költség/súly különbsége a kísérleti megoldás által nyert költség/súlyhoz képest.

Az algoritmus több szakaszból áll. Először keressen megoldást mohó algoritmus segítségével. A mohó algoritmus minden iterációjához a kísérleti megoldást hozzá kell adni a készlethez, amely tartalmazza az elemek maximális maradványsúlyát osztva ezen elemek maradványköltségével, valamint a halmaz maradék költségével. Másodszor, hasonlítsa össze az első lépésben kapott megoldást a legjobb megoldással, amely kis számú készletet használ. Harmadszor, adja vissza a legjobbat az összes vizsgált megoldás közül. Ez az algoritmus közelítő arányt ér el . ${\ displaystyle 1-1/eo (1)}$

Kapcsolódó problémák

• A készletborítás problémája az, hogy az összes elemet a lehető legkevesebb készlettel fedje le.

Megjegyzések

Hivatkozások

• Vazirani, Vijay V. (2001). Közelítési algoritmusok . Springer-Verlag. ISBN 978-3-540-65367-7.

Külső linkek