Grahamin algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 26. heinäkuuta 2020 tarkistetusta versiosta . tarkastukset vaativat 5 muokkausta .

Grahamin algoritmi on algoritmi kuperan rungon rakentamiseksi kaksiulotteisessa avaruudessa. Tässä algoritmissa kupera rungon ongelma ratkaistaan käyttämällä ehdokaspisteistä muodostettua pinoa . Syöttöjoukon kaikki pisteet työnnetään pinoon, ja sitten pisteet, jotka eivät ole kuperan rungon kärkipisteitä, poistetaan lopulta siitä. Algoritmin lopussa pinoon jäävät vain kuoren kärjet siinä järjestyksessä, jossa ne ajetaan vastapäivään.

Algoritmi

Graham-proseduurin syöttödata on pisteiden Q, jossa . Se kutsuu funktiota Top(S), joka palauttaa pisteen pinon S yläosassa muuttamatta sen sisältöä. Lisäksi käytetään myös funktiota NextToTop(S), joka palauttaa pinossa S sijaitsevan pisteen, yhden kohdan yläpisteen alapuolella; pino S ei muutu. $|Q|\geqslant 3$

Graham (Q) 1) Olkoon piste joukosta Q, jolla on pienin koordinaatti y tai vasen piste, jos on osumia

p_{0}

2) Olkoon joukon Q jäljellä olevat pisteet napakulman nousevassa järjestyksessä,

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

mitattuna vastapäivään suhteessa pisteeseen (jos useiden pisteiden napakulmat ovat samat, niin pisteen etäisyydellä )

p_{0}

p_{0}

3) Työnnä( ,S)

p_{0}

4) Työnnä( ,S)

p_{1}

5) kun i = 2 - m tee 6) , kun taas pisteiden NextToTop(S),Top(S) ja , muodostama kulma muodostaa ei-vasemman käännöksen

p_{i}

(liikkuessamme näiden pisteiden muodostamaa katkoviivaa pitkin, siirrymme suoraan tai oikealle) 7) tee pop(S) 8) Työnnä( ,S)

p_{i}

9) palauta S

Sen määrittämiseksi, muodostavatko kolme pistettä , ja käännöksen vasemmalle, voit käyttää vektoritulon yleistystä kaksiulotteiseen avaruuteen, nimittäin vasemman käännöksen ehto näyttää tältä: , missä $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\}$

Esimerkki Grahamin algoritmin toiminnasta.

Graham-skannauksen oikeellisuus

Jos Graham-proseduuri käsittelee joukon pisteitä Q, jossa , niin tämän toimenpiteen lopussa pino S sisältää (alhaalta ylös) vain kuoren CH(Q) kärjet vastapäivään järjestyksessä. $|Q|\geqslant 3$

Todiste

Kun rivi 2 on suoritettu, meillä on käytettävissämme pistejono . Määritellään pisteiden osajoukko arvolle i = 2,3,…,m. Pisteiden joukko Q - muodostaa ne, jotka poistettiin, koska niiden napakulma pisteeseen p0 nähden osuu yhteen joukosta jonkin pisteen napakulman kanssa . Nämä pisteet eivät kuulu kuperaan runkoon CH(Q), joten CH( ) = CH(Q). Näin ollen riittää, kun osoitetaan, että Grahamin proseduurin lopussa pino S koostuu kuoren CH( ) kärjeistä vastapäivään, jos näitä pisteitä tarkastellaan pinosta alhaalta ylös. Huomaa, että aivan kuten pisteet , , ovat kuoren CH(Q) pisteitä, pisteet , , ovat kuoren CH( ) pisteitä. $<p_{1},p_{2},\ldots ,p_{m}>$ $Q_{i}=\vasen\{p_{0},p_{1},\ldots ,p_{i}\oikea\}$ $Q_{m}$ $Q_{m}$ $Q_{m}$ $Q_{m}$ $p_{0}$ $p_{1}$ $p_{m}$ $p_{0}$ $p_{1}$ $p_{i}$ $Q_{i}$

Todistuksessa käytetään alla formuloitua sykliinvarianttia. Jokaisen for-silmukan iteraation alussa riveillä 6-9 pino S koostuu (alhaalta ylös) vain kuoren CH( ) pisteistä vastapäivään järjestyksessä. $Q_{{i-1}}$

Alustus . Ensimmäinen aikarivi 6 suoritetaan, invariantti säilyy, koska siinä vaiheessa pino S koostuu vain pisteistä = , ja tämä kolmen kärjen joukko muodostaa oman kuperan runkonsa. Lisäksi, jos tarkastelet pisteitä alhaalta ylöspäin, ne sijaitsevat vastapäivään. $Q_{2}$ $Q_{{i-1}}$

Säilytys . Kun syötetään for-silmukan uusi iteraatio, pinon S yläosassa on piste , joka sijoitetaan edellisen iteraation loppuun (tai ennen ensimmäistä iteraatiota, kun i = 3). Olkoon pinon S yläpiste while-silmukan rivien 7-8 suorittamisen jälkeen, mutta ennen kuin piste työnnetään pinoon rivillä 9 . Olkoon myös piste, joka sijaitsee pinossa S suoraan pisteen alapuolella . Sillä hetkellä, kun piste on pinon S yläosassa, eikä pistettä ole vielä lisätty, pinossa on samat pisteet kuin for-silmukan j:nnen iteraation jälkeen. Siksi silmukkainvariantin mukaan pino S sisältää tässä vaiheessa vain CH( ) vastapäivään kulkevassa järjestyksessä alhaalta ylös katsottuna. Pisteen napakulma pisteen suhteen on suurempi kuin pisteen napakulma ja koska kulma pyörii vasemmalle (muuten piste poistettaisiin pinosta), kun piste on lisätty pinoon S (ennen oli vain pisteitä CH( )) se sisältää kärjet CH( ). Samalla ne järjestetään vastapäivään, jos niitä katsotaan alhaalta ylöspäin. $p_{{i-1}}$ $p_{j}$ $p_{i}$ $p_{k}$ $p_{j}$ $p_{j}$ $p_{i}$ $Q_{j}$ $p_{i}$ $p_{0}$ $p_{j}$ $p_{k}$ $p_{j}$ $p_{i}$ $p_{j}$ $p_{i}$ $Q_{j}$ $Q_{j}\kuppi \vasen\{p_{i}\oikea\}$

Osoitetaan, että kärkijoukko CH( ) osuu yhteen pisteiden CH( ) kanssa. Tarkastellaan mielivaltaista pistettä , joka pompasi pinosta for-silmukan i:nnen iteraation aikana, ja olkoon pinossa S oleva piste välittömästi sen pisteen alapuolella, joka edeltää viimeistä pinosta pomppausta (tämä piste pr voi olla piste ). Kulma ei pyöri vasemmalle, ja pisteen napakulma pisteeseen nähden on suurempi kuin pisteen napakulma . Koska piste on joukon kolmen muun pisteen muodostaman kolmion sisällä , se ei voi olla CH( ) -pisteen kärki. Koska se ei ole CH( ) -piste, niin CH( - { }) = CH( ). Olkoon joukko pisteitä, jotka on otettu pinosta for-silmukan i:nnen iteraation aikana. Yhtälö CH( - ) = CH( ) on totta. Kuitenkin — = { }, joten päätämme, että CH( { }) = CH( — ) = CH( ). $Q_{j}\kuppi \vasen\{p_{i}\oikea\}$ $Q_{i}$ $p_{t}$ $PR}$ $p_{t}$ $p_{j}$ $PR}$ $p_{t}$ $p_{i}$ $p_{t}$ $p_{0}$ $PR}$ $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}$ $\kuppi$ $p_{i}$ $Q_{j}$ $\kuppi$ $p_{i}$ $Q_{i}$ $P_{i}$ $Q_{i}$

Välittömästi sen jälkeen, kun piste on työnnetty ulos pinosta S , se sisältää vain kärjet CH( ) siinä järjestyksessä kuin ne on ajettu vastapäivään, jos niitä tarkastellaan pinossa alhaalta ylös. Myöhempi lisäys yhdellä i:n arvosta johtaa silmukan invariantin säilymiseen seuraavassa iteraatiossa. $p_{i}$ $Q_{i}$

Valmistuminen . Silmukan lopussa yhtälö i = m + 1 täyttyy, joten silmukkainvariantista seuraa, että pino S koostuu vain CH( ) -pisteistä eli CH(Q:n) pisteistä. Nämä kärjet ovat vastapäivään kulkevassa järjestyksessä, kun niitä tarkastellaan pinossa alhaalta ylös. $Q_{m}$

Aukioloajat

Graham-menettelyn suoritusaika on , missä . Kuten näet helposti, while-silmukka kestää O( ) aikaa. Vaikka napakulmien lajittelu vie aikaa, tästä johtuu Grahamin menettelyn yleinen asymptoottinen käyttäytyminen. $O(N\log N)$ $N=|Q|$ $N$ $O(N\log N)$

Katso myös

Jarvis-algoritmi
Chanin algoritmi
Nopea Shell-algoritmi
Andrew'n monotoninen merkkijono-algoritmi

Kirjallisuus

T. Kormen, C. Leizerson, R. Rivest, K. Stein. Algoritmit. Rakentaminen ja analyysi = Johdatus algoritmeihin. - 2. painos - "Williams", 2005.