Алгоритм решения задачи о рюкзаке, основанный на обходе дерева вариантов укладки

Георгий Иванович Борзунов, Михаил Андреевич Куприяшин

Аннотация


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

Ключевые слова


графы; задача о рюкзаке; деревья

Полный текст:

PDF

Литература


1. Merkle R., Hellman M. Hiding Information and Signatures in Trapdoor Knapsacks // IEEE Transactions on Information Theory.
Vol. IT-24. М., 1978. С. 525–530.

2. Шнайер Б. Прикладная криптография. М.: Триумф, 2012. – 815 с.

3. Куприяшин М. А., Борзунов Г. И. Aнализ состояния работ, направленных на повышение стойкости шифрсистем на основе
задачи о рюкзаке // Безопасность информационных технологий. 2013. № 1. С. 111–112.

4. Осипян В.О. Разработка математических моделей систем передачи и защиты информации. М., 2006. – 371 с.

5. Подколзин В. В. Моделирование систем на основе односторонних рюкзачных отображений. АКД. М., 2011. – 24 с.

6. Horowitz E., Sahni S. Computing Partition with Applications to the Knapsack Problem // Journal of the ACM. 1974. № 21.
С. 277–292.

7. Woeginger G. J. Exact Algorithms for NP-Hard Problems: A Survey // Combinatorial Optimization / M. Jünger et al. Springer-Verlag
Berlin, 2003. P. 185–207.


Ссылки

  • На текущий момент ссылки отсутствуют.


Лицензия Creative Commons
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.