Tilnærmet algoritme til at finde p-medianer

Den heuristiske metode til at finde p-medianen er som følger: toppunkter er tilfældigt udvalgt , de danner det indledende sæt , der tilnærmer p-mediansættet . Derefter finder man ud af, om et eller andet toppunkt kan erstatte toppunktet (som et midterpunkt), hvortil der bygges et nyt sæt og udvekslingsforhold og sammenlignes . Hvis , så erstat med , som bedre tilnærmer p-mediansættet . Derefter analyseres sættet på samme måde, og så videre, indtil sættet ' er konstrueret, hvilket ikke kan ændres efter ovenstående princip. $s$ $S$ $X_{p}^{*}$ $x_{j}\in X\setminus S$ $x_{i}\in S$ $S^{*}=(S\kop {x_{j)))\setminus {x_{i}}$ $\sigma (S^{*})$ $\sigma (S)$ $\sigma (S^{*})<\sigma (S)$ $S$ $S^{*}$ $X_{p}^{*}$ $S^{*}$ $S$

Algoritme

Trin 1. Vælg et sæt p-hjørner som en indledende tilnærmelse til p-medianen. Og lad os kalde alle hjørnerne "utestede". $S$ $x_{i}\notin S$

Trin 2. Tag et vilkårligt "utestet" toppunkt og for hvert toppunkt beregn "tilvæksten" Δij svarende til udskiftningen af toppunktet med toppunktet , det vil sige beregn . $x_{i}\in S$ $x_i$ ${\displaystyle x_{j))$ $\Delta _{ij}=\sigma (S)-\sigma ((S\kop {x_{j)))\setminus {x_{i)))$

Trin 3. Find af alle . $\Delta _{i^{1}j}=max[\Delta _{ij}]$ $x_{i}\in S$

a) Hvis , så kald toppunktet "testet" og gå til trin 2. $\Delta _{i^{1}j}\leq 0$ ${\displaystyle x_{j))$

b) Hvis , så kald toppunktet "testet" og gå til trin 2. $\Delta _{i^{i}j}\geq 0$ $S\gets (S\cup {x_{j}})\setminus {x_{i}}$ $x_{j}$

Trin 4. Gentag trin 2 og 3, indtil alle hjørner fra er testet. Denne procedure er designet som en cyklus. Hvis der i løbet af den sidste cyklus ikke er nogen udskiftninger af hjørner ved trin 3(a), så gå til trin 5. Ellers, det vil sige, hvis der er foretaget en udskiftning, kalder du alle knudepunkter "uforsøgt" og vender tilbage til trin 2. $X\setminus S$

Trin 5. Stop. Det aktuelle sæt er en passende tilnærmelse af p-mediansættet . $S$ $X_{p}^{*}$

Eksempel

Det er let at se, at ovenstående algoritme ikke giver det optimale svar i alle tilfælde. Lad os overveje et eksempel (tallene nær kanterne er lig med de tilsvarende kantomkostninger, alle hjørner har samme enhedsvægt):

Hvis vi kigger efter 2-medianen og tager {x3, x6} som startmængden S med gearforholdet , så fører ingen udskiftning af kun et toppunkt til et sæt med et mindre gearforhold. Men mængden {x3, x6} er ikke 2-medianen af denne graf, fordi der er to 2-mediansæt med forholdet 7: {x1, x4} og {x2, x5}. $\sigma (S)=8$

Litteratur

Christofides N. Grafteori. Algoritmisk tilgang. — M .: Mir, 1978.
E. Mainik. Optimeringsalgoritmer til netværk og grafer. — M .: Mir, 1981. — 324 s.

Tilnærmet algoritme til at finde p-medianer

Algoritme

Eksempel

Litteratur

Links