Особый алгоритм перебора всех подмножеств мультимножества

[B@R5uk]

Я тут вспомнил, что у меня осталась ещё одна не реализованная идея. Я как-то размышлял над тем, нельзя ли применить в этой задаче парадигму "разделяй и властвуй". Этот подход позволяет заменить линейный множитель в сложности алгоритма на логарифмический. Конкретно в этой задаче, если от экспоненциальной сложности удастся отщепить экспоненциальный множитель и заменить его на линейный, то, не смотря на то, что алгоритм всё равно останется экспоненциально сложным, его сложность упадёт неимоверно (хочется на это надеяться во всяком случае).

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

Рассмотрим конкретный пример:
[9, 14, 34, 42, 47, 49, 57, 66, 68, 71, 74, 97, 100]
[5, 2, 5, 5, 1, 1, 1, 1, 4, 5, 2, 7, 10]
[227, 235, 264, 292, 298, 322, 327, 341, 820]

0: 227 -> 96
1: 235 -> 107
2: 264 -> 179
3: 292 -> 279
4: 298 -> 305
5: 322 -> 431
6: 327 -> 459
7: 341 -> 555
8: 820 -> 20314
9: 462 -> 2129
10: 726 -> 13379
11: 1018 -> 37779
12: 1316 -> 62229
13: 1638 -> 69566
14: 1965 -> 50622
15: 2306 -> 20314
16: 3126 -> 1
Здесь в первой строчке уникальные значения элементов, во второй — количество повторов каждого элемента, в третьей — целевые суммы. Затем для некоторых чисел (которые являются целевыми суммами и суммами целевых сумм) посчитано число решений, которыми каждое это число можно представить через исходное множество элементов. Видно, что для числа 1018, являющимся суммой наименьших четырёх сумм число решений чуть меньше 38 тысяч. Это не большое число само по себе, но не надо забывать, что это только первый уровень алгоритма!

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

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

Сложность алгоритма всё равно останется довольно таки заметной. Конкретно для этого теста на первом этапе получается 37779 комбинаций. На втором для каждой из половинок получится меньше, но тоже заметное число. Пусть где-то 2129 (вариант с числом решений для двух сумм, но с полным числом элементов — оценка сверху с запасом). На третьем уровне будет где-нибудь по 100-200 комбинаций. В итоге получается произведение порядка $1,6\cdot10^{10}$. Остаётся надеяться, что решение найдётся значительно раньше, чем перебор хотя бы 1% этих вариантов. Плюс отсечения сделают своё благое дело.

[B@R5uk]

А существует ли такой двоичный экспоненциальный перебор всех возможных подмножеств, чтобы при переходе от одного подмножества к другому удалялся/прибавлялся только один элемент? Вроде где-то попадалось это...

[arseniiv]

Код Грэя? Но как вы там будете делать пропуски…

-- Пт фев 09, 2018 23:12:04 --

Мой знакомый, контактирующий с олимпиадным программированием часто, предлагал пару дней назад применить имитацию отжига (и когда время истекает, выдавать самый лучший полученный кандидат в надежде, что подойдёт). Я в этом не разбираюсь, но могу совсем немножко побыть медиатором.

[B@R5uk]

arseniiv в сообщении #1291487 писал(а):

Код Грэя

Что-то я не нашёл простого варианта в виде цикла. Всё в виде рекурсии.

arseniiv в сообщении #1291487 писал(а):

Но как вы там будете делать пропуски

Это для другого нужно. Вернее, для той же задачи но в другом месте. Я, пока размышлял как же реализовать последнюю идею, придумал как улучшить отсечения в предыдущем алгоритме. Там проверяется наличие решения для каждой из $N$ целевых сумм (которые с погружением алгоритма уменьшались), а по хорошему надо бы проверять все $2^N$ комбинаций этих сумм. Я надеюсь, это позволит отсечь неудачные направления основного перебора значительно раньше.

-- 09.02.2018, 21:54 --

arseniiv в сообщении #1291487 писал(а):

...предлагал пару дней назад применить имитацию отжига...

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

[arseniiv]

B@R5uk в сообщении #1291496 писал(а):

Что-то я не нашёл простого варианта в виде цикла. Всё в виде рекурсии.

Странно. Есть простое преобразование двоичного числа в его код Грэя: https://en.wikipedia.org/wiki/Gray_code#Converting_to_and_from_Gray_code (в русской статье притом всё то же имеется). Конечно, вы храните по разряду в элементе массива, но как будто так трудно сделать то же с массивом — тот же xor, сдвиг элементарен.

Впрочем, можно опять выписать коды и посмотреть на них пристально:

Используется синтаксис Text

cur   flip→
0000  1
0001  2
0011  1
0010  3
0110  1
0111  2
0101  1
0100  4
1100  1
1101  2
1111  1
1110  3
1010  1
1011  2
1001  1
1000  4

Последовательность $C_n$ сменяемых разрядов для $n$-битного числа, если не делать последнего шага и возвращения к началу, описывается просто: $C_0 = \varepsilon$ (пустая), $C_{n} = C_{n-1} + \langle\text{flip } n\rangle + C_{n-1}$. Сможете сгенерировать её нерекурсивно?

[B@R5uk]

arseniiv в сообщении #1291506 писал(а):

Впрочем, можно опять выписать коды и посмотреть на них пристально:

Да, спасибо. Видно, что индекс изменяемого бита для новой комбинации является индексом самого младшего единичного бита номера этой комбинации. Сделав вложенный цикл можно вычислять индекс этого бита по порядковому номеру комбинации. Но я вот думаю: а нельзя ли это как-то сделать без вложенного цикла?

[realeugene]

В коде Грэя при прибавлении единицы изменяется всегда самый старший бит, который изменяется при прибавлении единицы к двоичному представлению числа. Если прибавлять единицу к двоичному представлению и вручную переносить биты переноса, то нужно будет изменять в коде Грэя тот бит, на котором останавливается перенос (или же самый старший бит), и эта операция будет занимать амортизированное константное время. Но можно поиграться и с встроенными целочисленными операциями (особенно, на современных 64-битных процессорах: подозреваю, что 64 бит более чем достаточно для любого желаемого вами в настоящее время множества). Прибавить к числу единицу, вычислить XOR с предыдущим значением, найти позицию самого старшего бита - всё по одной команде.