Квантовий генетичний алгоритм в задачі 0-1 пакування мультиплікативного рюкзака

Abstract

Задача про мультиплікативний рюкзак є узагальненням більш простої дискретної комбінаторної задачі 0-1 упаковки рюкзака. До неї може бути зведено багато прикладних задач розподілу обмежених ресурсів. Задача є NP-повною, тому знайти її точний розв’язок навіть при відносно невеликих значеннях параметрів n та m практично неможливо. Ефективними в цьому випадку є евристичні алгоритми, які дозволяють отримати близькі до оптимального розв’язки задач великої розмірності за прийнятний час. Одним із таких підходів є квантовий генетичний алгоритм, робота якого грунтується на поєднанні ідей квантових обчислень та технології класичних генетичних алгоритмів .