Likimääräinen algoritmi p-mediaanien löytämiseksi

Heuristinen menetelmä p-mediaanin löytämiseksi on seuraava: kärjet valitaan satunnaisesti , ne muodostavat alkujoukon , approksimoiden p-mediaanijoukkoa . Sitten selvitetään, voiko jokin kärki korvata kärjen (mediaanipisteenä), jolle rakennetaan uusi joukko ja vertaillaan välityssuhteita ja . Jos , korvaa sitten , joka on paremmin likimääräinen p-mediaani joukko . Sitten joukkoa analysoidaan samalla tavalla ja niin edelleen, kunnes joukko ' on konstruoitu, jota ei voi muuttaa yllä olevan periaatteen mukaisesti. $s$ $S$ $X_{p}^{*}$ $x_{j}\in X\setminus S$ $x_{i}\in S$ $S^{*}=(S\cup {x_{j)))\setminus {x_{i}}$ $\sigma (S^{*})$ $\sigma (S)$ $\sigma (S^{*})<\sigma (S)$ $S$ $S^{*}$ $X_{p}^{*}$ $S^{*}$ $S$

Algoritmi

Vaihe 1. Valitse jokin p-pisteiden joukko p-mediaanin alustavaksi approksimaatioksi. Ja kutsutaan kaikkia huippuja "testaamattomiksi". $S$ $x_{i}\notin S$

Vaihe 2. Ota mielivaltainen ”testaamaton” kärki ja laske jokaiselle kärkipisteelle ” lisäys” Δij, joka vastaa kärjen korvaamista kärjellä , eli laske . $x_{i}\in S$ $x_i$ ${\näyttötyyli x_{j))$ $\Delta _{ij}=\sigma (S)-\sigma ((S\cup {x_{j)))\setminus {x_{i)))$

Vaihe 3. Etsi kaikkien mukaan . $\Delta _{i^{1}j}=max[\Delta _{ij}]$ $x_{i}\in S$

a) Jos , kutsu kärkipiste "testatuksi" ja siirry vaiheeseen 2. $\Delta _{i^{1}j}\leq 0$ ${\näyttötyyli x_{j))$

b) Jos , niin , kutsu kärkeä "testatuksi" ja siirry vaiheeseen 2. $\Delta _{i^{i}j}\geq 0$ $S\gets (S\cup {x_{j}})\setminus {x_{i}}$ $x_{j}$

Vaihe 4. Toista vaiheita 2 ja 3, kunnes kaikki kärjet kohteesta on testattu. Tämä menettely on suunniteltu sykliksi. Jos viimeisen jakson aikana ei ole vaihdettu kärkejä vaiheessa 3(a), siirry vaiheeseen 5. Muussa tapauksessa, toisin sanoen, jos jokin korvaus on tehty, kutsu kaikkia pisteitä "untried" ja palaa vaiheeseen 2. $X\setminus S$

Vaihe 5. Pysäytä. Nykyinen joukko on sopiva approksimaatio p-mediaanijoukolle . $S$ $X_{p}^{*}$

Esimerkki

On helppo nähdä, että yllä oleva algoritmi ei anna optimaalista vastausta kaikissa tapauksissa. Tarkastellaan esimerkkiä (reunojen lähellä olevat luvut ovat yhtä suuria kuin vastaavat reunakustannukset, kaikilla pisteillä on sama yksikköpaino):

Jos etsimme 2-mediaania ja otamme {x3, x6} alkujoukoksi S välityssuhteella , niin vain yhden kärjen korvaaminen ei johda joukkoon, jolla on pienempi välityssuhde. Joukko {x3, x6} ei kuitenkaan ole tämän kaavion 2-mediaani, koska on olemassa kaksi 2-mediaanijoukkoa, joiden suhde on 7: {x1, x4} ja {x2, x5}. $\sigma (S)=8$

Kirjallisuus

Christofides N. Graafiteoria. Algoritminen lähestymistapa. - M .: Mir, 1978.
E. Mainik. Optimointialgoritmit verkoille ja kaavioille. - M .: Mir, 1981. - 324 s.

Likimääräinen algoritmi p-mediaanien löytämiseksi

Algoritmi

Esimerkki

Kirjallisuus

Linkit