АЛГОРИТМЫ NP-ПОЛНЫХ ЗАДАЧ. ЧАСТЬ I

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

1. Bellman R. Notes on the theory of dynamic programming IV – maximization over discrete sets // Naval Research Logistics Quarterly. – 1956. – Vol. 3, № 1–2. – P. 67–70.

2. Pisinger D. Linear time algorithms for knapsack problems with bounded weights // Journal of Algorithms. – 1999. – Vol. 33, № 1. – P. 1–14.

3. Koiliaris K., Xu C. A faster pseudopolynomial time algorithm for subset sum // To appear in SODA ’17. – 2017. – 18 p. – URL: https://arxiv.org/abs/1610.04712v2.

4. Bringmann K. A near-linear pseudopolynomial time algorithm for subset sum // To appear in SODA’17. – 2017. – 18p. – URL: https://arxiv.org/abs/1610.04712v2.

5. Horowitz E., Sanni S. Computing partitions with application to the knapsack problem // Journal of the ACM (JACM). – 1974. – Vol. 21. – P. 277–292.

6. Schroeppel R., Shamir A. A T=O(2^n/2), S=O(2^n/4) algorithm for certain NP-complete problem // SIAM Journal on Computing. – 1981. – Vol. 10, № 3. – P. 456–464.

7. Cobham A. The intrinsic computational difficulty of functions // Proceedings of the Congress for Logic, Methodology and Philosophy of Science. – North-Holland, 1964. – P. 24–30.

8. Egmonds J. Paths, trees and flowers // Canadian Journal of Mathematics. – 1965. – Vol. 17. – P. 449–467.

9. Николаев А.В. Геометрический подход к задаче о разрезе. – Ярославль: ЯрГУ, 2014. – 68 с.

10. Ivan Rijsbergen C.J. Information Retrieval. – Glasgow: Dept. of Computer Science, University of Glasgow, 1979.

11. Adamansky A. Overview of full-text search methods and algorithms. – Novosibirsk: Novosibirsk State University, 2018. – 26 p.

12. Chen M., Mao S., Zhang Y., Leung V.C.M. Big Data. Related Technologies, Challenges, and Future Prospects. – Springer, 2014. – 100 p.

13. Лифшиц Ю. Точные алгоритмы и открытые проблемы // Современные задачи теоретической информатики. – URL: http://download.yandex.ru/class/...

14. Куликов А. Алгоритмы NP-трудных задач. Лекции. – СПб: Computer Science клуб СПб отделения МИАН, 2009.

15. Sinchev B., Sinchev A.B., Akzhanova J., Mukhanova A.M. New methods of information search. I // News of the National Academy of Sciences of Kazakhstan. Series of Geology and Technical Sciences. – 2019. – Vol. 3, № 435. – P. 240–246.

16. Sinchev B., Sinchev A.B., Akzhanova Z.A. Computing network architecture for reducing computing operation time and memory usage… // Патент USPTO. – 2019. – 38 p.

17. Akl S.G. Adaptive and optimal algorithms for enumerating permutations and combinations // The Computer Journal. – 1987. – Vol. 30. – P. 433–436.

18. Hoare C.A.R. Quicksort // The Computer Journal. – 1962. – Vol. 5. – P. 10–16.

19. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. – М.: Вильямс, 2005.