Algoritmul lui Graham

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 26 iulie 2020; verificările necesită 5 modificări .

Algoritmul lui Graham este un algoritm pentru construirea unei carcase convexe în spațiu bidimensional. În acest algoritm, problema învelișului convex este rezolvată folosind o stivă formată din puncte candidate. Toate punctele setului de intrare sunt împinse pe stivă, iar apoi punctele care nu sunt vârfuri ale carcasei convexe sunt în cele din urmă îndepărtate din acesta. La sfârșitul algoritmului, doar vârfurile shell-ului rămân pe stivă în ordinea în care sunt parcurse în sens invers acelor de ceasornic.

Algoritm

Datele de intrare ale procedurii Graham sunt setul de puncte Q, unde . Apelează funcția Top(S), care returnează punctul din vârful stivei S fără a-și schimba conținutul. În plus, este folosită și funcția NextToTop(S), care returnează punctul situat pe stiva S, o poziție sub punctul de sus; stiva S nu se modifică. $|Q|\geqslant 3$

Graham (Q) 1) Fie un punct din mulțimea Q cu coordonata minimă y sau cel mai din stânga acestor puncte în prezența potrivirilor

p_{0}

2) Fie punctele rămase ale mulțimii Q, sortate în ordinea crescătoare a unghiului polar,

<p_{1},p_{2},\ldots ,p_{m}>

măsurată în sens invers acelor de ceasornic față de punct (dacă unghiurile polare ale mai multor puncte sunt aceleași, atunci prin distanța până la punct )

p_{0}

p_{0}

3) Apăsați( ,S)

p_{0}

4) Apăsați( ,S)

p_{1}

5) pentru i = 2 la m faceți 6) în timp ce unghiul format de punctele NextTop(S),Top(S) și , formează o viraj non-stânga

p_{i}

(când ne deplasăm de-a lungul liniei întrerupte formate de aceste puncte, ne deplasăm drept sau spre dreapta) 7) face Pop(S) 8) Apăsați( ,S)

p_{i}

9) întoarce S

Pentru a determina dacă trei puncte formează și o viraj la stânga , puteți utiliza o generalizare a produsului vectorial la un spațiu bidimensional, și anume, condiția viraj la stânga va arăta astfel: , unde $A$ $b$ $c$ $u_{x}v_{y}-u_{y}v_{x}\geqslant 0$ $u=\left\{b_{x}-a_{x},\;b_{y}-a_{y}\right\},v=\left\{c_{x}-b_{x} ,\;c_{y}-b_{y}\right\}$

Un exemplu de funcționare a algoritmului lui Graham.

Corectitudinea scanării Graham

Dacă procedura Graham prelucrează un set de puncte Q, unde , atunci la sfârșitul acestei proceduri, stiva S va conține (de jos în sus) doar vârfurile învelișului CH(Q) în sens invers acelor de ceasornic. $|Q|\geqslant 3$

Dovada

După executarea liniei 2, avem la dispoziție o succesiune de puncte . Să definim o submulțime de puncte pentru i = 2,3,…,m. Mulțimea punctelor Q - formează cele care au fost îndepărtate datorită faptului că unghiul lor polar față de punctul p0 coincide cu unghiul polar al unui punct din mulțime . Aceste puncte nu aparțin corpului convex CH(Q), deci CH( ) = CH(Q). Astfel, este suficient să arătăm că, la sfârșitul procedurii lui Graham, stiva S constă din vârfurile învelișului CH( ) în sens invers acelor de ceasornic, dacă aceste puncte sunt privite în sus pe stiva de jos în sus. Rețineți că, așa cum punctele , , sunt vârfuri ale învelișului CH(Q), punctele , , sunt vârfuri ale învelișului CH( ). $<p_{1},p_{2},\ldots ,p_{m}>$ $Q_{i}=\left\{p_{0},p_{1},\ldots ,p_{i}\right\}$ $Q_{m}$ $Q_{m}$ $Q_{m}$ $Q_{m}$ $p_{0}$ $p_{1}$ $p.m}$ $p_{0}$ $p_{1}$ $p_{i}$ $Q_{i}$

Dovada folosește invariantul ciclului formulat mai jos. La începutul fiecărei iterații a buclei for din liniile 6-9, stiva S constă (de jos în sus) numai din vârfurile shell-ului CH( ) în sens invers acelor de ceasornic. $Q_{{i-1}}$

Inițializare . Prima linie temporală 6 este executată, invariantul este menținut deoarece în acel moment stiva S constă numai din vârfuri = , iar acest set de trei vârfuri își formează propriul înveliș convex. În plus, dacă vizualizați punctele de jos în sus, acestea vor fi localizate în sens invers acelor de ceasornic. $Q_{2}$ $Q_{{i-1}}$

Conservarea . Când introduceți o nouă iterație a buclei for, în vârful stivei S este punctul , plasat acolo la sfârșitul iterației anterioare (sau înaintea primei iterații, când i = 3). Fie punctul de sus al stivei S după executarea liniilor 7-8 ale buclei while, dar înainte ca punctul să fie împins pe stiva din linia 9 . Fie și punctul situat în stiva S direct sub punctul . În momentul în care punctul se află în vârful stivei S, iar punctul nu a fost încă adăugat, stiva conține aceleași puncte ca după a j-a iterație a buclei for. Prin urmare, conform invariantei buclei, în acest punct, stiva S conține doar CH( ) în ordinea de parcurgere în sens invers acelor de ceasornic, văzut de jos în sus. Unghiul polar al punctului în raport cu punctul este mai mare decât unghiul polar al punctului și, deoarece unghiul se rostogolește spre stânga (în caz contrar, punctul ar fi îndepărtat din stivă), după adăugarea punctului la stiva S (înainte de au existat doar vârfuri CH( )) va conține vârfuri CH( ). În același timp, acestea vor fi aranjate în sens invers acelor de ceasornic, dacă sunt privite de jos în sus. $p_{{i-1}}$ $pijamale}$ $p_{i}$ $p_{k}$ $pijamale}$ $pijamale}$ $p_{i}$ $Q_{j}$ $p_{i}$ $p_{0}$ $pijamale}$ $p_{k}$ $pijamale}$ $p_{i}$ $pijamale}$ $p_{i}$ $Q_{j}$ $Q_{j}\cup \left\{p_{i}\right\}$

Să arătăm că mulţimea vârfurilor CH( ) coincide cu mulţimea punctelor CH( ). Luați în considerare un punct arbitrar ieșit din stivă în timpul i-a iterație a buclei for și să fie punctul situat pe stiva S imediat sub punctul dinaintea ultimei iterații din stivă (acest punct pr poate fi punctul ). Unghiul nu se rotește spre stânga, iar unghiul polar al punctului în raport cu punctul este mai mare decât unghiul polar al punctului . Deoarece punctul se află în interiorul triunghiului format din alte trei puncte ale mulțimii , nu poate fi vârful lui CH( ). Deoarece nu este un vârf al lui CH( ), atunci CH( - { }) = CH( ). Fie setul de puncte luate din stivă în timpul execuției celei de-a i-a iterații a buclei for. Egalitatea CH( - ) = CH( ) este adevărată. Totuși — = { }, deci concluzionăm că CH( { }) = CH( — ) = CH( ). $Q_{j}\cup \left\{p_{i}\right\}$ $Q_{i}$ $p_{t}$ $relatii cu publicul}$ $p_{t}$ $pijamale}$ $relatii cu publicul}$ $p_{t}$ $p_{i}$ $p_{t}$ $p_{0}$ $relatii cu publicul}$ $p_{t}$ $Q_{i}$ $Q_{i}$ $p_{t}$ $Q_{i}$ $Q_{i}$ $p_{t}$ $Q_{i}$ $P_{i}$ $Q_{i}$ $P_{i}$ $Q_{i}$ $Q_{i}$ $P_{i}$ $Q_{i}$ $\ceașcă$ $p_{i}$ $Q_{j}$ $\ceașcă$ $p_{i}$ $Q_{i}$ $P_{i}$ $Q_{i}$

Imediat după ce punctul este împins din stiva S , acesta conține doar vârfurile CH( ) în ordinea în care sunt parcurse în sens invers acelor de ceasornic, dacă le priviți în stiva de jos în sus. Creșterea ulterioară cu una a valorii lui i va duce la păstrarea invariantului buclei în următoarea iterație. $p_{i}$ $Q_{i}$

Finalizare . La sfârșitul buclei, egalitatea i = m + 1 este satisfăcută, deci din invariantul buclei rezultă că stiva S constă numai din vârfurile lui CH( ), adică din vârfurile lui CH(Q). Aceste vârfuri sunt în ordinea de traversare în sens invers acelor de ceasornic atunci când sunt văzute pe stivă de jos în sus. $Q_{m}$

Orele de deschidere

Timpul de rulare al procedurii Graham este , unde . După cum puteți vedea cu ușurință, bucla while va dura O( ) timp. În timp ce sortarea unghiurilor polare va dura timp, de aici și comportamentul asimptotic general al procedurii lui Graham. $O(N\log N)$ $N=|Q|$ $N$ $O(N\log N)$

Vezi și

Algoritmul Jarvis
algoritmul lui Chan
Algoritmul rapid Shell
Algoritmul de șiruri monotonice al lui Andrew

Literatură

T. Kormen, C. Leizerson, R. Rivest, K. Stein. Algoritmi. Construcție și analiză = Introducere în algoritmi. - Ed. a II-a. - „Williams”, 2005.