Метод наибольшей разности
Алгоритм решения задачи разбиения

В информатике наибольший метод разности — это алгоритм решения проблемы разбиения и многоканального разбиения чисел . Его также называют алгоритмом Кармаркара–Карпа в честь его создателей Нарендры Кармаркара и Ричарда М. Карпа . [1] Его часто сокращают до LDM. [2] [3]

Алгоритм

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

  1. Расположите числа от большего к меньшему.
  2. Замените наибольшее и второе по величине числа их разностью.
  3. Если осталось два или более чисел, вернитесь к шагу 1.
  4. Используя возврат , вычислите раздел.

Двустороннее разделение

При k = 2 основной шаг (2) работает следующим образом.

  • Возьмите два наибольших числа в S , удалите их из S и вставьте их разность (это представляет собой решение поместить каждое из этих чисел в другое подмножество).
  • Продолжайте таким образом, пока не останется одно число. Это одно число представляет собой разницу в суммах между двумя подмножествами.

Например, если S = ​​{8,7,6,5,4}, то результирующие наборы разностей будут {6,5,4,1} после изъятия двух наибольших чисел {8,7} и подстановки разности 8-7=1 обратно; Повторяем шаги, и тогда у нас будет {4,1,1}, затем {3,1}, затем {2}.

Шаг 3 создает подмножества в разбиении путем возврата назад. Последний шаг соответствует {2},{}. Затем 2 заменяется на 3 в одном наборе и на 1 в другом наборе: {3},{1}, затем {4},{1,1}, затем {4,5}, {1,6}, затем {4,7,5}, {8,6}, где сумма-разность действительно равна 2.

Сложность выполнения этого алгоритма определяется шагом 1 (сортировкой), который занимает O( n log n ).

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

  • Если числа равномерно распределены в [0,1], то ожидаемая разница между двумя суммами равна . Это также подразумевает, что ожидаемое отношение между максимальной суммой и оптимальной максимальной суммой равно . [3] н − Θ ( бревно ⁡ ( н ) ) ) {\displaystyle n^{-\Theta (\log(n)))}} 1 + н − Θ ( бревно ⁡ ( н ) ) ) {\displaystyle 1+n^{-\Тета (\log(n)))}}
  • Если элементов не более 4, LDM возвращает оптимальное разбиение.
  • LDM всегда возвращает раздел, в котором наибольшая сумма не превышает оптимума более чем в 7/6 раз. [4] Этого недостаточно, когда имеется 5 или более элементов. [2]
  • На случайных примерах этот приблизительный алгоритм работает намного лучше, чем жадное разбиение чисел . Однако он все еще плох для примеров, где числа экспоненциально зависят от размера набора. [5]

Многоканальное разбиение

Для любого k ≥ 2 алгоритм можно обобщить следующим образом. [2]

  • Первоначально для каждого числа i в S строится k -кортеж подмножеств, в котором одно подмножество — это { i }, а остальные k -1 подмножеств пусты.
  • В каждой итерации выбираем два k -кортежа A и B , в которых разница между максимальной и минимальной суммой самая большая, и объединяем их в обратном порядке размеров, т. е.: наименьшее подмножество в A с наибольшим подмножеством в B , второе по величине подмножество в A со вторым по величине в B и т. д.
  • Продолжайте таким образом, пока не останется один раздел.

Примеры:

  • Если S = ​​{8,7,6,5,4} и k =2, то начальные разбиения будут ({8},{}), ({7},{}), ({6},{}), ({5},{}), ({4},{}). После первого шага мы получаем ({6},{}), ({5},{}), ({4},{}), ({8},{7}). Затем ({4},{}), ({8},{7}), ({6},{5}). Затем ({4,7},{8}), ({6},{5}) и, наконец, ({4,7,5},{8,6}), где сумма-разность равна 2; это то же самое разбиение, что описано выше.
  • Если S = ​​{8,7,6,5,4} и k =3, то начальные разбиения будут ({8},{},{}), ({7},{},{}), ({6},{},{}), ({5},{},{}), ({4},{},{}). После первого шага получаем ({8},{7},{}), ({6},{},{}), ({5},{},{}), ({4},{},{}). Затем ({5},{},{}), ({4},{},{}), ({8},{7},{6}). Затем ({5},{4},{}), ({8},{7},{6}) и, наконец, ({5,6},{4,7},{8}), где сумма-разность равна 3.
  • Если S = ​​{5,5,5,4,4,3,3,1} и k = 3, то после 7 итераций мы получаем разбиение ({4,5},{1,4,5},{3,3,5}). [2] Это решение не является оптимальным; лучшее разбиение обеспечивается группировкой ({5,5},{3,3,4},{1,4,5}).

Имеются данные, подтверждающие хорошую эффективность LDM: [2]

  • Эксперименты по моделированию показывают, что когда числа равномерно случайны в [0,1], LDM всегда работает лучше (т. е. создает разбиение с меньшей наибольшей суммой), чем жадное разбиение чисел . Он работает лучше, чем алгоритм multifit , когда количество элементов n достаточно велико. Когда числа равномерно случайны в [ o , o +1], начиная с некоторого o >0, производительность LDM остается стабильной, в то время как производительность multifit ухудшается по мере увеличения o . Для o >0,2 LDM работает лучше.
  • Пусть f* будет оптимальной наибольшей суммой. Если все числа больше f */3, то LDM возвращает оптимальное решение. В противном случае LDM возвращает решение, в котором разница между наибольшей и наименьшей суммой не превышает наибольшее число, которое не больше f */3.
  • Когда имеется не более k +2 элементов, LDM является оптимальным.
  • Когда число элементов n находится в диапазоне от k +2 до 2 k , наибольшая сумма в разбиении LDM в большинстве случаев равна оптимальной, 4 3 − 1 3 ( н − к − 1 ) {\displaystyle {\frac {4}{3}}-{\frac {1}{3(nk-1)}}}
  • Во всех случаях наибольшая сумма в разбиении LDM в большинстве случаев является оптимумом, а в некоторых случаях она по крайней мере в разы больше оптимума. 4 3 − 1 3 к {\displaystyle {\frac {4}{3}}-{\frac {1}{3k}}} 4 3 − 1 3 ( к − 1 ) {\displaystyle {\frac {4}{3}}-{\frac {1}{3(k-1)}}}
  • Для двухстороннего разбиения, когда входные данные представляют собой равномерно распределенные случайные величины, ожидаемая разница между наибольшей и наименьшей суммой составляет . [3] н − Θ ( бревно ⁡ н ) {\displaystyle n^{-\Theta (\log n)}}

Сбалансированное двухстороннее разделение

Было разработано несколько вариантов LDM для задачи разбиения сбалансированных чисел , в которой все подмножества должны иметь одинаковую мощность (до 1).

Метод парных разностей (PDM) работает следующим образом. [6]

  1. Расположите числа от большего к меньшему.
  2. Замените числа №1 и №2 на их разность; №3 и №4 на их разность и т. д.
  3. Если осталось два или более чисел, вернитесь к шагу 1.
  4. Используя возврат , вычислите раздел.

PDM имеет средние свойства хуже, чем LDM. Для двухстороннего разбиения, когда входы являются равномерно распределенными случайными величинами, ожидаемая разница между наибольшей и наименьшей суммой составляет . Θ ( 1 / н ) {\displaystyle \Тета (1/n)}

Метод RLDM (ограниченный метод наибольшей разности) работает следующим образом. [7]

  1. Расположите числа от большего к меньшему.
  2. Замените числа №1 и №2 на их разность; №3 и №4 на их разность и т. д.
  3. Отсортируйте список из n /2 отличий от большего к меньшему.
  4. Поочередно распределите каждую пару по разным наборам: наибольший элемент в паре — по набору с наименьшей суммой, а наименьший элемент в паре — по набору с наибольшей суммой.

Для двухстороннего разбиения, когда входные данные представляют собой равномерно распределенные случайные величины, ожидаемая разница между наибольшей и наименьшей суммой составляет . О ( бревно ⁡ н / н 2 ) {\displaystyle O(\log {n}/n^{2})}

BLDM (сбалансированный метод наибольшей разности) работает следующим образом. [3]

  1. Расположите числа от большего к меньшему.
  2. Замените числа №1 и №2 на их разность; №3 и №4 на их разность и т. д.
  3. Запустите LDM на наборе различий.

BLDM имеет средние свойства, похожие на LDM. Для двухстороннего разбиения, когда входные данные являются равномерно распределенными случайными величинами, ожидаемая разница между наибольшей и наименьшей суммой составляет . [3] н − Θ ( бревно ⁡ н ) {\displaystyle n^{-\Theta (\log n)}}

Для многостороннего разбиения, когда c =ceiling( n / k ) и каждое из k подмножеств должно содержать либо ceiling( n / k ), либо floor( n / k ) элементы, коэффициент аппроксимации BLDM для минимальной наибольшей суммы составляет ровно 4/3 для c =3, 19/12 для c =4, 103/60 для c =5, 643/360 для c =6 и 4603/2520 для c =7. Коэффициенты были найдены путем решения смешанной целочисленной линейной программы . В общем случае (для любого c ) коэффициент аппроксимации составляет не менее и не более . Результаты MILP для 3,4,5,6,7 соответствуют нижней границе. Когда параметром является количество подмножеств ( k ), коэффициент аппроксимации составляет ровно . [8] 2 − ∑ дж = 0 с − 1 дж ! с ! {\displaystyle 2-\sum _{j=0}^{c-1}{\frac {j!}{c!}}} 2 − 1 с − 1 {\displaystyle 2-{\frac {1}{c-1}}} 2 − 1 к {\displaystyle 2-{\frac {1}{k}}}

Проблема подпоследовательности минимума-максимума

В задаче min-max subsequence входными данными является мультимножество из n чисел и целочисленный параметр k , а цель состоит в том, чтобы упорядочить числа таким образом, чтобы наибольшая сумма каждого блока соседних k чисел была как можно меньше. Проблема возникает при проектировании видеосерверов. [9] Эту задачу можно решить за политайм для k = 2, но она сильно NP-трудна для k≥ 3. К этой задаче можно применить вариант метода разности. [10]

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

Полный алгоритм Кармаркара–Карпа (CKK) находит оптимальное решение путем построения дерева степени . к ! {\displaystyle к!}

  • В случае k = 2 каждый уровень соответствует паре чисел, а две ветви соответствуют взятию их разности (т.е. помещению их в разные наборы) или взятию их суммы (т.е. помещению их в один и тот же набор).
  • Для общего k каждый уровень соответствует паре k -кортежей, а каждая из ветвей соответствует разному способу объединения подмножеств в этих кортежах. к ! {\displaystyle к!}

При k = 2 CKK работает существенно быстрее, чем полный жадный алгоритм (CGA) на случайных экземплярах. Это связано с двумя причинами: когда равное разбиение не существует, CKK часто допускает больше обрезки, чем CGA; и когда равное разбиение существует, CKK часто находит его намного быстрее и, таким образом, допускает более раннее завершение. Корф сообщает, что CKK может оптимально разбить 40 15-значных чисел двойной точности примерно за 3 часа, в то время как CGA требует около 9 часов. На практике при k = 2 задачи произвольного размера могут быть решены CKK, если числа имеют не более 12 значащих цифр ; при k = 3 — не более 6 значащих цифр. [11]

CKK также может работать как алгоритм, действующий в любое время : он сначала находит решение KK, а затем находит все лучшие решения по мере того, как позволяет время (возможно, для достижения оптимальности потребуется экспоненциальное время в худших случаях). [12]

Объединение CKK с алгоритмом сбалансированного LDM (BLDM) дает полный алгоритм для решения проблемы сбалансированного разбиения в любое время . [13]

Предыдущие упоминания

Алгоритм, эквивалентный эвристике Кармаркара-Карпа, упоминается в древних еврейских юридических текстах Нахманида и Иосифа ибн Хабиба . Алгоритм используется для объединения различных показаний об одном и том же кредите. [14]

Реализации

  • Python : Библиотека prtpy содержит реализации алгоритма Кармаркара-Карпа и полного алгоритма Кармаркара-Карпа.

Ссылки

  1. ^ Нарендра Кармаркар и Ричард М. Карп , «Метод разностного разбиения множеств», Технический отчет UCB/CSD 82/113, Отделение компьютерных наук, Калифорнийский университет в Беркли , 1982 г.
  2. ^ abcde Михилс, Вил; Корст, Ян; Аартс, Эмиль (2003). «Коэффициенты производительности для метода разности Кармаркара–Карпа». Электронные заметки по дискретной математике . 13 : 71–75 . CiteSeerX  10.1.1.107.1332 . doi :10.1016/S1571-0653(04)00442-1.
  3. ^ abcde Якир, Бенджамин (1996-02-01). "Алгоритм разностной логики LDM для разбиения: доказательство гипотезы Кармаркара и Карпа". Математика исследования операций . 21 (1): 85–99 . doi :10.1287/moor.21.1.85. ISSN  0364-765X.
  4. ^ Фишетти, Маттео; Мартелло, Сильвано (1987-02-01). "Анализ наихудшего случая метода разности для задачи разбиения". Математическое программирование . 37 (1): 117– 120. doi :10.1007/BF02591687. ISSN  1436-4646. S2CID  30065792.
  5. ↑ Хейс, Брайан (март–апрель 2002 г.), «Самая простая трудная проблема», American Scientist , т. 90, № 2, Sigma Xi, Научно-исследовательское общество, стр.  113–117 , JSTOR  27857621
  6. ^ Люкер, Джордж С. (1987-12-01). «Заметка о поведении простого метода разности для разделения в среднем». Operations Research Letters . 6 (6): 285– 287. doi :10.1016/0167-6377(87)90044-7. ISSN  0167-6377.
  7. ^ Цай, Ли-Хуэй (1992-02-01). «Асимптотический анализ алгоритма сбалансированного параллельного планирования процессоров». Журнал SIAM по вычислениям . 21 (1): 59– 64. doi :10.1137/0221007. ISSN  0097-5397.
  8. ^ Михилс, Уил; Корст, Ян; Аартс, Эмиль; ван Леувен, Январь (2003 г.), Коэффициенты производительности для метода дифференцирования, применяемого к задаче разделения сбалансированных чисел, Конспекты лекций по информатике, том. 2607, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр.  583–595 , doi : 10.1007/3-540-36494-3_51, ISBN 978-3-540-00623-7, получено 2021-10-15
  9. ^ Уил Михилс (2004). «Коэффициенты производительности для различающихся методов». Технический университет Эйндховена, 2004. https://www.elibrary.ru/item.asp?id=8860464.
  10. ^ Михилс, Вил; Корст, Ян (2001). «Проблемы минимальной и максимальной подпоследовательности при многозонной записи на диск». Журнал планирования . 4 (5): 271– 283. doi :10.1002/jos.80. ISSN  1099-1425.
  11. ^ Корф, Ричард Э. (1995-08-20). "От приближенных к оптимальным решениям: исследование случая разбиения чисел". Труды 14-й Международной объединенной конференции по искусственному интеллекту - Том 1. IJCAI'95. Монреаль, Квебек, Канада: Morgan Kaufmann Publishers Inc.: 266– 272. ISBN 978-1-55860-363-9.
  12. ^ Корф, Ричард Э. (1998-12-01). «Полный алгоритм разбиения чисел на части в любое время». Искусственный интеллект . 106 (2): 181– 203. doi : 10.1016/S0004-3702(98)00086-1 . ISSN  0004-3702.
  13. ^ Мертенс, Стефан (11.03.1999). "Полный алгоритм для сбалансированного разбиения чисел на разделы в любое время". arXiv : cs/9903011 .
  14. ^ Рон Адин и Юваль Ройхман (2015). «Объединение свидетелей: математические аспекты» ( PDF) . BDD (на иврите). 30. Университет Бар-Илан : 7–20 .
Взято с "https://en.wikipedia.org/w/index.php?title=Самый_большой_метод_различия&oldid=1234745378"