Protokół Even-Paz

Algorytm Even-Paz jest wydajnym obliczeniowo algorytmem do sprawiedliwego krojenia tortu . Obejmuje pewien heterogeniczny i podzielny zasób, taki jak tort urodzinowy, oraz n partnerów o różnych preferencjach co do różnych części tortu. Pozwala to n osobom osiągnąć proporcjonalny podział .

Historia

Pierwszym opublikowanym algorytmem proporcjonalnego dzielenia ciasta był ostatni algorytm zmniejszający , opublikowany w 1948 r. Jego złożoność w czasie wykonywania wynosiła O( n ^2). w 1984 roku Shimon Even i Azaria Paz opublikowali swój ulepszony algorytm, którego złożoność w czasie wykonywania wynosi tylko O ​​( n log n ).

Opis

Algorytm wykorzystuje strategię dziel i zwyciężaj, możliwe jest osiągnięcie proporcjonalnego podziału w czasie O( n log n ).

  • Każdy partner jest proszony o narysowanie linii dzielącej ciasto na prawą i lewą część w taki sposób, aby jego zdaniem stosunek wynosił ⌊ n /2⌋:⌈ n /2⌉. Cięcia muszą się nie przecinać; prostym sposobem zagwarantowania tego jest zezwolenie tylko na linie poziome lub tylko linie pionowe.
  • Algorytm sortuje n wierszy w porządku rosnącym i kroi tort po środku wierszy, czyli na ⌊ n /2⌋ wierszu. Np. jeśli jest 5 partnerów, którzy rysują linie w x =1, x =3, x =5, x =8 i x =9, to algorytm przecina tort pionowo na x =5.
  • Algorytm przypisuje do każdej z dwóch części partnerów, których linia jest w tej części, tzn. partnerzy, którzy narysowali pierwsze linie ⌊ n /2⌋ zostają przypisani do lewej części, pozostali do prawej. Np. partnerzy, którzy narysowali linie w punktach x =1, x =3 i x =5 są przypisani do partii lewej, a pozostali partnerzy do partii prawej. Każda część jest dzielona rekurencyjnie między przypisanych do niej partnerów.

Można udowodnić przez indukcję, że każdy partner grający zgodnie z regułami ma zagwarantowaną figurę o wartości co najmniej 1/ n , niezależnie od tego, co robią pozostali partnerzy.

Dzięki strategii dziel i zwyciężaj liczba iteracji wynosi tylko O(log n ), w przeciwieństwie do O( n ) w procedurze Last Diminisher. W każdej iteracji każdy partner musi zrobić jeden znak. W związku z tym całkowita liczba wymaganych ocen wynosi O( n log n ).

optymalność

Kilka lat po opublikowaniu algorytmu Even-Paz udowodniono, że każda deterministyczna lub losowa procedura dzielenia proporcjonalnego przypisująca każdej osobie ciągły element musi wykorzystywać działania Ω ( n log n ).

Co więcej, każda deterministyczna procedura dzielenia proporcjonalnego musi wykorzystywać działania Ω( n log n ), nawet jeśli procedura może przypisać każdemu partnerowi nieciągłą figurę i nawet jeśli procedura może gwarantować jedynie przybliżoną uczciwość .

Te wyniki twardości sugerują, że algorytm Even-Paz jest najszybszym możliwym algorytmem do osiągnięcia pełnej proporcjonalności z ciągłymi kawałkami i jest to najszybszy możliwy algorytm deterministyczny do osiągnięcia nawet częściowej proporcjonalności, a nawet z rozłączonymi kawałkami. Jedynym przypadkiem, w którym można to poprawić, są losowe algorytmy gwarantujące częściową proporcjonalność z rozłączonymi elementami; patrz algorytm Edmondsa – Pruhsa .

Wersja losowa

Istnieje możliwość zastosowania randomizacji w celu zmniejszenia liczby ocen. Następująca losowa wersja procedury rekurencyjnego podziału na pół pozwala uzyskać podział proporcjonalny przy użyciu średnio tylko zapytań ze znacznikami O ( n ). Pomysł polega na tym, że w każdej iteracji zamiast prosić wszystkich partnerów o zrobienie znaku połowy wartości, tylko niektórzy partnerzy są proszeni o zrobienie takich znaków, podczas gdy inni partnerzy wybierają tylko tę połowę, którą wolą. Partnerzy są wysyłani albo na zachód, albo na wschód, zgodnie z ich preferencjami, aż liczba partnerów po każdej stronie wyniesie n /2. Następnie dokonuje się cięcia i każda grupa n /2 partnerów rekurencyjnie dzieli swoją połowę.

W najgorszym przypadku nadal potrzebujemy n -1 znaków na iterację, więc w najgorszym przypadku wymagana liczba znaków to O( n log n ). Jednak średnio tylko znaki O (log n ) są wymagane na iterację; rozwiązując wzór na powtarzalność, można wykazać, że średnia wymagana liczba ocen wynosi O ( n ).

Zauważ, że całkowita liczba zapytań nadal wynosi O( n log n ), ponieważ każdy partner musi wybrać połowę.

  1. ^ a b Nawet, S .; Paz, A. (1984). „Uwaga na temat krojenia ciasta” . Dyskretna matematyka stosowana . 7 (3): 285. doi : 10.1016/0166-218x(84)90005-2 .
  2. ^ Sgall, Jiří; Woeginger, Gerhard J. (2007). „O złożoności krojenia ciasta” . Optymalizacja dyskretna . 4 (2): 213–220. doi : 10.1016/j.disopt.2006.07.003 .
  3. Bibliografia   _ Cięcie ciasta naprawdę nie jest bułką z masłem . Materiały z siedemnastego dorocznego sympozjum ACM-SIAM na temat algorytmu dyskretnego - SODA '06 . s. 271–278. doi : 10.1145/1109557.1109588 . ISBN 978-0898716054 . ,   Edmonds, Jeff (2011). „Krój ciasta naprawdę nie jest bułka z masłem”. Transakcje ACM na algorytmach . 7 (4): 1–12. CiteSeerX 10.1.1.146.1536 . doi : 10.1145/2000807.2000819 .
  4. ^ Ten losowy rekurencyjny algorytm podziału na pół jest podobny do dobrze znanego losowego algorytmu rankingu - znajdowania elementu r -rankingowego w tablicy liczb
Pobrano z „ https://en.wikipedia.org/w/index.php?title=Even-Paz_protocol&oldid=1033881897 ”