Problém s 1 středem

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 8. března 2017; ověření vyžaduje 1 úpravu .

Problém 1-centra nebo problém umístění objektu s minimaxem je klasický problém kombinatorické optimalizace , problém v oboru operačního výzkumu , je speciálním případem problému umístění objektu . V nejobecnějším případě je formulován takto:

Je uveden soubor spotřebitelských míst, prostor možných umístění objektů (výroba nebo služba) a funkce nákladů na dopravu z libovolného místa možného místa do místa spotřeby. Je nutné najít optimální umístění objektů, minimalizující maximální náklady na doručení od objektu ke spotřebiteli.

Jednoduchý speciální případ, kdy jsou ubytovací a spotřební místa v rovině a náklady na doručení jsou euklidovská vzdálenost ( problém s euklidovským umístěním v rovinném minimaxu, problém euklidovské 1-středové roviny ) je také známý jako problém nejmenšího kruhu . Jeho zobecnění na vyšší dimenzionální euklidovské prostory je známé jako problém nejméně ohraničující koule . V dalším zobecnění ( vážený euklidovský problém umístění ) jsou bodům spotřeby přiřazeny váhy a náklady na dopravu jsou součtem vzdáleností vynásobených odpovídajícími váhami. Dalším speciálním případem je problém nejbližšího řádku , kdy vstupem problému je řetězec a vzdálenost je měřena jako Hammingova vzdálenost .

Zvláštních případů problému je celá řada, v závislosti jak na volbě umístění odběrných míst a výrobních (nebo servisních) objektů, tak na volbě funkce, která vzdálenost vypočítá.

Problém 1 centra z hlediska teorie grafů

Formulace takové varianty úlohy spočívá v tom, že je dán graf , i nákladová funkce a je potřeba najít takovou množinu , aby byla minimální, tzn. množina taková, že maximální cena cesty z vrcholu nejblíže k jakémukoli vrcholu zůstává minimální. Problém lze také doplnit funkcí vertex cost, a pak pro něj bude poloměr definován jako . $G=(V,E)$ $k\in {\mathbb {N}}$ ${\displaystyle c\colon E\to \mathbb {Q} ^{+))$ $Z\subset V$ $\operatorname {rad} (Z)=\max _{v\in V}\min _{z\in Z}c(z,v)$ $Z$ $Z$ ${\displaystyle w\colon V\to \mathbb {Q} ^{+))$ $\operatorname {rad} (Z)=\max _{v\in V}[w(v)\cdot \min _{z\in Z}c(z,v)]$

Myšlenkou přibližného řešení problému je hledání pevného poloměru pomocí chamtivého algoritmu . Dokud existují vertexy, které nejsou pokryty , je třeba chtivě vybrat vertex a zvážit všechny ostatní dostupné vertexy . Algoritmus se opakuje pro různé hodnoty . Níže je uveden popis metody ve formální podobě: $Z$ $R$ $Z$ $z$ $2R$ $R$

Nainstalujte a . $Z=\emptyset$ $U=V$
ahoj : $U\neq \emptyset$
1. ${\displaystyle z=\operatorname {argmax} \{w(u)\mid u\in U\))$ .
2. ${\displaystyle Z=Z\cup \{z\))$ .
3. ${\displaystyle U=U\setminus \{v\in U\mid w(v)\cdot \operatorname {dist} (v,z)\leqslant 2R\))$ .
Vynést . $Z$

Nechť je optimálním řešením pro . V případě kdy , chamtivý algoritmus vrátí množinu takovou, že . Na základě toho definujeme a poznamenáváme, že funkce není monotónní . Dále označíme poloměr , s jehož pomocí může pouze jeden vrchol v pokrýt všechny vrcholy grafu, tzn. , _ $R^{*}$ $Z^*$ $R\geqslant R^{*}$ $Z$ $|Z|\leqslant |Z^{*}|$ $f(R)=|\operatorname {GreedyCenter} (G,c,w,R)|$ $F$ $R'=\max _{v\in V}[w(v)\cdot \sum _{e\in E}c(e)]$ $Z$ $f(R')=1$ $f(0)=|V|=n$

Lemma. Pro jakýkoli graf s optimální sadou a poloměrem platí nerovnost pro všechny . $G=(V,E)$ $Z^*$ $R^{*}=\operatorname {rad} (Z^{*})$ $f(R)\leqslant k$ $R\geqslant R^{*}$

Důkaz. Nechť a je vybraný vrchol v cyklu algoritmu . Pak je skutečná nerovnost: ${\displaystyle V_{i}=\{v\in V\mid w(v)\cdot \operatorname {dist} (v,z_{i})\leqslant R^{*}\))$ ${\displaystyle z\in V_{i))$ $\operatorname {GreedyCenter}$

{\begin{aligned}w(v)\cdot \operatorname {dist} (v,z)&\leqslant w(v)\cdot (\operatorname {dist} (v,v_{i})+\ operatorname {dist} (v_{i},z))\\&\leqslant w(v)\cdot \operatorname {dist} (v,v_{i})+w(z)\cdot \operatorname {dist} ( v_{i},z)\\&\leqslant 2\cdot R^{*}\leqslant 2\cdot R\end{aligned}}

Všechny vrcholy z budou na konci iterace odstraněny, což znamená, že smyčka skončí maximálně v iteracích, a proto . $V_i$ $k=|Z^{*}|$ $|Z|\leqslant k$

Z lemmatu vyplývá, že chamtivý algoritmus lze spouštět, dokud nebude výsledná množina menší než požadovaná , pomocí matice vzdáleností k výpočtu poloměrů . Celková časová složitost algoritmu je tedy , a aproximační faktor je . $Z$ $k$ $O(n^{4})$ $2$

Řešitelnost

Za podmínky, že třídy P a NP nejsou stejné, neexistuje pro žádnou polynomiální algoritmus s aproximačním faktorem . Důkaz tohoto tvrzení se redukuje na redukci na problém dominující množiny : Nechť je dán jako vstup do algoritmu řešícího problém dominující množiny. Nechte také pro všechny okraje . Pak obsahuje dominující množinu velikosti , pokud množina obsahuje vrcholy a poloměr ( ) je roven . Pokud by existoval -aproximační algoritmus s , pak by našel dominantní množinu s přesně stejným aproximačním faktorem, což je nemožné. $r<2$ $r$ $(G,k)$ $c(e)=1$ $e\in E(G)$ $G$ $k$ $Z$ $k$ $\operatorname {rad} (Z)$ $jeden$ $r$ ${\mathcal {A}}$ $r<2$ ${\mathcal {A}}(G,1,k,c)$

Viz také

Problém umístění objektů s minimalizací součtu vzdáleností (aka "Problém 1-mediánu") s mediánem množiny bodů jako speciální případ
Problém maximálního umístění objektů (pokud je to možné, umístění škodlivých předmětů)
Problém k-centra
K-mediánový problém

Poznámky

Literatura

Nimrod Megiddo. Vážená euklidovská úloha s jedním středem // Matematika operačního výzkumu. — Hannover: Institut pro operační výzkum a vědy o řízení. - T. 8 , ne. 4 . — S. 498–504 . - doi : 10.1287/moor.8.4.498 .
Abdelaziz Faul. Problém 1 centra v rovině s rovnoměrně rozloženými poptávkovými body // Operations Research Letters. - Elsevier, 2006. - T. 34 , no. 3 . — S. 264–268 . - doi : 10.1016/j.orl.2005.04.011 .
R. Chandrasekaran. Vážený euklidovský problém s jedním středem // Operations Research Letters. - Elsevier, červenec 1982. - Svazek 1 , č. 3 . — S. 111–112 . - doi : 10.1016/0167-6377(82)90009-8 .
M. Colebrook, S. Alonso Gutierrez, J. Sicilia. Nový algoritmus pro nežádoucí problém s jedním centrem v sítích // Journal of the Operational Research Society . - Palgrave Macmillan Journals, 2002. - V. 53 , no. 12 . - S. 1357-1366 . doi : 10.1057 / palgrave.jors.2601468 . — .
Rainer E. Burkard, Helidon Dollani. Poznámka k problému robustního 1-centra na stromech // Annals of Operations Research. - Kluwer Academic Publishers, 2002. - T. 110 , no. 1-4 . — s. 69–82 . — ISSN 1572-9338 . - doi : 10.1023/A:1020711416254 .