Многостороннее разделение номеров

В информатике , многоходовое число разделы являются проблемой разбиения мультимножества чисел на фиксированное число подмножеств, такие , что суммы подмножеств являются как можно более близкими. Впервые он был представлен Рональдом Грэхемом в 1969 году в контексте проблемы планирования многопроцессорных систем . ^{[1] : sec.5} Задача параметризуется положительным целым числом k и называется разбиением по k- путям . ^[2] На вход этой проблемы является мультимножеством S чисел (обычно целые числа), сумма которых равна к * Т .

Связано решение проблемы является решить , следует ли S может быть разделена на K подмножеств , таких , что сумма каждого подмножества именно Т . Также существует проблема оптимизации : найти такое разбиение S на k подмножеств, чтобы k сумм были «как можно ближе». Точную цель оптимизации можно определить несколькими способами:

• Сведите к минимуму разницу между самой большой и самой маленькой суммой. Эта цель часто встречается в статьях о многомерном разбиении чисел, а также в статьях, связанных с физическими приложениями. ^[3]
• Минимизируйте самую большую сумму. Эта цель соответствует частному случаю многопроцессорного планирования, в котором все процессоры идентичны. Есть k идентичных процессоров, и каждое число в S представляет время, необходимое для выполнения однопроцессорной задачи. Цель состоит в том, чтобы разделить задания между процессорами так, чтобы время изготовления (время завершения последнего задания) было минимальным.
• Максимизируйте самую маленькую сумму. Эта цель соответствует применению справедливого распределения статей , особенно максимальной доли . Это также появляется в задачах манипулирования голосованием ^[4] и в последовательности действий по обслуживанию модульных газотурбинных авиационных двигателей. ^[5]

Эти три целевые функции эквивалентны, когда k = 2, но все они разные, когда k ≥3. ^[6]

Все эти проблемы являются NP-трудной , ^[7] , но существуют различные алгоритмы , которые решают ее эффективно во многих случаях.

Некоторые тесно связанные проблемы:

• Проблема разбиения - частный случай множественного разбиения чисел, в котором количество подмножеств равно 2.
• Задача 3-разбиения - другая и более сложная задача, в которой количество подмножеств не считается фиксированным параметром, а определяется входными данными (количество наборов - это количество целых чисел, деленное на 3).
• Проблема упаковки контейнеров - двойная задача, в которой общая сумма в каждом подмножестве ограничена, но k является гибким; цель состоит в том, чтобы найти разбиение с наименьшим возможным k . Задачи оптимизации тесно связаны между собой : оптимальное количество д -sized бункеров не превосходит к , тогда и только тогда размер оптимальной величине из подмножества в K -разбиения не превосходит г . ^[8]
• Проблема многопроцессорного планирования - более общая проблема, в которой разные процессоры могут иметь разные скорости.

Алгоритмы аппроксимации [ править ]

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

Минимизация самой большой суммы [ править ]

Коэффициент аппроксимации в этом контексте представляет собой наибольшую сумму в решении, возвращаемую алгоритмом, деленную на наибольшую сумму в оптимальном решении (отношение больше 1).

• Жадное разбиение чисел (также называемоеметодом наибольшего времени обработки ) перебирает числа и помещает каждое число в набор, текущая сумма которого является наименьшей. Если числа не отсортированы, время выполнения равно O ( n ), а коэффициент аппроксимации - не больше. Сортировка чисел увеличивает время выполнения до O ( n log n ) и улучшает коэффициент приближения до 7/6, когда k = 2, ив целом. Если числа распределены равномерно в [0,1], то коэффициент аппроксимации не более чем почти наверняка и являетсяожидаемым.${\ displaystyle 2-1 / k}$${\ displaystyle 4/3 + 1 / 3k}$${\ Displaystyle 1 + О (\ журнал {\ журнал {п}} / п)}$ ${\ Displaystyle 1 + О (1 / п)}$
• Метод наибольшей разности (также называемый алгоритмом Кармаркара-Карпа ) сортирует числа в порядке убывания и многократно заменяет числа на их разности. Сложность выполнения - O ( n log n ). В худшем случае его коэффициент аппроксимации аналогичен - не более 7/6 для k = 2 и не более чемв целом. Однако в среднем случае он работает намного лучше, чем жадный алгоритм: для k = 2, когда числа распределены равномерно в [0,1], его коэффициент аппроксимации непревышаетожидаемого. Он также лучше работает в имитационных экспериментах.${\ displaystyle 4/3 + 1 / 3k}$${\ displaystyle 1 + 1 / n ^ {\ Theta (\ log {n})}}$
• Алгоритм Multifit использует бинарный поиск в сочетании с алгоритмом для упаковки в контейнерах . В худшем случае его продолжительность составляет не более 8/7 для k = 2 и не более 13/11 в целом.

Было разработано несколько схем полиномиальной аппроксимации (PTAS):

• Грэм ^{[9] : раздел 6} представил следующий алгоритм. Для любого целого числа r> 0 выберите r наибольших чисел в S и разделите их оптимальным образом. Затем произвольно распределите оставшиеся числа. Этот алгоритм имеет коэффициент аппроксимации и работает во времени .${\ displaystyle 1 + {\ frac {1-1 / k} {1+ \ lfloor r / k \ rfloor}}}$${\ Displaystyle О (2 ^ {г} п \ журнал {п})}$
• Санхи ^[10] представил PTAS для случая, когда k не является частью ввода.
• Хохбаум и Шмойс ^[11] представили следующие алгоритмы, которые работают, даже когда k является частью входных данных.
  • Для любого r > 0 алгоритм с коэффициентом аппроксимации не более (6/5 + 2 ^{- r} ) по времени .${\ Displaystyle О (п (г + \ журнал {п}))}$
  • Для любого r > 0 алгоритм с коэффициентом аппроксимации не более (7/6 + 2 ^{- r} ) по времени .${\ Displaystyle О (п (гк ^ {4} + \ журнал {п}))}$
  • Для любого ε > 0 алгоритм с коэффициентом аппроксимации не более (1 + ε) по времени .${\ Displaystyle О ((п / \ varepsilon) ^ {(1 / \ varepsilon ^ {2})})}$
• Существуют вариации этой идеи, которые представляют собой полностью полиномиальные схемы аппроксимации для задачи о сумме подмножеств, а значит, и для задачи о разбиении. ^[12]

Максимизация наименьшей суммы [ править ]

Коэффициент аппроксимации в этом контексте - это наименьшая сумма в решении, возвращаемом алгоритмом, деленная на наименьшую сумму в оптимальном решении (отношение меньше 1).

• Для жадного разделения чисел, если числа не отсортированы, тогда коэффициент аппроксимации в наихудшем случае равен 1 / k . ^[5] Сортировка чисел увеличивает коэффициент аппроксимации до 5/6, когда k = 2, и в целом, и это точно. ^[13]${\displaystyle {\frac {3k-1}{4k-2}}}$

• Woeginger ^[5] представил PTAS, который достигает коэффициента аппроксимации во времени , где огромная константа, являющаяся экспоненциальной в требуемом коэффициенте аппроксимации ε. Алгоритм использует алгоритм Ленстры для целочисленного линейного программирования .${\displaystyle 1-{\varepsilon }}$${\displaystyle O(c_{\varepsilon }n\log {k})}$${\displaystyle c_{\varepsilon }}$

Другие целевые функции [ править ]

Пусть s _i (для i между 1 и k ) будет суммой подмножества i в данном разделе. Вместо минимизации целевой функции max ( s _i ) можно минимизировать целевую функцию max ( f ( s _i )), где f - любая фиксированная функция. Точно так же можно минимизировать сумму целевой функции ( f ( s _i )), или максимизировать min (f ( s _i )), или максимизировать сумму ( f ( s _i )). Алон, Азар, Вегингер и Ядид ^[14]представил общий PTAS, который работает для любого f, удовлетворяющего определенному условию непрерывности, и является выпуклым (для задач минимизации) или вогнутым (для задач максимизации). Их алгоритм обобщает PTAS-ы Санхи, Хохбаума, Шмойса и Вегингера. Время работы их PTAS линейно по n , но экспоненциально по точности аппроксимации. Они показывают, что для некоторых функций f, которые не удовлетворяют этим условиям, PTAS не существует, если P = NP .

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

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

• Псевдополином число раз разбиение занимает O ( N ( K - 1) т ^{к - 1} ) память, где т наибольшее число во входных данных. Это практично, только когда k = 2 или когда k = 3 и входы - небольшие целые числа. ^[15]
• Полный Жадный алгоритм (CGA) рассматривает все разделы, построив K - ичной дерева . Каждый уровень в дереве соответствует входному числу, где корень соответствует наибольшему числу, уровень ниже - следующему наибольшему числу и т. Д. Каждая из k ветвей соответствует разному набору, в который можно поместить текущее число. . Для обхода дерева в порядке « сначала глубина» требуется только O ( n ) пространства, но может потребоваться время O ( k ⁿ ). Среду выполнения можно улучшить, используя жадную эвристику: на каждом уровне сначала разработайте ветвь, в которой текущее число помещается в набор с наименьшей суммой. Этот алгоритм сначала находит решение, найденноежадное разбиение чисел , но затем переходит к поиску лучших решений.
• Полный алгоритм Кармаркар-Karp (ЦКК) рассматривает все разделы с помощью построения дерева степени . Каждый уровень соответствует паре k -элементов, и каждая из ветвей соответствует разному способу объединения этих k -элементов. Этот алгоритм сначала находит решение, найденное методом наибольшей разности , но затем переходит к поиску лучших решений. Для k = 2 и k = 3 CKK работает значительно быстрее, чем CGA на случайных экземплярах. Преимущество CKK перед CGA в последнем случае (когда существует равный раздел) намного больше и может достигать нескольких порядков. На практике с k${\displaystyle k!}$${\displaystyle k!}$= 2, задачи произвольного размера могут быть решены CKK, если числа имеют не более 12 значащих цифр s; при k = 3 не более 6 значащих цифр. ^[16] CKK также может работать как алгоритм в любое время  : он сначала находит решение KK, а затем находит все более лучшие решения, когда позволяет время (возможно, для достижения оптимальности в худших случаях требуется экспоненциальное время). ^[17] Для k ≥ 4 CKK становится намного медленнее, а CGA работает лучше.
• Рекурсивное разделение чисел (RNP) использует CKK для k = 2, но для k > 2 оно рекурсивно разбивает S на подмножества и разбивает k пополам. Он работает намного лучше, чем CKK. ^[15]
• Корф, Шрайбер и Моффитт представили гибридные алгоритмы, объединяющие CKK, CGA и другие методы из задачи суммы подмножества и задачи упаковки бункеров для достижения еще лучшей производительности. ^{[18] [19] [20] [21]}

Редукция к упаковке в контейнеры [ править ]

Проблема упаковки бункера решается многими быстро. Решатель BP может использоваться для поиска оптимального разделения чисел. ^[22] Идея состоит в том, чтобы использовать двоичный поиск, чтобы найти оптимальное время изготовления. Для инициализации бинарного поиска нам нужны нижняя и верхняя границы:

• Ниже приведены некоторые нижние границы диапазона изготовления: (сумма S ) / k - среднее значение для подмножества, s ₁ - наибольшее число в S и s _k + s _{k + 1} - размер корзины в оптимальном разделе только самые большие числа k +1.
• Некоторые верхние границы могут быть получены с помощью эвристических алгоритмов, таких как жадный алгоритм или KK.

Учитывая нижнюю и верхнюю границы, запустите решатель BP со средним размером ячейки: = (нижний + верхний) / 2.

• Если результат содержит более k ячеек, тогда оптимальное время изготовления должно быть больше: установите от меньшего до среднего и повторите.
• Если результат содержит не более k ячеек, то оптимальное время изготовления может быть меньше, увеличивая до среднего и повторяя.

Варианты [ править ]

В задаче сбалансированного разделения чисел мощность каждого подмножества должна быть либо минимальной ( n / k), либо максимальной (n / k), т. Е. Мощность всех подмножеств должна быть одинаковой вплоть до 1. ^[23]

Недавний вариант - это многомерное многомерное числовое разделение. ^[24]

Приложения [ править ]

Одно из применений проблемы раздела - манипулирование выборами . Предположим, есть три кандидата (A, B и C). Единственный кандидат должен быть избран с использованием правила голосования вето, т. Е. Каждый избиратель накладывает вето на одного кандидата, и побеждает кандидат с наименьшим количеством вето. Если коалиция желает обеспечить избрание C, ей следует разделить право вето между A и B, чтобы максимально увеличить количество вето, которое получает каждый из них. Если голоса взвешены, тогда проблема может быть сведена к проблеме разделения, и, таким образом, ее можно эффективно решить с помощью CKK. Для k = 2 то же самое верно и для любого другого правила голосования, основанного на подсчете очков. Однако для k > 2 и других правил голосования требуются некоторые другие методы. ^[25]

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