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

В информатике — многостороннее разделение чисел это проблема разделения мультимножества чисел на фиксированное количество подмножеств так, чтобы суммы подмножеств были как можно более похожими. Впервые он был представлен Рональдом Грэмом в 1969 году в контексте проблемы планирования идентичных машин . Задача параметризуется положительным целым числом k и называется k -сторонним числовым разделением . Входными данными для задачи является мультимножество S чисел (обычно целых), сумма которых равна k*T .

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

• Минимизируйте разницу между наибольшей и наименьшей суммами. Эта цель часто встречается в статьях о многостороннем разделении чисел, а также в статьях, посвященных физическим приложениям.
• Минимизируйте наибольшую сумму. Эта цель эквивалентна одной цели для планирования идентичных машин . Имеется k одинаковых процессоров, и каждое число в S представляет время, необходимое для выполнения задания одного процессора. Цель состоит в том, чтобы распределить задания между процессорами так, чтобы время выполнения (время завершения последнего задания) было минимальным.
• Максимизируйте наименьшую сумму. Эта цель соответствует применению справедливого распределения статей , в частности максимальной доли . Это также проявляется в проблемах манипулирования голосованием. и в определении последовательности действий по техническому обслуживанию модульных газотурбинных авиационных двигателей. Предположим, имеется несколько k двигателей, которые необходимо проработать как можно дольше. Для работы двигателя необходима определенная важная часть. Имеется набор S деталей, каждая из которых имеет разный срок службы. Цель состоит в том, чтобы распределить детали по двигателям таким образом, чтобы кратчайший срок службы двигателя был как можно большим.

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

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

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

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

Алгоритмы аппроксимации

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

Минимизация наибольшей суммы

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

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

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

• Грэм представил следующий алгоритм. Для любого целого числа r>0 выберите r самых больших чисел в S и оптимально разбейте их. Затем распределите оставшиеся числа произвольно. Этот алгоритм имеет коэффициент аппроксимации $1+{\frac {1-1/k}{1+\lfloor r/k\rfloor }}$ и это происходит во времени $O(2^{r}n\log {n})$.
• Сахни представил PTAS, который достигает (1+ε)OPT во времени $O(n\cdot (n^{2}/\epsilon )^{k-1})$. Это FPTAS, если k фиксировано. Для k =2 время выполнения улучшается до $O(n^{2}/\epsilon )$. Алгоритм использует технику, называемую интервальным разделением .
• Хохбаум и Шмойс представил следующие алгоритмы, которые работают, даже если k является частью входных данных.
  • Для любого r >0 алгоритм с коэффициентом аппроксимации не более (6/5+2 ^{− р} ) во времени $O(n(r+\log {n}))$.
  • Для любого r >0 алгоритм с коэффициентом аппроксимации не более (7/6+2 ^{− р} ) во времени $O(n(rk^{4}+\log {n}))$.
  • Для любого ε >0 алгоритм со степенью аппроксимации не более (1+ε) за время $O((n/\varepsilon )^{(1/\varepsilon ^{2})})$ . Это ПТАС .

Максимизация наименьшей суммы

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

• Для жадного разделения чисел , если числа не отсортированы, то коэффициент аппроксимации в худшем случае равен 1/ k . Сортировка чисел увеличивает коэффициент аппроксимации до 5/6, когда k = 2, и ${\frac {3k-1}{4k-2}}$ в общем и то тесно.
• Фёгингер представил PTAS, который достигает коэффициента аппроксимации $1-{\varepsilon }$ вовремя $O(c_{\varepsilon }n\log {k})$, где $c_{\varepsilon }$ огромная константа, экспоненциальная относительно требуемого коэффициента аппроксимации ε. Алгоритм использует алгоритм Ленстры для целочисленного линейного программирования .
• FPTAS Сахни работает и для этой цели.

Максимизация суммы произведений

Слух изучает проблему, цель которой состоит в том, чтобы максимизировать сумму по каждому множеству i в 1,..., k , произведения чисел в множестве i . В более общем варианте каждый набор i может иметь вес w _i , и цель состоит в том, чтобы максимизировать взвешенную сумму произведений. Эта задача имеет точное решение, работающее за время O( n ² ).

PTAS для общих целевых функций

Пусть C _i (для i между 1 и k ) будет суммой подмножества i в данном разделе. Вместо минимизации целевой функции max( C _i ) можно минимизировать целевую функцию max( f ( C _i )), где f — любая фиксированная функция. Аналогичным образом можно минимизировать сумму целевой функции ( f ( C _i )), или максимизировать min (f ( C _i )), или максимизировать сумму ( f ( C _i )). Алон, Азар, Вегингер и Ядид представил общие PTAS (обобщающие PTAS Санхи, Хохбаума, Шмойса и Вёгингера) для этих четырех задач. Их алгоритм работает для любого f, удовлетворяющего следующим двум условиям:

1. Сильное условие непрерывности, называемое условием F* : для любого ε>0 существует δ>0 такое, что, если | y - x |<δ x , то |f( y )-f( x )|<ε f ( x ).
2. Выпуклость (для задач минимизации) или вогнутость (для задач максимизации).

Время работы их PTAS-ов линейно по n (количеству входов), но экспоненциально по точности аппроксимации. PTAS для минимизации sum( f ( C _i )) основан на некоторых комбинаторных наблюдениях:

1. Пусть L := средняя сумма в одном подмножестве (1/ k сумма всех входов). Если некоторые входные данные x не меньше L , то существует оптимальное разбиение, в котором одна часть содержит только x . Это следует из выпуклости f . Следовательно, входные данные могут быть предварительно обработаны путем присвоения каждому такому входному набору уникального подмножества. После этой предварительной обработки можно предположить, что все входные данные меньше L .
2. Существует оптимальное разбиение, в котором суммы всех подмножеств находятся строго между L /2 и 2 L ( L /2 < C _i < 2 L для всех i из 1,..., k ). В частности, разбиение, минимизирующее сумму квадратов C _i ² среди всех оптимальных разбиений удовлетворяет этим неравенствам.

PTAS использует метод округления входных данных . Учитывая входную последовательность S = ( v ₁ ,..., v _n ) и положительное целое число d , округленная последовательность S ^# ( d ) определяется следующим образом:

• Для любого v _j > L/d последовательность S ^# ( d ) содержит входные данные v _j ^# что представляет собой v _j, округленное до следующего целого числа, кратного L / d ² . Обратите внимание, что v _j ≤ v _j ^# < v _j + L / d ² , и Л/д ² < v _j / d , поэтому v _j ^# < ( d +1) v _j / d.
• Кроме того, последовательность S ^# ( d ) содержит некоторые входные данные, равные L/d . Количество этих входов определяется таким образом, чтобы сумма всех этих новых входов равнялась сумме всех входов в S. ^# ( d ), которые не превышают L/d , округленные до следующего целого числа, кратного L/d (например, если сумма всех «коротких» входов в S равна 51,3 L/d , то 52 новых L/d входа добавляются к S ^# ( д )).

В С ^# ( d ), все входные данные являются целыми кратными L / d ² . Более того, два приведенных выше наблюдения справедливы для S ^# ( г ) тоже:

1. Пусть L ^# быть средней суммой в одном подмножестве (1/ k сумма всех входов в S ^# ( д )). По конструкции L ^# как минимум Л. это Поскольку L само по себе является целым кратным L / d ² , округление входных данных, меньших, чем L, не может сделать их больше, чем L . Следовательно, все входы в S ^# ( d ) меньше L и, следовательно, меньше L ^# .
2. Существует оптимальное разбиение S ^# ( d ), в котором все суммы подмножеств находятся строго между L ^# /2 и 2 л ^# . Следовательно, все подмножества содержат не более 2 d элементов (поскольку все входы в S ^# ( d ) не менее L / d ).

На основании этих наблюдений все входные данные в S ^# ( d ) имеют вид hL / d ² , где h — целое число в диапазоне $(d,d+1,\ldots ,d^{2})$. Следовательно, входные данные можно представить как целочисленный вектор. $\mathbf {n} =(n_{d},n_{d+1},\ldots ,n_{d^{2}})$, где $n_{h}$ это количество гл / д ² входы в S ^# ( д ). При этом каждое подмножество можно представить в виде целочисленного вектора $\mathbf {t} =(t_{d},t_{d+1},\ldots ,t_{d^{2}})$, где $x_{h}$ это количество гл / д ² входы в подмножестве. Тогда сумма подмножества равна $C(\mathbf {t} )=\sum _{h=d}^{d^{2}}t_{h}\cdot (hL/d^{2})$. Обозначим через $T$, набор векторов $\mathbf {t}$ с $L^{\#}/2<C(\mathbf {t} )<2L^{\#}$. Поскольку сумма элементов такого вектора не превосходит 2 d , общее количество этих элементов меньше ${(d^{2})}^{2d}=d^{4d}$, так $|T|\leq d^{4d}$.

Существует два разных способа найти оптимальное решение задачи S. ^# ( д ). Один из способов использует динамическое программирование: время выполнения представляет собой полином, показатель степени которого зависит от d . Другой способ использует алгоритм Ленстры для целочисленного линейного программирования.

Решение для динамического программирования

Определять $VAL(k,\mathbf {n} )$ как оптимальное (минимальное) значение суммы целевой функции ( f ( C _i )), когда входной вектор равен $\mathbf {n} =(n_{d},n_{d+1},\ldots ,n_{d^{2}})$ и его необходимо разделить на k подмножеств, среди всех разделов, в которых все суммы подмножеств находятся строго между L ^# /2 и 2 л ^# .

Эту проблему можно решить с помощью следующего рекуррентного соотношения :

• $VAL(0,\mathbf {0} )=0$ - поскольку их объективная сумма пуста.
• $VAL(1,\mathbf {n} )=f(C(\mathbf {n} ))$ если $L^{\#}/2<C(\mathbf {n} ))<2L^{\#}$ - поскольку все входы должны быть отнесены к одному подмножеству, его сумма равна $C(\mathbf {n} )$.
• $VAL(1,\mathbf {n} )=\infty$ в противном случае – поскольку мы не рассматриваем оптимальные решения вне этого диапазона.
• $VAL(k,\mathbf {n} )=\min _{\mathbf {t} \leq \mathbf {n} ,\mathbf {t} \in T}[f(C(\mathbf {t} ))+VAL(k-1,\mathbf {n} -\mathbf {t} )]$ для всех $k\geq 2$: проверяем все варианты k -го подмножества, и объединяем его с оптимальным разбиением остатка на k -1 подмножества.

Для каждого k и n рекуррентное соотношение требует проверки не более $|T|$ векторы. векторов n не превышает Общее количество проверяемых $n^{d^{2}}$, где n — исходное количество входов. Следовательно, время выполнения алгоритма динамического программирования равно $O(k\cdot n^{d^{2}}\cdot d^{4d})$. Оно линейно по n для любого фиксированного d .

Решение для целочисленного линейного программирования

Для каждого вектора t в T введите переменную x _t, обозначающую количество подмножеств с этой конфигурацией. Минимизация суммы ( f ( C _i )) может быть достигнута путем решения следующей ILP:

• Свернуть $\sum _{\mathbf {t} \in T}x_{\mathbf {t} }\cdot f(C(\mathbf {t} ))$
• при условии $\sum _{\mathbf {t} \in T}x_{\mathbf {t} }=k$ (общее количество подмножеств)
• и $\sum _{\mathbf {t} \in T}x_{\mathbf {t} }\cdot \mathbf {t} =\mathbf {n}$ (общий вектор входов)
• и $x_{\mathbf {t} }\geq 0$.

Число переменных не более $d^{4d}$, а количество уравнений $d^{4d}+d^{2}-d+2$ - обе константы не зависят от n , k . Следовательно, алгоритм Ленстры можно использовать . Время его выполнения экспоненциально в размерности ( $d^{4d}$), но полиномиально в двоичном представлении коэффициентов, находящихся в O(log( n )). Построение самой ILP занимает время O( n ).

Преобразование решения из округленного в исходный экземпляр

Следующие леммы связывают разбиения округленного экземпляра S ^# ( d ) и исходный экземпляр S .

• Для каждого раздела S с суммами C _i существует раздел S ^# ( d ) с суммами C _i ^# , где $C_{i}-{\frac {L}{d}}\leq C_{i}^{\#}\leq {\frac {d+1}{d}}C_{i}+{\frac {L}{d}}$.
• Для каждого раздела S ^# ( d ) с суммами C _i ^# , существует разбиение S с суммами C _i , где ${\frac {d}{d+1}}C_{i}^{\#}-2{\frac {L}{d}}\leq C_{i}\leq C_{i}^{\#}+{\frac {L}{d}}$, и его можно найти за время O( n ).

При заданной точности аппроксимации ε>0 пусть δ>0 — константа, соответствующая ε/3, существование которой гарантируется условием F*. Позволять $d:=\lceil 5/\delta \rceil$. Можно показать, что преобразованное разбиение S имеет общую стоимость не более $(1+{\frac {\epsilon }{3}})\cdot OPT\leq (1+\epsilon )\cdot OPT$, поэтому коэффициент аппроксимации равен 1+ε.

Отсутствие PTAS для некоторых целевых функций.

В отличие от приведенного выше результата, если мы возьмем f( x ) = 2 ^х , или f( x )=( x -1) ² , то PTAS для минимизации sum( f ( C _i )) не существует, если P=NP . Обратите внимание, что эти f( x ) выпуклы, но они не удовлетворяют условию F*, приведенному выше. Доказательство основано на задаче о разделении .

Точные алгоритмы

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

• Псевдополиномиальное разбиение числа по времени занимает O ( n ( k − 1) m ^{к - 1} ) память, где m — наибольшее число во входных данных. Это практично только тогда , когда k =2 или когда k =3 и входные данные представляют собой небольшие целые числа.
• Полный жадный алгоритм (CGA) учитывает все разделы путем построения k - арного дерева . Каждый уровень в дереве соответствует входному числу, где корень соответствует наибольшему числу, уровень ниже — следующему по величине числу и т. д. Каждая из k ветвей соответствует отдельному набору, в который можно поместить текущее число. . Обход дерева в порядке глубины требует всего O( n ) пространства, но может занять O( k ^н ) время. Время выполнения можно улучшить, используя жадную эвристику: на каждом уровне сначала разрабатывайте ветвь, в которой текущее число помещается в набор с наименьшей суммой. Этот алгоритм сначала находит решение, найденное путем жадного разделения чисел , а затем переходит к поиску лучших решений.
• Полный алгоритм Кармаркара-Карпа (CKK) учитывает все разделы, строя дерево степени $k!$ . Каждому уровню соответствует пара k -кортежей, и каждый из $k!$ ветвей соответствует другому способу объединения этих k -кортежей. Этот алгоритм сначала находит решение, найденное методом наибольшей разности , а затем переходит к поиску лучших решений. Для k =2 и k =3 CKK работает существенно быстрее, чем CGA в случайных экземплярах. Преимущество CKK перед CGA в последнем случае гораздо больше (когда существует равный раздел) и может составлять несколько порядков. На практике при k = 2 задачи произвольного размера могут быть решены с помощью CKK, если числа имеют не более 12 значащих цифр s; при k =3 не более 6 значащих цифр. CKK также может работать как алгоритм в любое время : сначала он находит решение KK, а затем, по мере того, как позволяет время, находит все более лучшие решения (возможно, для достижения оптимальности требуется экспоненциальное время в худших случаях). При k ≥ 4 CKK становится намного медленнее, а CGA работает лучше.
• Корф, Шрайбер и Моффитт представили гибридные алгоритмы, сочетающие CKK, CGA и другие методы из задачи суммы подмножества и задачи упаковки контейнеров для достижения еще большей производительности. Их журнальная статья за 2018 год. суммирует работы из нескольких предыдущих документов конференции:
  • Рекурсивное разделение чисел (RNP) использует CKK для k = 2, но для k > 2 он рекурсивно разбивает S на подмножества и разбивает k пополам.
  • Гибридное рекурсивное разделение чисел (HRNP).
  • Улучшено заполнение корзины.
  • Улучшенные стратегии поиска.
  • Алгоритм нескольких машин.
  • Кэшированное итеративное ослабление (CIW).
  • Последовательное разбиение .

Сокращение до упаковки в мусорные контейнеры

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

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

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

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

Варианты

В задаче разделения сбалансированных чисел существуют ограничения на количество элементов, которые можно отнести к каждому подмножеству (они называются ограничениями мощности ).

Другой вариант — разбиение многомерных чисел .

Приложения

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

Реализации

• Python: пакет prtpy содержит код для различных алгоритмов разделения чисел и упаковки ячеек.