K-střed
Problémem k -centre ( k-centrum problém v angličtině) je problémem z kombinatorické optimalizace , pobočka algoritmu . Problém lze neformálně popsat takto: vzhledem k n městům je nutné otevřít hasičskou stanici v k městech tak, aby byla minimalizována vzdálenost mezi každým městem a nejbližší požární stanicí.
Formálnější je to, vzhledem k množině bodů V , výběru podmnožiny k bodů, nazývaných středy, tak, aby byla minimalizována maximální vzdálenost od bodů V k nejbližšímu středu. Ve většině případů implicitně považujeme prostor za metrický , problém je pak přirozeně vyjádřen jako problém na grafu, jehož hrany mají váhy respektující trojúhelníkovou nerovnost .
Tento problém je studován hlavně z hlediska aproximace . Existuje několik variant s konkrétními metrikami nebo jinými náklady, které je třeba minimalizovat. Odlišnou aplikací od umístění instalace je rozdělení dat (shlukování) .
Formální definice
Problém je v metrickém případě vyjádřen následovně.
Vzhledem k celému číslu k a úplnému neorientovanému grafu G = ( V , E ) vzdálenost d ( v i , v j ) ∈ N respektuje nerovnost trojúhelníku, najděte podmnožinu S ⊆ V s | S | = K , který minimalizuje: . Jinými slovy, uvažujeme problém optimalizace, jehož objektivní funkcí je .
Obecný případ bez metriky je málo studován, protože je příliš obtížný i z hlediska aproximace. Přesněji řečeno, bez předpokladu není problém v APX . Zbytek článku se implicitně zabývá metrickým případem.
Složitost
Problém je ve své verzi problémového rozhodnutí NP-úplný .
Přiblížení
Existují aproximační algoritmy poměru 2, a pokud se P liší od NP, je tento výsledek optimální.
Chamtivý algoritmus
Následující hladový algoritmus byl navržen Gonzalez v roce 1985. To je někdy nazýváno nejvzdálenější první průchod .
- Vyberte libovolný první vrchol a udělejte z něj střed.
- Proveďte k-1 krát:
- Najděte vrchol, jehož vzdálenost k již otevřeným středům je maximální
- Udělejte z toho centrum.
Vypočítané řešení je v nejhorším případě poloviční jako optimální řešení. Rychle to dokážeme. Na konci algoritmu nechť r je maximální vzdálenost od bodu ke středu a nechť p bude takový bod. Nechť S je množina skládající se z center a p . Sada S má k + 1 bodů alespoň r od sebe navzájem. Pak v optimálním řešení musí alespoň dva body S sdílet stejný střed (v optimálním řešení je více bodů v S než středech). Podle trojúhelníkové nerovnosti je alespoň jeden z těchto bodů sdílejících stejný střed ve vzdálenosti r / 2 od středu.
Časová složitost algoritmu je O (nk) .
Prahová metoda
Můžeme získat 2-aproximaci prahovou metodou ( nazývanou také parametrické prořezávání ). Spočívá v testování všech možných řešení: optimální hodnota je cena přítomná na hraně, počet hran je polynomický a pro každou hodnotu můžeme provést polynomický test. Test spočívá v odstranění hran větší váhy a kontrole, zda můžeme v prořezaném grafu získat 2-aproximaci.
Tento algoritmus je způsoben Hochbaumem a Shmoysem.
Obtížnost aproximace
Problém je NP obtížně přístupný pro poměr menší než 2. Tento výsledek je způsoben Hsu a Nemhauserem. Důkaz uvedený níže je redukcí problému dominantní množiny .
Nechť je instance (G, k) pro problém dominantní množiny. Transformujeme jej na instanci G ' , kompletní graf se stejnými vrcholy, s následujícími váhami na okrajích: 1 pro hrany G a 2 pro ostatní. Pokud má dominantní množina velikost menší než k, pak G ' má k-středové řešení nákladu 1, jinak řešení nákladu 2. Aproximační algoritmus poměru menší než 2 tedy dává odpověď na problém dominantní množiny což je samo o sobě NP-tvrdé .
Speciální případy
Pokud je graf rovinný, existuje polynomiální časové aproximační schéma problému.
Varianty, související problémy a aplikace
Zvláštní případ je, když metrika je euklidovská , někdy nazývaná geometrickým středem k .
Klasickým způsobem, jak problém upravit, je přidání různých kapacit do center. Pokud je tedy určitý uzel zvolen jako střed, může sloužit pouze omezenému počtu sousedů.
Problém k-medián používá stejný rámec, ale s jinou funkcí, kterou je třeba minimalizovat. V problému umístění zařízení ( problém umístění zařízení ) nahradíme parametr k náklady na otevření a připojení.
Výpočet k -centra umožňuje rozdělit data . Vzdálenosti pak představují podobnosti, jako u k-means .
Poznámky a odkazy
- Francouzský překlad pochází z překladu (en) Vijay Vazirani , Aproximační algoritmy , Nicolase Shabanela , Springer Verlag , 2001 (tehdy 2003), 380 s. ( ISBN 978-3-540-65367-7 ) , viz „ Aproximační algoritmy: obsah “ na webu Nicolase Schabanela .
- Samir Khuller a Yoram J. Sussmann, „ Problém Capacitated \ emph {K} -Center “, SIAM J. Diskrétní matematika. , sv. 13, n o 3, 2000, str. 403-418
- Dorit S Hochbaum, „Různé představy o aproximacích: Dobré, lepší, nejlepší a další“ , v Aproximační algoritmy pro NP-hard problems , PWS Publishing Co., 1996, str. 346-446
- (in) Michael Garey a David S. Johnson , Computers and Intractability: A Guide to The Theory of NP-Completeness , WH Freeman,1979( ISBN 0-7167-1045-5 ).
- (en) Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski a Gerhard Woeginger, „ Metrické k-centrum “ , na Kompendiu optimalizačních problémů NP ,2000.
- Teofilo F. Gonzalez , „ Shlukování za účelem minimalizace maximální vzdálenosti mezi klastry “, Theoretical Computer Science , sv. 38, 1985, str. 293-306 ( DOI 10.1016 / 0304-3975 (85) 90224-5 )
- (en) Sanjoy Dasgupta, „ Přednáška 1: Shlukování v metrických prostorech “ , na Kalifornské univerzitě v San Diegu ,2013
- Jack Edmonds a Delbert Ray Fulkerson , „ Extreme Bottleneck “, Journal of Combinatorial Theory , sv. 8, n o 3, 1970, str. 299-306.
- (en) Vijay Vazirani , Aproximační algoritmy , Springer Verlag , 2001 (poté 2003), 380 s. ( ISBN 978-3-540-65367-7 ) , kap. 5 („k-střed“)
- Viz snímky 14-19 Thomase Rothvosse, „ Aproximační algoritmus “ ,2009.
- Dorit S. Hochbaum a David B. Shmoys , „ Nejlepší možná heuristika pro problém k-Center “, Mathematics of Operations Research , sv. 10, n O 2 1985, str. 180-184
- Wen-Lian Hsu a George L. Nemhauser, „ Snadné a těžké problémy s problémovým místem “, Discrete Applied Mathematics , Elsevier, sv. 1, n o 3, 1979, str. 209-215
- David Eisenstat, Philip N. Klein a Claire Mathieu, „Aproximační k -centrum v rovinných grafech“ , ve sborníku z dvacátého pátého výročního sympozia ACM-SIAM o diskrétních algoritmech, SODA 2014, Portland, Oregon, USA, 5. ledna 7, 2014 , 2014, str. 617-627
- David P. Williamson a David B. Shmoys, kap. 2.2 „Problém k-centra“ v The Design of Aproximation Algorithms , Cambridge University Press
externí odkazy
- (en) Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski a Gerhard Woeginger , „ Metrické k-centrum “ , Kompendium optimalizačních problémů NP ,2000.
- (en) Sanjoy Dasgupta, „ Přednáška 1: Shlukování v metrických prostorech “ , na Kalifornské univerzitě v San Diegu ,2013