Алгоритм Эвена — Паза

Алгоритм Эвена — Паза — это вычислительно эффективный алгоритм для справедливого разрезания торта. Он предназначен для некоторого разнородного делимого ресурса, такого как торт на день рождения, среди n участников с различными предпочтениями для различных частей торта. Алгоритм позволяет для n людей получить пропорциональный делёж.

ИсторияПравить

Первым опубликованным алгоритмом пропорционального дележа торта был алгоритм «последний уменьшивший», опубликованный в 1948 году и имевший сложность $\text{[math]}$ $\text{[math]}$ $O(n^{2})$ . В 1984 году израильские математики Шимон Эвен и Азария Паз опубликовали улучшенный алгоритм, сложность которого составила $\text{[math]}$ $\text{[math]}$ $O(n\log n)$ ^[1].

ОписаниеПравить

Алгоритм использует стратегию «разделяй и властвуй» и способен дать пропорциональный делёж за время $\text{[math]}$ $\text{[math]}$ $O(n\log n)$ .

Каждого партнёра просят провести линию, делящую торт на левую и правую часть так, что (по его мнению) отношение равно ⌊n/2⌋:⌈n/2⌉. Требуется, чтобы линии не пересекались. Простой путь гарантировать это — разрешать только горизонтальные линии или только вертикальные.
Алгоритм сортирует n линий и разрезает торт по медиане линий, то есть по ⌊n/2⌋-ой линии. Например, если имеется 5 партнёров, проведших линии x=1, x=3, x=5, x=8 и x=9, то алгоритм режет торт вертикально по линии x=3.
Алгоритм назначает каждой из половинок партнёров, линии которых принадлежат этой части, то есть партнёры, которые провели первые ⌊n/2⌋ линии назначаются левой части, остальные назначаются правой части. Так, партнёры проведшие линии x=1 и x=3, назначаются левой части, а остальные три партнёра назначаются правой части. Каждая из частей рекурсивно делится среди партнёров, назначенных этой части.

Можно доказать по индукции, что любой партнёр, который играет по правилам, гарантирующий значение по меньшей мере 1/n независимо от поведения других партнёров.

Благодаря стратегии «разделяй и властвуй» число итераций равно лишь O(log n), в отличие от O(n) для процедуры «последний уменьшивший». На каждой итерации от каждого партнёра требуется один маркер. Следовательно, число требуемых маркеров равно $\text{[math]}$ $\text{[math]}$ $O(n\log n)$ .

ОптимальностьПравить

Несколькими годами позже после публикации алгоритма Эвена — Паза доказано, что любая детерминированная или рандомизированная процедура пропорционального дележа, назначающего каждого участника непрерывный кусок, должна использовать $\text{[math]}$ $\text{[math]}$ $\Omega (n\log n)$ действий^[2].

Более того, любая процедура детерминированного пропорционального дележа должна использовать $\text{[math]}$ $\text{[math]}$ $\Omega (n\log n)$ действий, даже если процедуре разрешено дать участнику кусок, не являющийся непрерывным, и даже если процедуре разрешено гарантирует лишь примерную справедливость^[3]^[4].

Из этих результатов трудности алгоритмов следует, что алгоритм Эвена — Паза является самым быстрым алгоритмом для достижения полной пропорциональности с непрерывными кусками, и этот алгоритм является самым быстрым для получения даже частичной пропорциональности и даже с разрывными кусками. Единственный случай, в котором алгоритм можно улучшить, это рандомизированные алгоритмы, гарантирующие частичную пропорциональность с разрывными кусками. См. «алгоритм Эдмондса — Пруса».

Рандомизированная версияПравить

Можно использовать рандомизацию для снижения числа маркеров. Следующая рандомизированная версия рекурсивной процедуры деления пополам достигает пропорциональный делёж используя только O(n) маркирующих запросов в среднем^[1]. Идея в том, что на каждой итерации вместо опроса всех участников сделать отметку посередине, просят только несколько партнёров сделать такие маркеры, в то время как другие партнёры лишь выбирают половинку, которую они предпочитают. Партнёры посылаются либо на запад, либо на восток согласно их предпочтениям, пока число партнёров на каждой стороне не станет равной n/2. Тогда делается разрез и каждая группа из n/2 партнёров делят свою половину рекурсивно^[5].

В худшем случае нам по-прежнему нужно n-1 маркеров на итерацию, так что число требуемых маркеров в худшем случае равно O(n log n). Однако в среднем случае нужно только O(log n) маркеров на итерацию. При решении рекуррентного соотношения можно показать, что число требуемых маркеров равно O(n).

Заметим, что полное число запросов остаётся равным O(n log n), поскольку каждый партнёр должен выбрать половину.

ПримечанияПравить

↑ ¹ ² Even, Paz, 1984, с. 285.
↑ Sgall, Woeginger, 2007, с. 213–220.
↑ Edmonds, 2006, с. 271–278.
↑ Edmonds, 2011, с. 1–12.
↑ Этот рандомизированный рекурсивный алгоритм деления пополам похож на хорошо известный рандомизарованный алгоритм ранжирования – нахождения r-ранжирования элементов в массиве чисел.

ЛитератураПравить

Even S., Paz A. A note on cake cutting // Discrete Applied Mathematics. — 1984. — Т. 7, вып. 3. — doi:10.1016/0166-218x(84)90005-2.
Jiří Sgall, Gerhard J. Woeginger. On the complexity of cake cutting // Discrete Optimization. — 2007. — Т. 4, вып. 2. — doi:10.1016/j.disopt.2006.07.003.
Jeff Edmonds. Cake cutting really is not a piece of cake. — Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm - SODA '06. — 2006. — ISBN 978-0898716054. — doi:10.1145/1109557.1109588.
Jeff Edmonds. Cake cutting really is not a piece of cake // ACM Transactions on Algorithms. — 2011. — Т. 7, вып. 4. — doi:10.1145/2000807.2000819.

[_202969dfc4f4cf45-1] ¹ ² Even, Paz, 1984, с. 285.

[_9792561fdd56ab5f-2] Sgall, Woeginger, 2007, с. 213–220.

[_2083a523f5642e7b-3] Edmonds, 2006, с. 271–278.

[_c55528f1498ca7cc-4] Edmonds, 2011, с. 1–12.

[Ranking-5] Этот рандомизированный рекурсивный алгоритм деления пополам похож на хорошо известный рандомизарованный алгоритм ранжирования – нахождения r-ранжирования элементов в массиве чисел.

[1]

[2]

[3]

[4]

[5]