Even-Paz algoritmus

Az Even-Paz algoritmus  egy számításilag hatékony algoritmus a torta tisztességes vágására . Valamilyen heterogén osztható erőforrásra, például egy születésnapi tortára szolgál, n résztvevő között, akik különböző preferenciákkal rendelkeznek a torta különböző részei iránt. Az algoritmus lehetővé teszi, hogy n ember arányos osztást kapjon .

Történelem

Az első közzétett algoritmus a torta arányos felosztására az 1948-ban közzétett utolsó csökkenő algoritmus volt, amely összetett volt . 1984-ben Shimon Even és Azariah Paz izraeli matematikusok egy továbbfejlesztett algoritmust adtak ki, amelynek összetettsége [1] volt .

Leírás

Az algoritmus oszd meg és uralkodj stratégiát használ, és képes időarányos osztást adni .

• Minden partnernek húznia kell egy vonalat, amely a tortát bal és jobb részre osztja úgy, hogy (szerinte) az arány ⌊ n /2⌋:⌈ n /2⌉ legyen. Szükséges, hogy a vonalak ne metsszék egymást. Ennek egyszerű módja, ha csak vízszintes vagy csak függőleges vonalakat engedélyez.
• Az algoritmus n sort rendez, és a vonalak mediánja , azaz a ⌊ n /2⌋-edik vonal mentén vágja el a tortát . Például, ha van 5 partner, aki megrajzolta az x =1, x =3, x =5, x =8 és x =9 vonalakat, akkor az algoritmus függőlegesen vágja el a tortát az x =3 vonal mentén .
• Az algoritmus mindegyik félhez hozzárendeli azokat a partnereket, akiknek vonalai ehhez a részhez tartoznak, azaz az első ⌊ n /2⌋ sort húzó partnereket a bal oldalhoz, a többit a jobb oldalhoz rendeli. Tehát azok a partnerek, akik x = 1 és x = 3 vonalat húztak, a bal oldalra, a másik három partner pedig a jobb oldalra kerülnek. Mindegyik rész rekurzív módon fel van osztva az adott részhez rendelt partnerek között.

Indukcióval igazolható, hogy minden olyan partner, aki legalább 1/ n értéket garantáló szabályok szerint játszik , függetlenül a többi partner viselkedésétől.

Az oszd meg és uralkodj stratégiának köszönhetően az iterációk száma csak O(log n ), szemben az utoljára redukált eljárás O( n ) értékével. Minden iterációnál minden partnertől egy token szükséges. Ezért a szükséges markerek száma .

Optimalitás

Néhány évvel az Even-Paz algoritmus megjelenése után bebizonyosodott, hogy minden determinisztikus vagy véletlenszerű arányos osztási eljárásnak, amely minden résztvevőhöz egy folytonos darabot rendel, akciókat kell használnia [2] .

Ezen túlmenően minden determinisztikus arányos felosztási eljárásnak műveleteket kell alkalmaznia , még akkor is, ha az eljárás nem folytonos darabot ad a résztvevőnek, és akkor is, ha az eljárás csak hozzávetőleges igazságosságot garantál [3] [4] .

Ezekből az algoritmusok nehézségi eredményeiből következik, hogy az Even-Paz algoritmus a leggyorsabb algoritmus a teljes arányosság elérésére folytonos darabokkal, és ez az algoritmus a leggyorsabb akár részarányosság elérésére, akár nem folytonos darabokkal is. Az egyetlen eset, amikor az algoritmus javítható, a véletlenszerű algoritmusok alkalmazása , amelyek részleges arányosságot garantálnak nem folytonos darabokkal. Lásd: " Edmonds-Prus algoritmus ".

Véletlenszerű változat

Véletlenszerűsítéssel csökkentheti a markerek számát. A rekurzív felezési eljárás következő véletlenszerű változata arányos osztást ér el átlagosan csak O( n ) címkézési lekérdezések használatával [1] . Az ötlet az, hogy minden iterációnál ahelyett, hogy az összes résztvevőt megkérnénk, hogy középen jelöljön, csak néhány partnert kérünk meg ilyen jelzők készítésére, míg a többi partner csak azt a felét választja, amelyik jobban tetszik. A partnereket preferenciájuk szerint nyugatra vagy keletre küldik, amíg a partnerek száma mindkét oldalon n /2 lesz. Ezután egy vágás történik, és minden n /2 partnerből álló csoport rekurzívan elosztja a felét [5] .

A legrosszabb esetben iterációnként még mindig n -1 markerre van szükségünk, így a szükséges markerek száma legrosszabb esetben O( n log n ). Átlagos esetben azonban csak O(log n ) markerre van szükség iterációnként. Az ismétlődési összefüggés megoldásával kimutatható, hogy a szükséges markerek száma O( n ).

Vegye figyelembe, hogy a kérelmek teljes száma O( n log n ) marad, mivel minden partnernek a felét kell választania.

Jegyzetek

1. ↑ 1 2 Even, Paz, 1984 , p. 285.
2. ↑ Sgall, Woeginger, 2007 , p. 213–220.
3. ↑ Edmonds, 2006 , p. 271–278.
4. ↑ Edmonds, 2011 , p. 1–12.
5. ↑ Ez a véletlenszerű rekurzív felező algoritmus hasonló a jól ismert randomizált rangsoroló algoritmushoz, amely egy számtömb elemeinek r -rangsorát keresi.

Irodalom

• Even S., Paz A. Megjegyzés a tortavágásról // Discrete Applied Mathematics. - 1984. - T. 7 , sz. 3 . - doi : 10.1016/0166-218x(84)90005-2 .
• Jiri Sgall, Gerhard J. Woeginger. A tortavágás összetettségéről // Discrete Optimization. - 2007. - T. 4 , sz. 2 . - doi : 10.1016/j.disopt.2006.07.003 .
• Jeff Edmonds. A tortavágás valóban nem egy szelet torta. – A diszkrét algoritmusokról szóló tizenhetedik éves ACM-SIAM szimpózium anyaga – SODA '06. - 2006. - ISBN 978-0898716054 . doi : 10.1145 / 1109557.1109588 .
• Jeff Edmonds. A tortavágás valóban nem egy darab torta // ACM Transactions on Algorithms. - 2011. - T. 7 , sz. 4 . - doi : 10.1145/2000807.2000819 .