Even-Paz-algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 12. helmikuuta 2020 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Even-Paz- algoritmi on laskennallisesti tehokas algoritmi kakun reilun leikkaamiseen . Se on tarkoitettu jollekin heterogeeniselle jaettavalle resurssille, kuten syntymäpäiväkakulle, n osallistujan kesken, joilla on erilaiset mieltymykset kakun eri osista. Algoritmi antaa n :lle mahdollisuuden saada suhteellinen jako .

Historia

Ensimmäinen julkaistu algoritmi kakun suhteelliselle jakamiselle oli viimeinen vähenevä algoritmi , joka julkaistiin vuonna 1948 ja joka oli monimutkainen . Vuonna 1984 israelilaiset matemaatikot Shimon Even ja Azariah Paz julkaisivat parannetun algoritmin, jonka monimutkaisuus oli [1] . $O(n^{2})$ $O(n\log n)$

Kuvaus

Algoritmi käyttää hajota ja hallitse - strategiaa ja pystyy antamaan suhteellisen jaon ajassa . $O(n\log n)$

Jokaista kumppania pyydetään piirtämään viiva, joka jakaa kakun vasempaan ja oikeaan osaan siten, että (hänen mielestä) suhde on ⌊ n /2⌋:⌈ n /2⌉. On välttämätöntä, että viivat eivät leikkaa. Helppo tapa varmistaa tämä on sallia vain vaakaviivat tai vain pystysuorat viivat.
Algoritmi lajittelee n riviä ja leikkaa kakun viivojen mediaania pitkin eli ⌊ n /2⌋:nnettä viivaa pitkin. Jos esimerkiksi 5 kumppania on piirtänyt viivat x =1, x =3, x =5, x =8 ja x =9, niin algoritmi leikkaa kakun pystysuunnassa viivaa x =3 pitkin.
Algoritmi jakaa jokaiselle puolikkaalle osapuolet, joiden suorat kuuluvat tähän osaan, eli ensimmäiset ⌊ n /2⌋ viivaa piirtäneet osapuolet on osoitettu vasemmalle puolelle, loput oikealle puolelle. Joten kumppanit, jotka ovat piirtäneet viivat x = 1 ja x = 3, määrätään vasemmalle puolelle ja muut kolme kumppania oikealle puolelle. Jokainen osa jaetaan rekursiivisesti kyseiseen osaan määritettyjen kumppaneiden kesken.

Induktiolla voidaan todistaa, että jokainen kumppani, joka pelaa vähintään 1/ n arvon takaavien sääntöjen mukaan , riippumatta muiden kumppanien käyttäytymisestä.

Jaa ja hallitse -strategian ansiosta iteraatioiden määrä on vain O(log n ), toisin kuin viimeksi pelkistetyssä proseduurissa O( n ). Jokaisessa iteraatiossa vaaditaan yksi tunnus jokaiselta kumppanilta. Siksi vaadittujen merkkien määrä on . $O(n\log n)$

Optimaalisuus

Muutama vuosi Even-Paz-algoritmin julkaisun jälkeen todistettiin, että minkä tahansa deterministisen tai satunnaistetun suhteellisen jakoproseduurin, joka määrittää kullekin osallistujalle jatkuvan kappaleen, täytyy käyttää toimintoja [2] . $\Omega (n\log n)$

Lisäksi kaikissa deterministisessä suhteellisessa jakomenettelyssä on käytettävä toimenpiteitä, vaikka menettelyn sallittaisiin antaa osallistujalle kappale, joka ei ole jatkuva, ja vaikka menettelyn sallittaisiin taata vain likimääräinen oikeudenmukaisuus [3] [4] . $\Omega (n\log n)$

Näistä algoritmin vaikeustuloksista seuraa, että Even-Paz-algoritmi on nopein algoritmi täyden suhteellisuuden saavuttamiseksi jatkuvilla kappaleilla, ja tämä algoritmi on nopein saavuttamaan jopa osittaisen suhteellisuuden ja jopa epäjatkuvien kappaleiden kanssa. Ainoa tapaus, jossa algoritmia voidaan parantaa, ovat satunnaistetut algoritmit , jotka takaavat osittaisen suhteellisuuden epäjatkuvilla paloilla. Katso " Edmonds-Prus-algoritmi ".

Satunnaistettu versio

Voit käyttää satunnaistamista vähentääksesi merkkien määrää. Seuraava satunnaistettu versio rekursiivisesta puolittajaproseduurista saavuttaa suhteellisen jaon käyttämällä keskimäärin vain O( n ) merkintäkyselyä [1] . Ajatuksena on, että jokaisessa iteraatiossa, sen sijaan, että kaikkia osallistujia pyydettäisiin merkitsemään keskelle, vain muutamaa kumppania pyydetään tekemään tällaisia merkkejä, kun taas muut kumppanit valitsevat vain haluamansa puolikkaan. Kumppanit lähetetään joko länteen tai itään heidän mieltymyksensä mukaan, kunnes kumppaneiden määrä kummallakin puolella on n /2. Sitten tehdään leikkaus ja jokainen n /2 kumppanin ryhmä jakaa puolikkaan rekursiivisesti [5] .

Pahimmassa tapauksessa tarvitsemme silti n -1 markkeria iteraatiota kohden, joten vaadittu merkkien määrä on pahimmassa tapauksessa O( n log n ). Keskimääräisessä tapauksessa tarvitset kuitenkin vain O(log n ) -merkkiä iteraatiota kohden. Ratkaisemalla toistuvuusrelaatio voidaan osoittaa, että tarvittavien merkkien määrä on O( n ).

Huomaa, että pyyntöjen kokonaismäärä on O( n log n ), koska jokaisen kumppanin on valittava puolet.

Muistiinpanot

↑ 1 2 Even, Paz, 1984 , s. 285.
↑ Sgall, Woeginger, 2007 , s. 213-220.
↑ Edmonds, 2006 , s. 271-278.
↑ Edmonds, 2011 , s. 1–12.
↑ Tämä satunnaistettu rekursiivinen puolittamisalgoritmi on samanlainen kuin hyvin tunnettu satunnaistettu ranking -algoritmi - elementtien r -sijoituksen löytäminen lukujoukosta.

Kirjallisuus

Even S., Paz A. Huomautus kakun leikkaamisesta // Discrete Applied Mathematics. - 1984. - T. 7 , no. 3 . - doi : 10.1016/0166-218x(84)90005-2 .
Jiri Sgall, Gerhard J. Woeginger. Kakun leikkaamisen monimutkaisuudesta // Discrete Optimization. - 2007. - T. 4 , no. 2 . - doi : 10.1016/j.disopt.2006.07.003 .
Jeff Edmonds. Kakun leikkaaminen ei todellakaan ole pala kakkua. — Seitsemännentoista vuotuisen ACM-SIAM-symposiumin julkaisut diskreetistä algoritmista - SODA '06. - 2006. - ISBN 978-0898716054 . doi : 10.1145 / 1109557.1109588 .
Jeff Edmonds. Kakun leikkaaminen ei todellakaan ole pala kakkua // ACM Transactions on Algorithms. - 2011. - T. 7 , no. 4 . - doi : 10.1145/2000807.2000819 .