Hozzávetőleges algoritmus a p-mediánok meghatározásához

A p-medián megtalálásának heurisztikus módszere a következő: a csúcsokat véletlenszerűen választjuk ki , ezek alkotják a kezdeti halmazt , közelítve a p-medián halmazt . Ezután kiderül, hogy valamelyik csúcs helyettesítheti-e azt a csúcsot (mint medián csúcsot), amelyhez új halmazt építenek , és összehasonlítják az áttételi viszonyokat és . Ha , akkor cserélje ki a -ra , amely jobban közelíti a p-medián halmazt . Ezután a halmazt hasonlóan elemezzük, és így tovább, amíg meg nem épül a ' halmaz, amely a fenti elv szerint nem módosítható. $p$ $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$

Algoritmus

1. lépés: Válasszon ki néhány p csúcskészletet a p-medián kezdeti közelítéseként. És nevezzük az összes csúcsot "nem teszteltnek". $S$ $x_{i}\notin S$

2. lépés : Vegyünk egy tetszőleges „nem tesztelt” csúcsot, és minden csúcsra számítsuk ki a Δij „növekményt”, amely megfelel a csúcsnak a csúcsgal való helyettesítésének , azaz számítsuk ki a . $x_{i}\in S$ $x_i$ ${\displaystyle x_{j))$ $\Delta _{ij}=\sigma (S)-\sigma ((S\cup {x_{j)))\setminus {x_{i)))$

3. lépés : Mindenki keresése . $\Delta _{i^{1}j}=max[\Delta _{ij}]$ $x_{i}\in S$

a) Ha , akkor nevezze a csúcsot "tesztelt"-nek, és folytassa a 2. lépéssel. $\Delta _{i^{1}j}\leq 0$ ${\displaystyle x_{j))$

b) Ha , akkor , nevezze a csúcsot "tesztelt"-nek, és folytassa a 2. lépéssel. $\Delta _{i^{i}j}\geq 0$ $S\gets (S\cup {x_{j}})\setminus {x_{i}}$ $x_{j}$

4. lépés. Ismételje meg a 2. és 3. lépést, amíg az összes csúcsot teszteli. Ezt az eljárást ciklusként tervezték. Ha az utolsó ciklusban nem történt csúcscsere a 3(a) lépésben, akkor folytassa az 5. lépéssel. Ellenkező esetben, ha történt valamilyen csere, hívja az összes csúcsot „kipróbálatlan”-nak, és térjen vissza a 2. lépéshez. $X\setminus S$

5. lépés . Állj. Az aktuális halmaz megfelelő közelítése a p-medián halmaznak . $S$ $X_{p}^{*}$

Példa

Könnyen belátható, hogy a fenti algoritmus nem minden esetben adja meg az optimális választ. Tekintsünk egy példát (az élek közelében lévő számok megegyeznek a megfelelő élköltséggel, minden csúcsnak azonos az egységsúlya):

Ha a 2-mediánt keressük, és {x3, x6}-t vesszük S kezdeti halmaznak az áttételi arány mellett , akkor egyetlen csúcs cseréje sem vezet kisebb áttételű halmazhoz. Az {x3, x6} halmaz azonban nem ennek a grafikonnak a 2-mediánja, mert két 7-es arányú 2-medián halmaz létezik: {x1, x4} és {x2, x5}. $\sigma (S)=8$

Irodalom

Christofides N. Gráfelmélet. Algoritmikus megközelítés. - M .: Mir, 1978.
E. Mainik. Optimalizálási algoritmusok hálózatokhoz és gráfokhoz. — M .: Mir, 1981. — 324 p.

Hozzávetőleges algoritmus a p-mediánok meghatározásához

Algoritmus

Példa

Irodalom

Linkek