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

У теорії чисел та інформатиці, задачею про розбиття (або розбиття числа) є визначення того, чи можна дану множину 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, яка додається до $\lfloor K/2\rfloor$. Якщо є підмножина, то:

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

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

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

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

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

Тоді p($\lfloor K/2\rfloor$, n) - це Істина тоді та тільки тоді, коли існує мультимножина S, котра дорівнює $\lfloor K/2\rfloor$. Метою нашого алгоритму буде обчислення p($\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.

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

Алгоритм полягає в тому, щоб створити таблицю розміру $\lfloor K/2\rfloor$ по n , що містить значення повторення. Пам'ятайте, що K - це розмір суми, а N - це . кількість елементів. Коли вся таблиця заповнена, поверніть P($\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 ($\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 $\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($\lfloor K/2\rfloor$, n)

Приклад

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

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

Аналіз

Цей алгоритм працює з часом Шаблон:Math, де Шаблон:Mvar - кількість елементів у наборі вхідних даних та Шаблон:Mvar - сума елементів у вхідній множині.

Алгоритм може бути розширений до Шаблон:Mvar-задачі багаторозбиття, але потім приймає Шаблон:Math пам'ять, де Шаблон:Mvar - найбільше число на вході, що робить його непрактичним навіть для Шаблон:Math , якщо входи не є дуже маленькими числами. Шаблон:R

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

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

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

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

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

Відомо, що цей жадібний підхід дає Шаблон:Frac-наближення до оптимального рішення версії оптимізації; Тобто, якщо жадібний алгоритм виводить два набори Шаблон:Mvar та Шаблон:Mvar, то Шаблон:Math, де Шаблон:Math це розмір більшого набору в найкращому можливому розділі.Нижче наведено приклад (написаний на мові 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)

Цей алгоритм може бути поширений на випадок Шаблон:Math множин: для того, щоб узяти Шаблон:Mvar найбільших елементів і для кожного розбиття їх розширює розділ, послідовно додаючи інші елементи в залежності від того, який набір менше. (Проста версія вище відповідає Шаблон:Math.) Ця версія працює в часі Шаблон:Math і, як відомо, дає Шаблон:Math наближення. Таким чином, ми маємо схему наближення поліноміального часу (PTAS) для завдання про розбиття чисел, хоча це не повністю поліноміальна схема наближення часу (час роботи є експоненціальним у гарантованій задачі наближення). Однак існують варіанти цієї ідеї, які є повністю поліноміальними схемами апроксимації для завдання підмножини, а отже, і для завдання розбиття.

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

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

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

Наступна програма на 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();
}

Інші підходи

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

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

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

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

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

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

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

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

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

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

Нотатки

• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation

• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation