Мой алгоритм суммы подмножества полиномиального времени?

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

Быстрые факты начинающего:

Проблемой суммы подмножества является полная NP проблема. Решение его в полиномиальное время означает это P = NP.
Количество подмножеств в ряде длины N, 2^N.

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

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

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

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

Вообразите массив индексированным суммой, которая имеет записи за все возможные суммы результата положительной стороны (который только линеен, помните). Когда мы добавляем запись, значение является записями в подмножестве. Таким образом как, выстройте [3] = {1, 2}.

В целом мы теперь перемещаемся для перечисления всех подмножеств в наборе. Мы делаем это путем запуска с подмножеств одной длины, затем добавления к ним. Когда у нас есть все уникальные подмножества, они формируют массив, и мы просто выполняем итерации их способом, используемым в Horowitz/Sahni.

Теперь мы запускаем со значений "первого поколения". Таким образом, если не было никаких дублирующихся чисел в исходном наборе данных, там, как гарантируют, не будут никакими дубликатами в этих значениях. Таким образом, все подмножества единственного значения и вся длина набора минус подмножества одной длины. Они могут легко быть сгенерированы путем подведения итогов набора и вычитания каждого элемента в свою очередь. Кроме того, сам набор является допустимой суммой первого поколения и подмножеством, а также каждым отдельным элементом подмножества.

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

Путем удаления дублирующихся подмножеств этим способом мы не должны продолжать комбинировать дубликаты с остальной частью набора, ни продолжать проверять их на коллизии, ни суммировать их. Самое главное, не создавая новые подмножества, которые являются групповыми, мы не генерируем новые подмножества от них, которые, я верю, могут повернуть алгоритм от NP до P, так как рост подмножеств больше не экспоненциален - мы отбрасываем подавляющее большинство их, прежде чем они смогут "воспроизвести" в следующем поколении и создать больше подмножеств, будучи объединенным с другими недублирующимися подмножествами.

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

Например, вообразите (потому что я делаю этот пример вручную), простой набор данных, который переходит-7 в 7 (не нуль), для которого мы стремимся к нулю. Вид и разделение, таким образом, нас оставляют с (1, 2, 3, 4, 5, 6, 7). Сумма равняется 28. Но 2^7 128. Таким образом, 128 подмножеств помещаются в диапазон 1.. 28, означая, что мы знаем заранее, что 100 наборов являются дубликатами. Если бы мы имели 8, то у нас только было бы 36 слотов, но теперь 256 подмножеств. Таким образом, можно легко видеть, что число простофиль теперь было бы 220, больше, чем двойной, чем это было прежде.

В этом случае значения первого поколения равняются 1, 2, 3, 4, 5, 6, 7, 28, 27, 26, 25, 24, 23, 22, 21, и мы отображаем их на их составляющие компоненты, таким образом,

1 = { 1 }
2 = { 2 }
...
28 = { 1, 2, 3, 4, 5, 6, 7 }
27 = { 2, 3, 4, 5, 6, 7 }
26 = { 1, 3, 4, 5, 6, 7 }
...
21 = { 1, 2, 3, 4, 5, 6 }

Теперь для генерации новых подмножеств мы берем каждое подмножество в свою очередь и добавляем его друг к другу подмножество, если у них нет взаимного подподмножества, например, 28, и 27 имеют hueg взаимное подподмножество. Таким образом, когда мы берем 1, и мы добавляем его к 2, мы добираемся 3 = {1, 2}, но owait! Это уже находится в массиве. То, что это означает, - то, что мы теперь не добавляем 1 ни к какому подмножеству, которое уже имеет 2 в нем, и наоборот, потому что это - дубликат на 3's подмножества.

Теперь мы имеем

1 = { 1 }
2 = { 2 }
// Didn't add 1 to 2 to get 3 because that's a dupe
3 = { 3 } // Add 1 to 3, amagad, get a duplicate. Repeat the process.
4 = { 4 } // And again.
...
8 = { 1, 7 }

21? Already has 1 in.
...
27? We already have 28

Теперь мы добавляем 2 ко всем.

1? Existing duplicate
3? Get a new duplicate
...
9 = { 2, 7 }
10 = { 1, 2, 7 }

21? Already has 2 in
...
26? Already have 28
27? Got 2 in already.

3?

1? Existing dupe
2? Existing dupe
4? New duplicate
5? New duplicate
6? New duplicate
7? New duplicate
11 = { 1, 3, 7 }
12 = { 2, 3, 7 }
13 = { 1, 2, 3, 7 }

Как Вы видите, даже при том, что я все еще добавляю новые подмножества каждый раз, количество только повышается линейно.

4?

1? Existing dupe
2? Existing dupe
3? Existing dupe
5? New duplicate
6? New duplicate
7? New duplicate
8? New duplicate
9? New duplicate
14 = {1, 2, 4, 7}
15 = {1, 3, 4, 7}
16 = {2, 3, 4, 7}
17 = {1, 2, 3, 4, 7}

5?

1,2,3,4 existing duplicate
6,7,8,9,10,11,12 new duplicate
18 = {1, 2, 3, 5, 7}
19 = {1, 2, 4, 5, 7}
20 = {1, 3, 4, 5, 7}
21 = new duplicate

Теперь у нас есть каждое значение в диапазоне, таким образом, мы останавливаемся и добавляем к нашему списку 1-28. Повторитесь для отрицательных чисел, выполните итерации через списки.

Править:

Этот алгоритм является полностью неправильным в любом случае. Подмножества, которые имеют дублирующиеся суммы, не являются дубликатами в целях, из которых подмножества могут быть порождены от них, потому что они прибываются по-другому - т.е. они не могут быть свернуты.