WikiSort.ru - Не сортированное

Рекуррентные соотношения

Мы хотим определить, если существует подмножество S, сумма элементов которого равна ${\displaystyle \lfloor K/2\rfloor }$ . Пусть:

p(i, j) принимает значение True, если среди { x₁, ..., x_j } существует такое подмножество, элементы которого в сумме дают i и False в противном случае.

Тогда p(${\displaystyle \lfloor K/2\rfloor }$ , n) принимает значение True тогда и только тогда, когда существует подмножество S, сумма которого равна ${\displaystyle \lfloor K/2\rfloor }$ . Цель нашего алгоритма — вычислить p(${\displaystyle \lfloor K/2\rfloor }$ , n). Для достижения этого мы имеем следующие рекуррентные формулы:

p(i, j) принимает значение True, если либо p(i, j − 1) принимает значение True, либо p(i − x_j, j − 1) принимает значение True

p(i, j) принимает значение False в противном случае

Причина этому следующая: существует некоторое подмножество 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, содержащую значения рекурсии, где ${\displaystyle K}$ — сумма значений, а ${\displaystyle n}$ — число элементов. Когда вся таблица заполнена, возвращаем ${\displaystyle P(\lfloor K/2\rfloor ),n)}$ . Ниже приведена таблица P. На рисунке синяя стрелка из одного блока в другой, если значение конечного блока может зависеть от значения исходного блока. Эта зависимость является свойством рекуррентного отношения.

INPUT:  Список целых чисел S
OUTPUT: True, если S может быть разбито на два подмножества, имеющих одинаковые суммы
1 функция найти_разбиение(S):
2     n ← |S|
3     K ← sum(S)
4     P ← пустая булева таблица размера (${\displaystyle \lfloor K/2\rfloor }$
 + 1) by (n + 1)
5     инициализируем верхнюю строку (P(0,x)) таблицы P значениями True
6     инициализируем крайний левый столбец (P(x, 0)) таблицы P, за исключением ячейки P(0, 0) значениями False
7     для i от 1 до ${\displaystyle \lfloor K/2\rfloor }$

8         для j от 1 до n
9             если (i-S[j-1]) >= 0
10               P(i, j) ← P(i, j-1) или P(i-S[j-1], j-1)
11            иначе
12               P(i, j) ← P(i, j-1)
13    вернуть значение P(${\displaystyle \lfloor K/2\rfloor }$
, n)

Пример

Ниже приведена таблица P для использованного выше множества S={3, 1, 1, 2, 2, 1}:

Анализ

Этот алгоритм работает за время O(K N), где N — число элементов во входном множестве, а K — сумма элементов во входном множестве.

Алгоритм может быть распространён на задачу мультиразбиения на k частей, но требует памяти O(n(k − 1)m^{k − 1}), где m является наибольшим числом во входном множестве, что делает алгоритм практически бессмысленным даже для k = 3, если только на вход не подаются очень маленькие числа^[2].

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

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

Известно, что этот жадный подход даёт ⁷⁄₆-аппроксимацию относительно оптимального решения оптимизационной версии. То есть, если вывод жадного алгоритма даёт два множестваs A и B, тогда ${\displaystyle \max(\sum {A},\sum {B})\leq {\tfrac {7}{6}}OPT}$ , где OPT — размер наибольшего множества в лучшем разбиении^[3]. Ниже приведён пример (на языке Python) жадного алгоритма.

def find_partition(int_list):
    "Разбиваем `int_list` на два множества с одинаковыми суммами "
    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 множествам, затем перебираем оставшиеся числа в порядке убывания и добавляем их к множеству с меньшей суммой (простая версия выше соответствует k = 2). Эта версия работает за время O(2^k n²) и известно, что она даёт аппроксимацию ${\displaystyle {\tfrac {(k+2)}{(k+1)}}}$ ^[3]. Таким образом, мы имеем приближенную схему полиномиального времени (PTAS) для задачи разбиения на несколько частей, хотя это не полностью приближенная схема полиномиального времени (время работы экспоненциально для желаемого уровня гарантированной аппроксимации). Однако существуют варианты этой идеи, которые являются полностью приближенными схемами полиномиального времени для задачи о сумме подмножеств, а следовательно, и для задачи разбиения^[4][5].

Разностный алгоритм

Другой эвристический алгоритм — метод наибольшей разности (МНР, en:Largest Differencing Method, LDM)^[6], который называется эвристическим методом Кармаркара–Карпа^[2], по имени учёных, опубликовавших метод в 1982^[7]. МНР имеет две фазы. Первая фаза алгоритма берёт два наибольших числа из входа и заменяем их разностью. Повторяем операцию, пока не останется одно число. Замена представляет решение разместить два числа в разные подмножества, но в какие множества эти числа размещаются, решение не принимается. В конце первой фазы оставшееся единственное число является разностью двух сумм подмножеств. На втором этапе строится актуальное решение^[1].

Разностный эвристический алгоритм работает лучше, чем жадный алгоритм, но остаётся плохим для задач, в которых числа экспоненционально зависят от размера множества^[1].

Следующий код на 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], основанные на разностной эвристической схеме, которые сначала находят решение, полученное разностной эвристической схемой, затем находится поступательно лучшие решения, если время позволяет (возможен экспоненциальный рост времени работы для получения оптимального решения в худшем случае)^[8][9].

Вероятностная версия

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

Решение этой задачи может быть парадоксальным. Например, при выборе случайно целых чисел между 1 и одним миллионом, многие люди считают, что ответом будет тысячи, десятки тысяч, или даже сотни тысяч, хотя, на самом деле, правильным ответом будет примерно 23 (подробности — в статье Задача разбиения).