Задача о сумме подмножеств

Цель курсового проекта – изучить особенности задачи о сумме подмножеств, различные алгоритмы её решения. Объем – 27 с., 4 ил. 5 таблиц, 3 источника.


Ключевые слова
Сумма, множество, подмножество, алгоритм, Горовиц и Сани, динамическое программирование.
...

Оглавление
Введение 5
1. Теоретическая часть 6
1.1 Постановка задачи 6
1.2 Алгоритмы решения 7
2. Практическая часть 9
2.1 Алгоритм перебора 9
2.2 Алгоритм динамического программирования 14
2.3 Приближенный алгоритм 18
2.4 Сравнение алгоритмов 25
Заключение 26
Список использованной литературы 27

В теории сложности алгоритмов и криптографии выделяют несколько важнейших задач. Каждая из этих задач имеет свои особенности, совокупность всех таких задач называют задачами NP-класса. К данному классу задач также относится задача о сумме подмножеств.
Смысл данной задачи заключается в нахождении (хотя бы одного) непустого подмножества некоторого набора чисел, чтобы сумма чисел, входящих в это подмножество, равнялась заданному числу.
Классическим примером данной задачи является задача о наборе необходимой суммы монетами (или купюрами) заданного номинала.
Также разновидностью данной задачи является задача о сумма подмножеств с повторяющимися элементами: Каждое a[i] может использоваться в сумме несколько раз, можно ли составить сумму K?
В информационных технологиях данная задача имеет немало важное значение при обработках больших массивов данных (базы данных и банки данных).
В данном курсовом проекте будут рассмотрены основные алгоритмы нахождения решения задачи: простой алгоритм перебора, алгоритм Горовица-Сани, алгоритм с использованием динамического программирования, приближенный алгоритм. Будет проверена работоспособность алгоритмов с помощью примеров, а также проведен их сравнительный анализ.

Сложность данного алгоритма экспотенциально зависит от N.Имеется несколько путей решения задачи за время, экспоненциально зависящее от N. Наиболее простой алгоритм просматривает все подмножества и, для каждого из них, проверяет, является ли сумма чисел подмножества приемлемой. Время работы алгоритма оценивается как O(2NN), поскольку имеется 2N подмножеств, а для проверки каждого подмножества нам нужно сложить не более N элементов. Блок-схема алгоритма представлена на рисунке 2.1.Рис.2.1 Блок-схема алгоритма простого перебораРешим задачу о сумме подмножеств с помощью данного алгоритма.Пусть имеется подмножество из шести элементов {3 4 5 -9 2 6}, необходимо выделить подмножества (по крайней мере одно), сумма которых равна 0.Выделим все подмножества исходного множества, всего их будет 64, поэтому мы выпишем только часть из них, достаточную для понятия принципа перебора:{3 4}{3 5}{3 -9}{3 2}{3 6}{4 5}{4 -9}…{3 4 5}{3 4 -9}{3 4 2}{3 4 6}{3 5 -9}{3 5 2}{3 5 6}{3 -9 2}{3 -9 6}{4 5 -9}{4 5 2}{4 5 6}…..{4 5 -9 2 6}Следующим шагом будет подсчет суммы элементов каждого подмножества:78-6 и т.д.Подмножества, сумма элементов которых будет равна нулю: {4 5 -9}, {3 6 -9}, {3 4 -9 2}.Существует и улучшенная версия данного алгоритма. Суть работы улучшенного варианта заключается в разбитии всего множества N на 2 подмножества по N/2 элементов в каждом. Затем для каждого из этих подмножеств стоится набор сумм всех 2N/2 возможных подмножеств. Оба списка сортируются. Если использовать простое сравнение для сортировки, получим время работы алгоритма, такое же как и при простом переборе – O(2N/2N). Однако, можно применить технику слияния. Сортировка слиянием совершается в три этапа:Сортируемый массив разбивается на две части примерно одинакового размера;Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом слияния;Два упорядоченных массива половинного размера соединяются в один.Когда один из подмассивов закончился, мы добавляем все оставшиеся элементы второго подмассива в результирующий массив.Имея сумму для k элементов, добавим k + 1-ый элемент и получим два сортированных списка, затем совершим слияние списков (без добавленного элемента и с добавленным элементом). В итоге у нас получается список сумм для (k + 1) элементов, и для его создания потребовалось O(2k) времени. Т.к. k в данном случае – половина от количества элементов в исходном множестве, выходит что список может быть создан за время O(2N/2). Имея два сортированных списка, алгоритм может проверить, могут ли дать суммы элементов из первого и второго списка значение s за время O(2N/2). Для этого алгоритм просматривает первый список в порядке убывания (начиная с самого большого элемента), а второй список в порядке возрастания (начиная с наименьшего элемента). Если сумма текущих элементов больше s, алгоритм передвигается к следующему элементу в первом списке, а если меньше s, к следующему элементу во втором списке. Если же сумма равна s, решение найдено и алгоритм останавливается. Горовиц (Horowitz) и Сани (Sartaj Sahni) впервые опубликовали этот алгоритм в отчете в 1972 году. Поэтому этот алгоритм часто называют алгоритм Горовица-Сани.Блок схема алгоритма представлена на рисунке 2.2.Рис. 2.2 Блок-схема алгоритма Горовица-СаниПроверим работу данного алгоритма на примере тех же исходных данных массив {3 4 5 -9 2 6} и s=0:Разобьем исходное множество на два подмножества:{3 4 5} {-9 2 6}Для каждого из них составим набор сумм для каждого из составляющих их подмножеств (кроме пустого и эквивалентного подмножества):Для первого: 3,4,5,7,8,9Для второго: -9,2,6,-7,-3,8Отсортируем их с помощью слияния:3,4,5,7,8,9-9,-7,-3,2,6,8Теперь производим сложение элементов и сравнение их суммы с s=0:3+8=11>03+6=10>03+2=5>03-3=0=04-7=-3<05-7=-2<07-7=0=08-9=-1<09-9=0;Получилось также 3 подмножества исходного множества, сумма элементов которых равна 0. 2.2 Алгоритм динамического программированияПусть задана последовательность чиселx1, ..., xNи нам нужно найти, существует ли непустое подмножество этой последовательности с заданной суммой элементов. Пусть A – сумма отрицательных элементов и B – сумма положительных. Определим булевскую функцию Q(i,s), принимающее значение ИСТИНА (True), если существует непустое подмножество элементов x1, ..., xi, дающих в сумме s, и ЛОЖЬ (false) в противном случае.Тогда решением задачи будет значение Q(N,0).Ясно, что Q(i,s) = false если s < A или s > B так что эти значения нет необходимости вычислять или хранить. Создадим массив, содержащий значения Q(i,s) для 1 ≤ i ≤ N и A ≤ s ≤ B.Массив может быть заполнен с помощью простой рекурсии. Первоначально, для A ≤ s ≤ B, положимQ(1,s) := (x1 == s).Теперь для i = 2, …, N, положимQ(i,s) := Q(i − 1,s) или (xi == s) или Q(i − 1,s − xi)   для A ≤ s ≤ B.Для каждого присвоения значение Q в правой части уже известно, поскольку оно либо занесено в таблицу предыдущих значений i или поскольку Q(i − 1,s − xi) = false если s − xi < A или s − xi > B. Таким образом, полное время арифметических операций составляет O(N(B − A)). Т.к. необходимо будет выполнить В-А сравнений (от наибольшей возможной суммы до наименьшей из возможных) не более N раз (общее количество чисел). Например, если все значения порядка O(Nk) для некоторого k, то необходимо время O(Nk+2).Алгоритм не считается полиномиальным, поскольку B − A не является полиномиальным от размера задачи, в качестве которого выступает число бит в числах. Алгоритм полиномиален от значений A и B, а вот они экспоненциально зависят от числа бит.Однако в программировании чаще всего используют модифицикацию алгоритма, описанного выше. Вместо двумерного массива используют одномерный m[0..M], при чем m[s] указывает на то, что для числа s такое подмножество существует. Для использования одномерного массива необходим еще один цикл по j в обратном направлении для положительных элементов исходного множества и в прямом для отрицательных, чтобы избежать беспорядка.Блок схема модифицированного алгоритма изображена на рисунке 2.3Рис. 2.3 Блок схема алгоритма динамического программированияПроверим работу алгоритма, используя в качестве исходных данных множество {3 4 5 -9 2 6} и сумму s=0.Посчитаем сумму положительных элементов В=3+4+5+2+6=20Сумма отрицательных элементов А= -9Создаем массив М и заполняем его нулями:01234567891011121314151617181920212223242526272829000000000100000000000000000000Элементу М[-A]=M[9] присваиваем 1Внешний цикл i=0 Внутренний цикл: J=20M[29]=m[29-3]=m[17]=0 J=19M[28]=m[28-3]=m[16]=0…..M[12]=m[12-3]=m[9]=1Выход из внутреннего циклаМассив М содержит значения:01234567891011121314151617181920212223242526272829000000000100100000000000000000Увеличение I на 1 и прогон цикла при i=2, массив М принимает значения:01234567891011121314151617181920212223242526272829000000000100110010000000000000Увеличим i еще на 1 (i=3):01234567891011121314151617181920212223242526272829000000000100111011100100000000Увеличим i еще на 1 (i=4):01234567891011121314151617181920212223242526272829100000000100111011100100000000Увеличим i еще на 1 (i=5):01234567891011121314151617181920212223242526272829100000000101111111111101000000Увеличим i еще на 1 (i=6):01234567891011121314151617181920212223242526272829100000000101111111111111111101Выводим M[0-(-9)]=M[9]=1То есть в исходном множестве имеются подмножества (хотя бы одно), сумма элементов которого равна 0.Если в конце вывести весь массив М, то можно судить обо всех возможных суммах всех возможных подмножеств исходного множества.2.3 Приближенный алгоритмАлгоритм приближенного решения задачи о сумме множеств работает следующим образом:Создаем список S, первоначально состоящий из одного элемента 0.Для всех i от 1 до N выполним следующие действия 2.1 Создаем список T, состоящий из xi + y для всех y из S 2.