Жадное разбиение чисел

В информатике , жадное число разделы являются жадным алгоритмом для многопозиционного числа разделов . Он имитирует то, как дети выбирают команды для игры. Впервые он был проанализирован Рональдом Грэхемом в 1960-х годах в контексте проблемы планирования работы многопроцессорных систем . ^[1]^[2]^{: sec.5} В этом контексте его часто называют наибольшим временем обработки ( LPT ).

Входом в алгоритм является набор чисел S и параметр k . Требуемый результат - это разделение S на k подмножеств таким образом, чтобы суммы в подмножествах были как можно более близкими.

Алгоритм линейного времени [ править ]

Базовый алгоритм просто обрабатывает числа в произвольном порядке и итеративно добавляет следующее число к набору, в котором текущая сумма наименьшая. Алгоритм выполняется за время O ( n ). Он всегда возвращает раздел, в котором наибольшая сумма в большинстве случаев является оптимальной (минимальной) наибольшей суммой. ^[1] ${\ displaystyle 2 - {\ frac {1} {k}}}$

Улучшенный алгоритм [ править ]

Усовершенствованный алгоритм сначала сортирует числа в порядке убывания, а затем итеративно добавляет следующее по величине число к набору, в котором текущая сумма наименьшая.

Например, если входной набор равен S = {8,7,6,5,4} и k = 2, то результирующее разделение будет {8,5,4}, {7,6}, где сумма-разность равна 4. Если k = 3, то результирующее трехстороннее разбиение будет {8}, {7, 4}, {6, 5}, где сумма-разность равна 3.

Время работы этого алгоритма определяется сортировкой, которая занимает O ( n log n ) времени.

Алгоритм может не найти оптимального раздела. Например, в приведенном выше примере оптимальное разбиение {8,7}, {6,5,4}, где сумма-разность равна 0. Однако его субоптимальность ограничена как в худшем, так и в среднем случае:

В худшем случае наибольшая сумма в возвращенном разделе в большинстве случаев является оптимальной (минимальной) наибольшей суммой. ^[2]^:^sec.5 В частности, при k = 2 это соотношение составляет 7/6. ${\ displaystyle {\ frac {4} {3}} - {\ frac {1} {3k}}}$
В худшем случае наименьшая сумма в возвращенном разделе, по крайней мере, умножается на оптимальную (максимальную) наименьшую сумму. ^[3] Более тщательный анализ показывает, что соотношение самое большее , и оно жесткое. ^[4] В частности, когда k = 2, соотношение составляет 5/6. ${\ displaystyle {\ frac {3} {4}}}$ ${\ displaystyle {\ frac {3k-1} {4k-2}}}$
В среднем случае, если входные числа распределены равномерно в [0,1], то наибольшая сумма почти наверняка умножается на оптимум и является ожидаемым. ^[5] ${\ Displaystyle 1 + О (\ журнал {\ журнал {п}} / п)}$ ${\ Displaystyle 1 + О (1 / п)}$

Реализация [ править ]

Ниже приведен пример жадного алгоритма , написанный на Python .

def  find_partition ( numbers ):  "" "Разделить заданные числа на две серии с одинаковой суммой. Args:  numbers: набор чисел, например список целых чисел. Возврат:  два списка чисел.  ""»  = [] B = [] sum_A = 0 sum_B = 0 для п в отсортированных ( чисел , обратное = Правда ): если sum_A < sum_B : . Append ( п ) sum_A = sum_A + п остальное : Б . Append ( n ) сумма_B = сумма_B                                +  n  return  ( A ,  B )

Пример

>>> find_partition ([ 1 ,  2 ,  3 ,  4 ,  5 ]) ([4, 3], [5, 2, 1])

Точный алгоритм [ править ]

Полный жадный алгоритм (CGA) представляет собой точный алгоритм , то есть, он всегда находит оптимальное решение. Это работает следующим образом. После сортировки чисел в порядке убывания он строит k- мерное дерево. Каждому уровню соответствует номер, и каждая из k ветвей соответствует разному набору, в который можно поместить текущий номер. Для обхода дерева в порядке « сначала в глубину» требуется только O ( n ) пространства, но может потребоваться O ( n ^k) время. Среду выполнения можно улучшить, используя жадную эвристику: на каждом уровне сначала разработайте ветвь, в которой текущее число помещается в набор с наименьшей суммой. Этот алгоритм сначала находит жадное решение, а затем переходит к поиску лучших решений.

В случае k = 2 можно использовать несколько дополнительных эвристик для улучшения времени выполнения: ^[6]

В узле, в котором текущая разница сумм равна, по крайней мере, сумме всех оставшихся чисел, оставшиеся числа можно просто поместить в подмножество наименьшей суммы.
Если мы дойдем до листа, в котором разница сумм равна 0 или 1, то алгоритм может завершиться, поскольку это оптимальное значение.
Если суммы подмножеств в текущем узле равны, то мы можем поместить текущее число только в одно подмножество, тем самым уменьшив размер поддерева вдвое.
Последний номер может быть присвоен только подмножеству с меньшей суммой.

Обобщения [ править ]

В задаче справедливого распределения предметов есть n предметов и k человек, каждый из которых присваивает, возможно, разное значение каждому предмету. Цель состоит в том, чтобы разделить предметы между людьми настолько справедливо, насколько это возможно. Естественным обобщением алгоритма разбиения на жадные числа является алгоритм графа зависти . Это гарантирует, что распределение не вызывает зависти максимум для одного элемента (EF1).

Ссылки [ править ]

^ ^a ^b Грэм, Рон Л. (1966). «Границы некоторых аномалий многопроцессорной обработки» . Технический журнал Bell System . 45 (9): 1563–1581. DOI : 10.1002 / j.1538-7305.1966.tb01709.x . ISSN 1538-7305 .
^ ^a ^b Грэм, Рон Л. (1969-03-01). «Границы многопроцессорных временных аномалий» . Журнал СИАМ по прикладной математике . 17 (2): 416–429. DOI : 10.1137 / 0117039 . ISSN 0036-1399 .
^ Deuermeyer, Bryan L .; Friesen, Donald K .; Лэнгстон, Майкл А. (1 июня 1982 г.). «Планирование для максимизации минимального времени обработки процессора в многопроцессорной системе» . Журнал СИАМ по алгебраическим и дискретным методам . 3 (2): 190–196. DOI : 10.1137 / 0603019 . ISSN 0196-5212 .
^ Чирик, Янош; Келлерер, Ганс; Woeginger, Герхард (1992-06-01). «Точная граница LPT для максимизации минимального времени завершения» . Письма об исследованиях операций . 11 (5): 281–287. DOI : 10.1016 / 0167-6377 (92) 90004-M . ISSN 0167-6377 .
^ Френк, JBG; Кан, AHG Rinnooy (1986-06-01). «Скорость сходимости к оптимальности правила LPT» . Дискретная прикладная математика . 14 (2): 187–197. DOI : 10.1016 / 0166-218X (86) 90060-0 . ISSN 0166-218X .
^ Корф, Ричард Э. (1995-08-20). «От приближенных к оптимальным решениям: пример разделения чисел» . Материалы 14-й совместной международной конференции по искусственному интеллекту - Том 1 . IJCAI'95. Монреаль, Квебек, Канада: Morgan Kaufmann Publishers Inc .: 266–272. ISBN 978-1-55860-363-9.

[:2-1] Грэм, Рон Л. (1966). «Границы некоторых аномалий многопроцессорной обработки» . Технический журнал Bell System . 45 (9): 1563–1581. DOI : 10.1002 / j.1538-7305.1966.tb01709.x . ISSN 1538-7305 .

[:1-2] Грэм, Рон Л. (1969-03-01). «Границы многопроцессорных временных аномалий» . Журнал СИАМ по прикладной математике . 17 (2): 416–429. DOI : 10.1137 / 0117039 . ISSN 0036-1399 .

[3] Deuermeyer, Bryan L .; Friesen, Donald K .; Лэнгстон, Майкл А. (1 июня 1982 г.). «Планирование для максимизации минимального времени обработки процессора в многопроцессорной системе» . Журнал СИАМ по алгебраическим и дискретным методам . 3 (2): 190–196. DOI : 10.1137 / 0603019 . ISSN 0196-5212 .

[4] Чирик, Янош; Келлерер, Ганс; Woeginger, Герхард (1992-06-01). «Точная граница LPT для максимизации минимального времени завершения» . Письма об исследованиях операций . 11 (5): 281–287. DOI : 10.1016 / 0167-6377 (92) 90004-M . ISSN 0167-6377 .

[5] Френк, JBG; Кан, AHG Rinnooy (1986-06-01). «Скорость сходимости к оптимальности правила LPT» . Дискретная прикладная математика . 14 (2): 187–197. DOI : 10.1016 / 0166-218X (86) 90060-0 . ISSN 0166-218X .

[:0-6] Корф, Ричард Э. (1995-08-20). «От приближенных к оптимальным решениям: пример разделения чисел» . Материалы 14-й совместной международной конференции по искусственному интеллекту - Том 1 . IJCAI'95. Монреаль, Квебек, Канада: Morgan Kaufmann Publishers Inc .: 266–272. ISBN 978-1-55860-363-9.

[1]