Параллельный статистический алгоритм решения задачи о сумме

[virusmxa]

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