Наилучший подход к производительности для поиска всех комбинаций чисел из заданного набора (> 80 элементов) для достижения заданной конечной суммы

Question

Прежде чем мне предложат пойти и продолжить поиск вместо того, чтобы задавать этот общий вопрос, пожалуйста, поймите мой вопрос подробно. У нас есть алгоритм, который делает это в PL SQL. однако это неэффективно, когда набор чисел имеет большое количество элементов. например, он хорошо работает, когда в наборе около 22 элементов. Однако после этого спектакль умирает. Мы работаем с базой данных 12c оракула, и эта комбинация поиска чисел является частью одного из наших приложений и переносится из таблиц оракула в ассоциативные массивы для поиска комбинаций. пример окончательной суммы требуется = 30 набор элементов на выбор {1,2,4,6,7,2,8,10,5} и т. д.

Мой вопрос в гисте: Действительно ли PL SQL подходит для написания такого алгоритма? Стоит ли искать другой язык программирования / технологию / серверную емкость / инструмент для обработки большего набора из более чем 80 элементов?

Answer 1

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

Как уже упоминали другие, эта проблема растет в геометрической прогрессии. Решение для 22 элементов даже не близко к решению для 80.

A алгоритм динамического программирования может быть в состоянии быстро найти, существует ли одно решение проблемы подмножества сумм. Но поиск всех решений требует тестирования 2 ^ 80 комплектов.

2 ^ 80 = 1 208 925 819 614 629 174 706 176. Это 1.2e24.

Это большое число. Давайте сделаем безумно оптимистичное предположение, что процессор может тестировать один миллиард наборов в секунду. Купите миллион из них, и вы сможете найти ответ примерно через 38 лет. Может быть, когда-нибудь квантовый компьютер сможет решить эту проблему быстрее.

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

Answer 2

Oracle не подходит для решения этой проблемы, потому что базы данных не подходят для него. На самом деле, я думаю, что эта проблема является NP-полной проблемой, поэтому действительно эффективных решений не существует.

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