Algoritm aproximativ pentru găsirea p-medianelor

Metoda euristică pentru găsirea p-medianei este următoarea: vârfurile sunt selectate aleatoriu , ele formează mulțimea inițială , aproximând mulțimea p-mediană . Apoi se află dacă un vârf poate înlocui vârful (ca un vârf median), pentru care se construiește un nou set și se compară rapoartele de transmisie . Dacă , atunci înlocuiți cu , care aproximează mai bine mulțimea p-mediană . Apoi, mulțimea este analizată în mod similar și așa mai departe, până când se construiește mulțimea, care nu poate fi schimbată conform principiului de mai sus. $p$ $S$ $X_{p}^{*}$ $x_{j}\în X\setminus S$ $x_{i}\în S$ $S^{*}=(S\cup {x_{j)))\setminus {x_{i}}$ $\sigma (S^{*})$ $\sigma (S)$ $\sigma (S^{*})<\sigma (S)$ $S$ $S^{*}$ $X_{p}^{*}$ $S^{*}$ $S$

Algoritm

Pasul 1. Alegeți un set de p vârfuri ca o aproximare inițială a p-mediană. Și să numim toate vârfurile „netestate”. $S$ $x_{i}\notin S$

Pasul 2. Luați un vârf arbitrar „netestat” și pentru fiecare vârf calculați „incrementul” Δij corespunzător înlocuirii vârfului cu vârful , adică calculați . $x_{i}\în S$ $x_i$ $x_{j)$ $\Delta _{ij}=\sigma (S)-\sigma ((S\cup {x_{j))}\setminus {x_{i))}$

Pasul 3. Găsiți de către toți . $\Delta _{i^{1}j}=max[\Delta _{ij}]$ $x_{i}\în S$

a) Dacă , atunci numiți vârful „testat” și treceți la pasul 2. $\Delta _{i^{1}j}\leq 0$ $x_{j)$

b) Dacă , atunci , numiți vârful „testat” și treceți la pasul 2. $\Delta _{i^{i}j}\geq 0$ $S\gets (S\cup {x_{j}})\setminus {x_{i}}$ $x_{j}$

Pasul 4. Repetați pașii 2 și 3 până când toate vârfurile de la sunt testate. Această procedură este concepută ca un ciclu. Dacă, în timpul ultimului ciclu, nu există înlocuiri de vârfuri la pasul 3(a), atunci treceți la pasul 5. În caz contrar, adică dacă a fost făcută o înlocuire, numiți toate nodurile „neîncercate” și reveniți la pasul 2. $X\setminus S$

Pasul 5. Opriți. Setul curent este o aproximare adecvată a mulțimii p-mediane . $S$ $X_{p}^{*}$

Exemplu

Este ușor de observat că algoritmul de mai sus nu oferă răspunsul optim în toate cazurile. Să luăm în considerare un exemplu (numerele din apropierea muchiilor sunt egale cu costurile corespunzătoare ale muchiei, toate vârfurile au aceeași greutate unitară):

Dacă căutăm mediana 2 și luăm {x3, x6} ca setul inițial S cu raportul de transmisie , atunci nicio înlocuire a unui singur vârf nu duce la un set cu un raport de transmisie mai mic. Totuși, mulțimea {x3, x6} nu este mediana 2 a acestui grafic, deoarece există două mulțimi cu 2 mediane cu raport 7: {x1, x4} și {x2, x5}. $\sigma (S)=8$

Literatură

Christofides N. Teoria grafurilor. Abordare algoritmică. — M .: Mir, 1978.
E. Mainik. Algoritmi de optimizare pentru rețele și grafice. — M .: Mir, 1981. — 324 p.

Algoritm aproximativ pentru găsirea p-medianelor

Algoritm

Exemplu

Literatură

Link -uri