Протокол Эвена-Паза
Алгоритм Эвена-Паза — это вычислительно эффективный алгоритм для честного разрезания торта . Он включает в себя определенный гетерогенный и делимый ресурс, например праздничный торт, и n партнеров с разными предпочтениями в отношении разных частей торта. Оно позволяет русскому народу добиться пропорционального деления .
История
[ редактировать ]Первым опубликованным алгоритмом пропорционального деления торта был последний алгоритм уменьшителя , опубликованный в 1948 году. Его сложность во время выполнения составляла O( n ^ 2). в 1984 году Шимон Эвен и Азария Пас опубликовали свой улучшенный алгоритм, сложность выполнения которого составляет всего O( n log n ). [ 1 ]
Описание
[ редактировать ]В алгоритме используется стратегия «разделяй и властвуй», можно добиться пропорционального деления за время O( n log n ).
- Каждому партнеру предлагается провести линию, разделяющую торт на правую и левую части, так, чтобы, по его мнению, соотношение было равно ⌊ n /2⌋:⌈ n /2⌉. Разрезы должны быть непересекающимися; простой способ гарантировать это — разрешить только горизонтальные или только вертикальные линии.
- Алгоритм сортирует n строк в порядке возрастания и разрезает пирог посередине строк, т.е. на ⌊ n /2⌋-й строке. Например, если есть 5 партнеров, которые рисуют линии в точках x =1, x =3, x =5, x =8 и x =9, то алгоритм разрезает торт вертикально в точке x =5.
- Алгоритм назначает каждой из двух частей партнеров, линия которых находится внутри этой части, т.е. партнеры, нарисовавшие первые ⌊ n /2⌋ линий, назначаются левой части, остальные — правой части. Например, партнеры, нарисовавшие линии в точках x =1, x =3 и x =5, назначаются левой части, а остальные партнеры — правой части. Каждая часть рекурсивно делится между закрепленными за ней партнерами.
По индукции можно доказать, что каждому партнеру, играющему по правилам, гарантирована фигура стоимостью не менее 1/ n , независимо от того, что делают другие партнеры.
Благодаря стратегии «разделяй и властвуй» количество итераций составляет всего O(log n ), в отличие от O( n ) в процедуре Last Diminisher. На каждой итерации каждый партнер должен сделать одну отметку. Следовательно, общее количество необходимых оценок равно O( n log n ).
Оптимальность
[ редактировать ]Через несколько лет после публикации алгоритма Эвена-Паза было доказано, что каждая детерминированная или рандомизированная процедура пропорционального деления, присваивающая каждому человеку непрерывный кусок, должна использовать Ω( n log n ) действий. [ 2 ]
Более того, каждая детерминированная процедура пропорционального деления должна использовать Ω( n log n ) действий, даже если процедуре разрешено назначать каждому партнеру несмежный кусок, и даже если процедуре разрешено гарантировать только приблизительную справедливость . [ 3 ]
Эти результаты по твердости подразумевают, что алгоритм Эвена-Паза является самым быстрым из возможных алгоритмов для достижения полной пропорциональности с смежными частями, и это самый быстрый из возможных детерминированных алгоритмов для достижения даже частичной пропорциональности и даже с несвязанными частями. Единственный случай, когда его можно улучшить, — это рандомизированные алгоритмы, гарантирующие частичную пропорциональность несвязанных частей; см. алгоритм Эдмондса-Пруса .
Рандомизированная версия
[ редактировать ]Для уменьшения количества оценок можно использовать рандомизацию. Следующая рандомизированная версия процедуры рекурсивного деления пополам обеспечивает пропорциональное деление, используя в среднем только запросы меток O( n ). [ 1 ] Идея состоит в том, что на каждой итерации вместо того, чтобы просить всех партнеров поставить отметку в половину значения, только некоторым партнерам предлагается сделать такие отметки, в то время как другие партнеры только выбирают, какую половину они предпочитают. Партнеры отправляются либо на запад, либо на восток в зависимости от их предпочтений, пока число партнеров с каждой стороны не станет n /2. Затем делается разрез, и каждая группа из n /2 партнеров рекурсивно делит свою половину. [ 4 ]
В худшем случае нам все равно понадобится n -1 оценок на итерацию, поэтому требуемое количество оценок в худшем случае равно O( n log n ). Однако в среднем только O(log n на итерацию требуется ) оценок; Решив рекуррентную формулу, можно показать, что среднее количество требуемых оценок равно O( n ).
Обратите внимание, что общее количество запросов по-прежнему равно O( n log n ), поскольку каждый партнер должен выбрать половину.
Ссылки
[ редактировать ]- ^ Перейти обратно: а б Эвен, С.; Пас, А. (1984). «Заметка о разрезании торта» . Дискретная прикладная математика . 7 (3): 285. дои : 10.1016/0166-218x(84)90005-2 .
- ^ Сгалл, Иржи; Вегингер, Герхард Дж. (2007). «О сложности разрезания торта» . Дискретная оптимизация . 4 (2): 213–220. дои : 10.1016/j.disopt.2006.07.003 .
- ^ Эдмондс, Джефф (2006). «Разрезка торта на самом деле непростая задача». Материалы семнадцатого ежегодного симпозиума ACM-SIAM по дискретному алгоритму - SODA '06 . стр. 271–278. дои : 10.1145/1109557.1109588 . ISBN 978-0898716054 . , Эдмондс, Джефф (2011). «Разрезка торта на самом деле непростая задача». Транзакции ACM на алгоритмах . 7 (4): 1–12. CiteSeerX 10.1.1.146.1536 . дои : 10.1145/2000807.2000819 . S2CID 2440968 .
- ^ Этот рандомизированный рекурсивный алгоритм деления пополам аналогичен хорошо известному рандомизированному алгоритму ранжирования - поиску элемента с r -рангом в массиве чисел.