Even-Paz algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 12. února 2020; ověření vyžaduje 1 úpravu .

Algoritmus Even-Paz je výpočetně účinný algoritmus pro spravedlivé krájení koláče . Je to pro nějaký heterogenní dělitelný zdroj, jako je narozeninový dort, mezi n účastníky s různými preferencemi pro různé části dortu. Algoritmus umožňuje n lidem získat poměrné dělení .

Historie

První publikovaný algoritmus pro poměrné dělení koláče byl algoritmus posledního zmenšování , publikovaný v roce 1948, který měl složitost . V roce 1984 publikovali izraelští matematici Shimon Even a Azariah Paz vylepšený algoritmus, jehož složitost byla [1] . $O(n^{2})$ $O(n\log n)$

Popis

Algoritmus používá strategii rozděl a panuj a je schopen dát proporcionální dělení v čase . $O(n\log n)$

Každý partner je požádán, aby nakreslil čáru rozdělující dort na levou a pravou část tak, aby (podle jeho názoru) byl poměr ⌊ n /2⌋:⌈ n /2⌉. Je nutné, aby se čáry nekřížily. Snadný způsob, jak to zajistit, je povolit pouze vodorovné čáry nebo pouze svislé čáry.
Algoritmus seřadí n řádků a ořízne koláč podél mediánu řádků, tedy podél ⌊ n /2⌋-té řádky. Například, pokud existuje 5 partnerů, kteří nakreslili čáry x = 1, x = 3, x = 5, x = 8 a x = 9, pak algoritmus rozřízne koláč svisle podél čáry x =3.
Algoritmus přiřadí každé polovině partnery, jejichž čáry patří do této části, to znamená, že partneři, kteří nakreslili prvních ⌊ n /2⌋ čar, jsou přiřazeni na levou stranu, zbytek na pravou stranu. Takže partneři, kteří narýsovali čáry x = 1 a x = 3, jsou přiřazeni na levou stranu a ostatní tři partneři jsou přiřazeni na pravou stranu. Každá z částí je rekurzivně rozdělena mezi partnery přiřazené k této části.

Indukcí lze dokázat, že každý partner, který hraje podle pravidel zaručujících hodnotu alespoň 1/ n , bez ohledu na chování ostatních partnerů.

Díky strategii rozděl a panuj je počet iterací pouze O(log n ), na rozdíl od O( n ) u poslední redukované procedury. Při každé iteraci je od každého partnera vyžadován jeden token. Počet požadovaných značek je tedy . $O(n\log n)$

Optimality

Několik let po zveřejnění algoritmu Even-Paz bylo prokázáno, že jakákoli deterministická nebo randomizovaná procedura proporcionálního dělení přidělující každému účastníkovi souvislou část musí používat akce [2] . $\Omega (n\log n)$

Kromě toho musí každá procedura deterministického proporcionálního dělení používat akce, i když je v rámci procedury povoleno dát účastníkovi kus, který není kontinuální, a i když je povoleno zaručovat pouze přibližnou spravedlnost [3] [4] . $\Omega (n\log n)$

Z těchto výsledků obtížnosti algoritmu vyplývá, že Even-Pazův algoritmus je nejrychlejším algoritmem pro dosažení plné proporcionality se spojitými kusy a tento algoritmus je nejrychlejší pro dosažení i částečné proporcionality a dokonce i s nespojitými kusy. Jediným případem, kdy lze algoritmus zlepšit, jsou randomizované algoritmy , které zaručují částečnou proporcionalitu s nespojitými kousky. Viz " Algoritmus Edmonds-Prus ".

Randomizovaná verze

Ke snížení počtu značek můžete použít randomizaci. Následující randomizovaná verze rekurzivní bisekční procedury dosahuje proporcionálního dělení v průměru pouze pomocí O( n ) značkovacích dotazů [1] . Myšlenka je taková, že při každé iteraci je místo toho, aby se všichni účastníci žádali, aby označili uprostřed, jen několik partnerů je požádáno, aby vytvořili takové značky, zatímco ostatní partneři si vyberou pouze polovinu, kterou preferují. Partneři jsou posíláni na západ nebo na východ podle svých preferencí, dokud počet partnerů na každé straně není n /2. Poté se provede řez a každá skupina n /2 partnerů rekurzivně rozdělí svou polovinu [5] .

V nejhorším případě stále potřebujeme n -1 značek na iteraci, takže počet požadovaných značek je v nejhorším případě O( n log n ). V průměrném případě však potřebujete pouze značky O(log n ) na iteraci. Řešením rekurentního vztahu lze ukázat, že počet požadovaných markerů je O( n ).

Všimněte si, že celkový počet požadavků zůstává O( n log n ), protože každý partner si musí vybrat polovinu.

Poznámky

↑ 1 2 Even, Paz, 1984 , str. 285.
↑ Sgall, Woeginger, 2007 , str. 213–220.
↑ Edmonds, 2006 , str. 271–278.
↑ Edmonds, 2011 , str. 1–12.
↑ Tento algoritmus randomizovaného rekurzivního půlení je podobný známému algoritmu randomizovaného hodnocení – nalezení r - hodnocení prvků v poli čísel.

Literatura

Even S., Paz A. Poznámka ke krájení dortu // Diskrétní aplikovaná matematika. - 1984. - T. 7 , no. 3 . - doi : 10.1016/0166-218x(84)90005-2 .
Jiří Sgall, Gerhard J. Woeginger. O složitosti krájení dortu // Diskrétní optimalizace. - 2007. - T. 4 , no. 2 . - doi : 10.1016/j.disopt.2006.07.003 .
Jeff Edmonds. Krájení dortu opravdu není hračka. — Sborník ze sedmnáctého výročního sympozia ACM-SIAM o diskrétním algoritmu - SODA '06. - 2006. - ISBN 978-0898716054 . doi : 10.1145 / 1109557.1109588 .
Jeff Edmonds. Krájení dortu opravdu není hračka // ACM Transactions on Algorithms. - 2011. - T. 7 , no. 4 . - doi : 10.1145/2000807.2000819 .