1-center probléma

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2017. március 8-án áttekintett verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

Az 1-center probléma vagy minimax objektum elhelyezési probléma klasszikus kombinatorikus optimalizálási probléma , probléma a műveletek kutatásának tudományágában , az objektum elhelyezési probléma speciális esete . A legáltalánosabb esetben a következőképpen van megfogalmazva:

Meg van adva a fogyasztói helyek halmaza, a tárgyak (termelési vagy szolgáltatási) lehetséges helyeinek tere, valamint a lehetséges helytől a fogyasztási pontig történő szállítás költségének függvénye. Meg kell találni a tárgyak optimális elhelyezkedését, minimalizálva a tárgytól a fogyasztóig történő szállítás maximális költségét.

Egy egyszerű speciális eset, amikor a szállások és a fogyasztási pontok egy síkon vannak, és a szállítási költség az euklideszi távolság ( planar minimax euklideszi elhelyezési probléma, euklideszi 1-középsík probléma), a legkisebb kör problémaként is ismert . A magasabb dimenziójú euklideszi terekre való általánosítása a legkevésbé korlátos gömbproblémaként ismert . Egy további általánosításban ( súlyozott euklideszi helyprobléma ) súlyokat rendelünk a fogyasztási pontokhoz, és a szállítási költség a távolságok összege szorozva a megfelelő súlyokkal. Egy másik speciális eset a legközelebbi egyenes problémája, amikor a feladat bemenete a karakterlánc , a távolságot pedig Hamming-távolságként mérjük .

A problémának számos speciális esete van, mind a fogyasztási helyek és a termelő (vagy szolgáltató) objektumok helyének megválasztásától, mind a távolságot számoló függvény megválasztásától függően.

Az 1-központú probléma a gráfelmélet szempontjából

A feladat egy ilyen változatának megfogalmazása abban rejlik, hogy adott egy gráf , valamint egy költségfüggvény, és olyan halmazt kell találni , amely minimális, azaz. egy olyan halmaz , amelynél a csúcshoz legközelebbi csúcsból induló útvonal maximális költsége minimális marad. Ezenkívül a feladat kiegészíthető a csúcsköltség függvénnyel, majd a rádiust a következőképpen határozzuk meg . $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)]$

A probléma hozzávetőleges megoldásának az az ötlete, hogy egy mohó algoritmussal keressünk egy rögzített sugarat . Mindaddig, amíg vannak olyan csúcsok, amelyeket nem fed le, mohón kell választani egy csúcsot , és figyelembe kell venni az összes többi elérhető csúcsot . Az algoritmus megismétlődik a különböző értékekre . Az alábbiakban a módszer leírása található formális formában: $Z$ $R$ $Z$ $z$ $2R$ $R$

Telepítse és . $Z=\emptyset$ $U=V$
Viszlát : $U\neq \emptyset$
1. ${\displaystyle z=\operátornév {argmax} \{w(u)\mid u\in U\))$ .
2. ${\displaystyle Z=Z\kupa \{z\))$ .
3. ${\displaystyle U=U\setminus \{v\in U\mid w(v)\cdot \operátornév {dist} (v,z)\leqslant 2R\))$ .
Hozd ki . $Z$

Legyen az optimális megoldás . Abban az esetben, ha , a mohó algoritmus olyan halmazt ad vissza , hogy . Ennek alapján definiáljuk és megjegyezzük, hogy a függvény nem monoton . Ezt követően jelöljük a sugarat , melynek segítségével csak egy in csúcs fedi le a gráf összes csúcsát, azaz. , a . $R^{*}$ $Z^*$ $R\geqslant R^{*}$ $Z$ $|Z|\leqslant |Z^{*}|$ $f(R)=|\operátornév {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. Minden optimális halmazú és sugarú gráf esetén az egyenlőtlenség mindenre érvényes . $G=(V,E)$ $Z^*$ $R^{*}=\operátornév {rad} (Z^{*})$ $f(R)\leqslant k$ $R\geqslant R^{*}$

Bizonyíték. Legyen és a kiválasztott csúcs az algoritmusciklusban . Akkor az igazi egyenlőtlenség: ${\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 \operátornév {dist} (v,z)&\leqslant w(v)\cdot (\operátornév {dist} (v,v_{i})+\ operátornév {dist} (v_{i},z))\\&\leqslant w(v)\cdot \operátornév {dist} (v,v_{i})+w(z)\cdot \operátornév {dist} ( v_{i},z)\\&\leqslant 2\cdot R^{*}\leqslant 2\cdot R\end{igazított}}

Az iteráció végén az összes csúcsot eltávolítjuk, ami azt jelenti, hogy a ciklus maximum iterációval fog végződni, ezért . $V_i$ $k=|Z^{*}|$ $|Z|\leqslant k$

A lemmából az következik, hogy a mohó algoritmust addig lehet futtatni, amíg a kapott halmaz kisebb nem lesz a szükségesnél , a távolságmátrix segítségével a sugarak kiszámításához . Így az algoritmus teljes időbonyolultsága , a közelítő tényező pedig . $Z$ $k$ $O(n^{4})$ $2$

Feloldhatóság

Feltéve, hogy a P és NP osztályok nem egyenlőek, egyikre sem létezik közelítési tényezőjű polinomiális algoritmus . Ennek az állításnak a bizonyítása a domináns halmazprobléma redukciójára redukálódik : Adjuk meg bemenetként a domináns halmazproblémát megoldó algoritmushoz. Szintén hagyjuk az összes élre . Ekkor tartalmaz egy domináns méretű halmazt, ha a halmaz tartalmaz csúcsokat és a sugár ( ) egyenlő . Ha lenne egy -közelítő algoritmus -val , akkor pontosan ugyanolyan közelítési tényezővel találna domináns halmazt, ami lehetetlen. $r<2$ $r$ ${\megjelenítési stílus (G,k)}$ $c(e)=1$ $e\in E(G)$ $G$ $k$ $Z$ $k$ $\operatorname {rad} (Z)$ $egy$ $r$ ${\mathcal {A}}$ $r<2$ ${\mathcal {A}}(G,1,k,c)$

Lásd még

Az objektumok elhelyezésének problémája a távolságok összegének minimalizálásával (más néven "Az 1-medián problémája") a ponthalmaz mediánjával , mint speciális eset
A tárgyak maximális elhelyezésének problémája (amennyire lehetséges, káros tárgyak elhelyezése)
A k-központ probléma
A k-medián probléma

Jegyzetek

Irodalom

Nimród Megiddo. A súlyozott euklideszi 1-központú probléma // Műveletekkutatás matematikája. – Hannover: Operációkutató és Vezetéstudományi Intézet. - T. 8 , sz. 4 . – S. 498–504 . - doi : 10.1287/moor.8.4.498 .
Abdelaziz Foul. Egy 1 központos probléma a síkon egyenletesen elosztott keresletpontokkal // Operations Research Letters. - Elsevier, 2006. - T. 34 , sz. 3 . – S. 264–268 . - doi : 10.1016/j.orl.2005.04.011 .
R. Chandrasekaran. A súlyozott euklideszi 1-központú probléma // Operations Research Letters. - Elsevier, 1982. július. - 1. kötet , 1. sz. 3 . – S. 111–112 . - doi : 10.1016/0167-6377(82)90009-8 .
M. Colebrook, S. Alonso Gutierrez, J. Sicilia. Új algoritmus a hálózatok nemkívánatos 1-központú problémájára // Journal of the Operational Research Society . - Palgrave Macmillan Journals, 2002. - V. 53 , 1. sz. 12 . - S. 1357-1366 . doi : 10.1057 / palgrave.jors.2601468 . — .
Rainer E. Burkard, Helidon Dollani. Megjegyzés a fák robusztus 1-központi problémájához // Annals of Operations Research. - Kluwer Academic Publishers, 2002. - T. 110 , 1. sz. 1-4 . – 69–82 . — ISSN 1572-9338 . - doi : 10.1023/A:1020711416254 .