Even-Paz algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 12. februar 2020; verifikation kræver 1 redigering .

Even-Paz- algoritmen er en beregningseffektiv algoritme til at skære kagen retfærdigt . Det er for en eller anden heterogen delbar ressource, såsom en fødselsdagskage, blandt n deltagere med forskellige præferencer for forskellige dele af kagen. Algoritmen gør det muligt for n personer at få en proportional division .

Historie

Den første offentliggjorte algoritme til proportional opdeling af kagen var den sidste aftagende algoritme , udgivet i 1948, som havde kompleksitet . I 1984 udgav de israelske matematikere Shimon Even og Azariah Paz en forbedret algoritme, hvis kompleksitet var [1] . $O(n^{2})$ $O(n\log n)$

Beskrivelse

Algoritmen bruger en divider og hersk strategi og er i stand til at give en proportional opdeling i tid . $O(n\log n)$

Hver partner bliver bedt om at tegne en linje, der deler kagen i venstre og højre del, så forholdet (efter hans mening) er ⌊ n /2⌋:⌈ n /2⌉. Det kræves, at linjerne ikke skærer hinanden. En nem måde at sikre dette på er kun at tillade vandrette linjer eller kun lodrette linjer.
Algoritmen sorterer n linjer og skærer kagen langs medianen af linjerne, det vil sige langs ⌊ n /2⌋. linje. Hvis der for eksempel er 5 partnere, der har tegnet linjerne x =1, x =3, x =5, x =8 og x =9, så skærer algoritmen kagen lodret langs linjen x =3.
Algoritmen tildeler hver af halvdelene partnere, hvis linjer tilhører denne del, det vil sige, at de partnere, der tegnede de første ⌊ n /2⌋ linjer, tildeles til venstre side, resten tildeles til højre side. Så partnere, der har tegnet linjer x = 1 og x = 3, tildeles til venstre side, og de tre andre partnere tildeles til højre. Hver af delene er rekursivt opdelt blandt de partnere, der er tildelt den del.

Det kan bevises ved induktion, at enhver partner, der spiller efter reglerne, der garanterer en værdi på mindst 1/ n , uanset de andre partneres adfærd.

Takket være divide and conquer-strategien er antallet af iterationer kun O(log n ), i modsætning til O( n ) for den sidst reducerede procedure. Ved hver iteration kræves der et token fra hver partner. Derfor er antallet af nødvendige markører . $O(n\log n)$

Optimalitet

Et par år efter offentliggørelsen af Even-Paz-algoritmen blev det bevist, at enhver deterministisk eller randomiseret proportional divisionsprocedure, der tildeler hver deltager et kontinuerligt stykke, skal bruge handlinger [2] . $\Omega (n\log n)$

Desuden skal enhver deterministisk proportional divisionsprocedure bruge handlinger, selvom proceduren tillades at give deltageren en brik, der ikke er kontinuerlig, og selvom proceduren kun har lov til at garantere omtrentlig retfærdighed [3] [4] . $\Omega (n\log n)$

Det følger af disse algoritmesværhedsresultater, at Even-Paz-algoritmen er den hurtigste algoritme til at opnå fuld proportionalitet med kontinuerlige stykker, og denne algoritme er den hurtigste til at opnå selv delvis proportionalitet og endda med diskontinuerlige stykker. Det eneste tilfælde, hvor algoritmen kan forbedres, er i randomiserede algoritmer , der garanterer delvis proportionalitet med diskontinuerlige bidder. Se " Edmonds-Prus Algorithm ".

Randomiseret version

Du kan bruge randomisering til at reducere antallet af markører. Den følgende randomiserede version af den rekursive bisektionsprocedure opnår proportional division ved kun at bruge O( n ) tagging-forespørgsler i gennemsnit [1] . Tanken er, at ved hver iteration, i stedet for at bede alle deltagere om at markere i midten, bliver kun nogle få partnere bedt om at lave sådanne markører, mens andre partnere kun vælger den halvdel, de foretrækker. Partnere sendes enten vest eller øst alt efter deres præference, indtil antallet af partnere på hver side er n /2. Derefter laves et snit, og hver gruppe af n /2 partnere deler deres halvdel rekursivt [5] .

I værste fald har vi stadig brug for n -1 markører per iteration, så antallet af nødvendige markører er O( n log n ) i værste fald. Men i gennemsnittet har du kun brug for O(log n ) markører pr. iteration. Ved at løse gentagelsesrelationen kan det vises, at antallet af nødvendige markører er O( n ).

Bemærk, at det samlede antal anmodninger forbliver O( n log n ), da hver partner skal vælge halvdelen.

Noter

↑ 1 2 Even, Paz, 1984 , s. 285.
↑ Sgall, Woeginger, 2007 , s. 213-220.
↑ Edmonds, 2006 , s. 271-278.
↑ Edmonds, 2011 , s. 1-12.
↑ Denne randomiserede rekursive bisektionsalgoritme ligner den velkendte randomiserede rangordningsalgoritme - at finde r - rangeringen af elementer i en række af tal.

Litteratur

Even S., Paz A. En note om kageskæring // Diskret anvendt matematik. - 1984. - T. 7 , no. 3 . - doi : 10.1016/0166-218x(84)90005-2 .
Jiri Sgall, Gerhard J. Woeginger. Om kompleksiteten ved kageskæring // Diskret optimering. - 2007. - T. 4 , no. 2 . - doi : 10.1016/j.disopt.2006.07.003 .
Jeff Edmonds. Kageskæring er virkelig ikke et stykke kage. — Proceedings af det syttende årlige ACM-SIAM-symposium om diskret algoritme - SODA '06. - 2006. - ISBN 978-0898716054 . doi : 10.1145 / 1109557.1109588 .
Jeff Edmonds. Kageskæring er virkelig ikke et stykke kage // ACM Transactions on Algorithms. - 2011. - T. 7 , no. 4 . - doi : 10.1145/2000807.2000819 .