Задача про розбиття

У теорії чисел та інформатиці, задачею про розбиття (або розбиття числа) є визначення того, чи можна дану множину S натуральних чисел розбити на дві підмножини S₁ і S₂ так, щоб сума чисел у S₁ дорівнювала сумі чисел в S₂. Хоча задача про розбиття NP-повна, існує псевдо-поліноміальне рішення динамічного програмування часу, і є евристики, які вирішують цю задачу оптимально або приблизно. З цієї причини її назвали «найлегшою NP-важкою задачею» .

Існує версія оптимізації задачі про розбиття, яка полягає в розбитті мультимножини S на дві підмножини S₁, S₂, так що різниця між сумою елементів в S₁ і сумою елементів в S₂ мінімізована. Оптимізаційна версія NP-важка, але на практиці її можна ефективно вирішити.

Задача про розбиття є окремим випадком задачі про суми підмножин, тому її можна точно розв'язати за час O(2^S/2).

Приклади

Якщо S = {3,1,1,2,2,1}, дійсним рішенням задачі розподілу є дві множини S₁ = {1,1,1,2} and S₂ = {2,3}. Обидва набори мають суму 5, та утворюють розбиття множини S. Зверніть увагу, що це рішення не є унікальним. S₁ = {3,1,1} and S₂ = {2,2,1} - інше рішення. Не кожну множину позитивних цілих чисел можна розбити на дві частини з однаковою сумою. Прикладом такого набору є S = {2,5}.

Алгоритм псевдо-поліноміального часу

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

Припустимо, що вхідним значенням для алгоритму є список форми: S = x₁, ..., x_n

Нехай N - кількість елементів в S. Нехай K - сума всіх елементів в S. Тобто: K = x₁ + ... + x_n. Ми побудуємо алгоритм, який визначає, чи існує підмножина S, яка додається до ${\displaystyle \lfloor K/2\rfloor }$. Якщо є підмножина, то:

Якщо сума K парна, залишок S також підсумовується до ${\displaystyle \lfloor K/2\rfloor }$

Якщо сума K непарна, то залишок S підсумовується з ${\displaystyle \lceil K/2\rceil }$. Це найкраще рішення.

Рекурентне відношення

Ми хочемо визначити, чи існує підмножина S, котра дорівнює ${\displaystyle \lfloor K/2\rfloor }$. Нехай:

p(i, j) буде Істина (True), якщо мультимножина { x₁, ..., x_j } дорівнює i , та Хибно (False), якщо навпаки.

Тоді p(${\displaystyle \lfloor K/2\rfloor }$, n) - це Істина тоді та тільки тоді, коли існує мультимножина S, котра дорівнює ${\displaystyle \lfloor K/2\rfloor }$. Метою нашого алгоритму буде обчислення p(${\displaystyle \lfloor K/2\rfloor }$, n). Для цього ми маємо наступне рекурентне співвідношення:

p(i, j) істинно, якщо p(i, j − 1) істинно або p(i − x_j, j − 1) істинно,

p(i, j) хибне, навпаки.

Це пояснюється наступним чином: є деяка підмножина S, яке підсумовує з i, використовуючи числа

x₁, ..., x_j

Тоді та тільки тоді, коли виконано одну з наступних умов:

Існує підмножина { x₁, ..., x_j-1 } , котра дорівнює i;

Існує підмножина { x₁, ..., x_j-1 } котра дорівнює i − x_j, коли x_j + сума підмножини = i.

Псевдо-поліноміальний алгоритм

Алгоритм полягає в тому, щоб створити таблицю розміру ${\displaystyle \lfloor K/2\rfloor }$ по n , що містить значення повторення. Пам'ятайте, що K - це розмір суми, а N - це . кількість елементів. Коли вся таблиця заповнена, поверніть P(${\displaystyle \lfloor K/2\rfloor }$, n). Нижче наведено зображення таблиці P. Існує синя стрілка від одного блоку до іншого, якщо значення цільового блоку може залежати від значення вихідного блоку. Ця залежність є властивістю рекурентного співвідношення.

Залежність записів у таблиці (i, j)

INPUT: A list of integers S OUTPUT: True if S can be partitioned into two subsets that have equal sum 1 function find_partition(S): 2 n ← |S| 3 K ← sum(S) 4 P ← empty boolean table of size (${\displaystyle \lfloor K/2\rfloor }$ + 1) by (n + 1) 5 initialize top row (P(0,x)) of P to True 6 initialize leftmost column (P(x, 0)) of P, except for P(0, 0) to False 7 for i from 1 to ${\displaystyle \lfloor K/2\rfloor }$ 8 for j from 1 to n 9 if (i-S[j-1]) >= 0 10 P(i, j) ← P(i, j-1) or P(i-S[j-1], j-1) 11 else 12 P(i, j) ← P(i, j-1) 13 return P(${\displaystyle \lfloor K/2\rfloor }$, n) 

Приклад

Нижче наведена таблиця P для прикладу, що використовується вище S = {3, 1, 1, 2, 2, 1}:

Результат виконання прикладу алгоритму на таблиці P

Аналіз

Цей алгоритм працює з часом O(K N), де N - кількість елементів у наборі вхідних даних та K - сума елементів у вхідній множині.

Алгоритм може бути розширений до k-задачі багаторозбиття, але потім приймає O(n(k − 1)m^{k − 1}) пам'ять, де m - найбільше число на вході, що робить його непрактичним навіть для k = 3 , якщо входи не є дуже маленькими числами.

Цей алгоритм можна узагальнити для вирішення задачі про суми підмножин.

Апроксимаційні алгоритми

Докладніше: Апроксимаційний алгоритм

Існує кілька евристичних алгоритмів для отримання наближень до задачі оптимізації розбиття. Вони можуть бути розширені до точних алгоритмів лінійного простору.

Жадібний алгоритм

Один з підходів до задачі, що імітує те, як діти вибирають команди для гри, — це жадібний алгоритм, який виконує ітерацію за номерами в порядку убування, привласнюючи кожному з них те, що підмножина має меншу суму. Цей підхід має час роботи  O(n log n). Ця евристика добре працює на практиці, коли цифри в наборі приблизно того ж розміру, що і потужність, або менше, але не гарантується, що буде створений найкращий розділ. Наприклад, якщо ввести S = {4, 5, 6, 7, 8} як вхідні дані, цей жадібний алгоритм розбив би S на підмножини {4, 5, 8} та {6, 7}; однак, S має точно збалансоване розбиття на підмножини {7, 8} та {4, 5, 6}.

Відомо, що цей жадібний підхід дає 7⁄6-наближення до оптимального рішення версії оптимізації; Тобто, якщо жадібний алгоритм виводить два набори A та B, то max(∑A, ∑B) ≤ 7/6 OPT, де OPT це розмір більшого набору в найкращому можливому розділі.Нижче наведено приклад (написаний на мові Python) для жадібного алгоритму..

def find_partition(int_list): "returns: An attempt at a partition of `int_list` into two sets of equal sum" A = set() B = set() for n in sorted(int_list, reverse=True): if sum(A) < sum(B): A.add(n) else: B.add(n) return (A, B) 

Цей алгоритм може бути поширений на випадок k > 2 множин: для того, щоб узяти k найбільших елементів і для кожного розбиття їх розширює розділ, послідовно додаючи інші елементи в залежності від того, який набір менше. (Проста версія вище відповідає k = 2.) Ця версія працює в часі O(2^k n²) і, як відомо, дає (k + 2)/(k + 1) наближення. Таким чином, ми маємо схему наближення поліноміального часу (PTAS) для завдання про розбиття чисел, хоча це не повністю поліноміальна схема наближення часу (час роботи є експоненціальним у гарантованій задачі наближення). Однак існують варіанти цієї ідеї, які є повністю поліноміальними схемами апроксимації для завдання підмножини, а отже, і для завдання розбиття.

Метод найбільшої різниці

Іншою евристикою є метод найбільшої різниці (largest differencing method, LDM), що також має назву евристика Кармаркара — Карпа, за прізвищами пари вчених, що опублікували роботу по цій темі в 1982 році. LDM працює в два етапи. Перша фаза алгоритму приймає два найбільших числа від входу і замінює їх їхньою різницею. Це повторюється до тих пір, поки не залишиться тільки одне число. Заміна є рішення розмістити два числа в різних наборах, не вдаючись до негайного визначення того, в якому з них встановлено. В кінці першого етапу єдиним числом, що залишилося, буде різниця двох сум підмножини. Друга фаза реконструює фактичне рішення.

Евристика різниць працює краще, ніж жадібна, але все ще погано для випадків, коли числа є експонентними за розміром набору.

Наступна програма на Java реалізує перший етап Кармаркара — Карпа. Він використовує купу, щоб знайти пару найбільших чисел, які залишилися.

int karmarkarKarpPartition(int[] baseArr) {  // create max heap  PriorityQueue<Integer> heap = new PriorityQueue<Integer>(baseArr.length, REVERSE_INT_CMP);  for (int value : baseArr) {  heap.add(value);  }  while(heap.size() > 1) {  int val1 = heap.poll();  int val2 = heap.poll();  heap.add(val1 - val2);  }  return heap.poll(); } 

Інші підходи

Існують також ^[en], засновані на евристичному різницевої аналізі, які спочатку знаходять рішення, повернене евристикою разностного аналізу, потім знаходять прогресивно кращі рішення в міру того, як дозволяє час (можливо, вимагаючи експоненціального часу для досягнення оптимальності для найгірших випадків).

Жорсткі інстанції

Набори з одним або без поділу, як правило, складніше (або найбільш дорогі) вирішувати в порівнянні з їх розмірами введення. Коли значення малі в порівнянні з розміром набору, більш досконалі розділи більш вірогідні. Відомо, що задача зазнає «фазовий перехід»; Ймовірно, для деяких наборів і малоймовірно для інших. Якщо m — число біт, необхідне для вираження будь-якого числа в наборі, а n — розмір набору, то ${\displaystyle m/n<1}$ має багато рішень і ${\displaystyle m/n>1}$, як правило, мало або взагалі не має рішень. У міру того як n і m стають більше, ймовірність вчиненого розбиття дорівнює 1 або 0 відповідно. Це спочатку стверджувалося на основі емпіричних даних Гента і Уолша, потім використовуючи методи статистичної фізики Мертенса, а потім довів Боргс, Чайс і Піттель.

Варіанти та узагальнення

Існує задача, звана ^[en], яка полягає в розбитті множини S до |S|/3 трійок з однаковою сумою. Ця задача суттєво відрізняється від задачі розділу і не має псевдо-поліноміального алгоритму часу, якщо P = NP.

Задача багатосторінкового розділу узагальнює оптимізаційну версію задачі про розбиття. Тут мета полягає в тому, щоб розбити безліч або мультимножину з n цілих чисел на задане число k підмножин, мінімізуючи різницю між найменшою і найбільшою сумою підмножини.

Для подальших узагальнень задачі про розбиття див. задачі про пакування в ємності.

Імовірнісна версія

Пов'язана з цим задача, в чомусь схожа на парадокс днів народження, полягає у визначенні розміру вхідної множини так, щоб ймовірність існування розв'язку була 50%, за припущення, що кожен елемент в наборі вибирається випадково за рівномірним розподілом між 1 і деяким заданим значенням.

Вирішення цієї задачі може бути нелогічним, як парадокс дня народження. Наприклад, якщо елементи вибираються випадковим чином в межах від 1 до 1 мільйона, інтуїція багатьох людей полягає в тому, що відповідь знаходиться в тисячах, десятках або навіть в сотнях тисяч, тоді як правильна відповідь становить приблизно 23 (див. Парадокс днів народження § апроксимація).^[]

Нотатки

• (May–June 2002), , American Scientist, архів оригіналу за 21 травня 2017, процитовано 23 травня 2017
• Karmarkar, Narenda; Karp, Richard M (1982), The Differencing Method of Set Partitioning, Technical Report UCB/CSD 82/113, University of California at Berkeley: Computer Science Division (EECS)
• Gent, Ian; Walsh, Toby (August 1996), Wolfgang Wahlster (ред.), , John Wiley and Sons, с. 170—174, архів оригіналу за 4 березня 2016, процитовано 23 травня 2017
• Gent, Ian; Walsh, Toby (1998), Analysis of Heuristics for Number Partitioning, Computational Intelligence, 14 (3): 430—451, doi:10.1111/0824-7935.00069
• Mertens, Stephan (November 1998), Phase Transition in the Number Partitioning Problem, Physical Review Letters, 81 (20): 4281, arXiv:cond-mat/9807077, Bibcode:1998PhRvL..81.4281M, doi:10.1103/PhysRevLett.81.4281, процитовано 3 жовтня 2009

• Mertens, Stephan (2001), A physicist's approach to number partitioning, Theoretical Computer Science, 265 (1-2): 79—108, doi:10.1016/S0304-3975(01)00153-0
• Mertens, Stephan (2006), The Easiest Hard Problem: Number Partitioning, у Allon Percus; Gabriel Istrate; (ред.), , Oxford University Press US, с. 125, arXiv:cond-mat/0310317, Bibcode:2003cond.mat.10317M, ISBN , архів оригіналу за 5 квітня 2017, процитовано 23 травня 2017
• Borgs, Christian; Chayes, Jennifer; Pittel, Boris (2001), , Random Structures and Algorithms, 19 (3-4): 247—288, doi:10.1002/rsa.10004, архів оригіналу за 29 вересня 2012, процитовано 4 жовтня 2009
• Korf, Richard E. (1998), , Artificial Intelligence, 106 (2): 181—203, doi:10.1016/S0004-3702(98)00086-1, ISSN 0004-3702, архів оригіналу за 29 вересня 2012, процитовано 4 жовтня 2009
• Mertens, Stephan (1999), A complete anytime algorithm for balanced number partitioning, arXiv:cs/9903011, Bibcode:1999cs........3011M

Примітки

1. Korf, 1998
2. Hayes, 2002
3. Korf, Richard E. (2009). (PDF). IJCAI. Архів оригіналу (PDF) за 27 листопада 2014. Процитовано 18 травня 2017.
4. Ron L. Graham (1969). Bounds on multiprocessor timing anomalies. SIAM J. Appl. Math. Т. 17, № 2. с. 416—429.
5. Martello, Silvano; Toth, Paolo (1990). 4 Subset-sum problem. Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience. с. 105–136. ISBN . MR 1086874.
6. Michiels, Wil; Korst, Jan; Aarts, Emile (2003). Performance ratios for the Karmarkar–Karp differencing method. Electronic Notes in Discrete Mathematics. 13: 71—75.
7. Karmarkar та Karp, 1982
8. Korf, 1998, Mertens, 1999
9. Gent та Walsh, 1996
10. Mertens, 1998
11. Borgs, Chayes та Pittel, 2001
12. Garey, Michael; Johnson, David (1979). Computers and Intractability; A Guide to the Theory of NP-Completeness. с. 96–105. ISBN .