2022, випуск 4, c. 15-32
Одержано 19.11.2022; Виправлено 15.12.2022; Прийнято 20.12.2022
Надруковано 29.12.2022; Вперше Online 28.02.2023
https://doi.org/10.34229/2707-451X.22.4.2
Попередня | ПОВНИЙ ТЕКСТ | Наступна
Про використання кодів Грея для розв'язування 0-1 комбінаторних задач оптимізації в еколого-економічних системах
О. Трофимчук 1 
, В. Васянін 1 * , В. Соколов 2 , А. Чикрій 3 , Л. Ушакова 1
1 Інститут телекомунікацій і глобального інформаційного простору НАН України, Київ
2 Київський університет імені Бориса Грінченка, Україна
3 Інститут кібернетики імені В.М. Глушкова НАН України, Київ
* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Вступ. Розглядається застосування двійково-відображених (дзеркальних, рефлексивних) кодів Грея для розв’язання комбінаторних задач з псевдобулевими функціями (поліномами від булевих змінних). Наводиться рекурсивний алгоритм Ерліха для генерації послідовності рядків n-розрядних кодів Грея, в якій кожний наступний рядок відрізняється від попереднього тільки одним розрядом (бітом). Як приклад ефективності використання цих кодів розглянуто розв’язання двох комбінаторних задач з булевими змінними з повним перебором розв’язків, показано, як ці коди можна використовувати для ефективного обчислення значень цільової функції і обмежень. Наведено результати експериментального дослідження, які показують, що коди Грея можуть бути практично застосовані у схемах розгалуження, наприклад, у методі гілок і меж, коли кількість змінних у вузлах розгалуження вирішального алгоритму не перевищує 35.
Мета. Робота полягає у тому, щоб показати розробникам алгоритмів і програм як можна застосувати коди Грея у різних схемах розгалуження вирішального алгоритму, наприклад, у методі гілок і меж, коли кількість двійкових (булевих) змінних у вузлах дерева розгалуження невелика (менше 35).
Методика. Дослідження грунтуються на проведенні обчислювального експерименту розв’язання 0-1 задачі про ранець запропонованим алгоритмом перебору варіантів розв’язку з частковим і повним перерахунком значень цільової функції і обмеження задачі. При проведенні експерименту перевірялася також точність розв’язання задачі «жадібним» евристичним алгоритмом з часової складністю O(n2).
Результати. В наслідок проведеного експерименту встановлено, що алгоритм з частковим перерахунком цільової функції і обмеження може застосовуватися для практичних розрахунків у схемах розгалуження, коли кількість змінних у вузлах дерева розгалуження не перевищує 35. Алгоритм з частковим перерахунком швидше алгоритму з повним перерахунком у середньому в 7 разів. Евристичний «жадібний» алгоритм можна застосовувати на практиці для розв’язання 0-1 задачі про ранець великої розмірності (більше 10000 предметів), коли достатньо отримати наближене значення цільової функції при обмежених обчислювальних ресурсах.
Наукова новизна і практична значимість. Новизна роботи полягає у запропонованому підході до розв’язання комбінаторних задач оптимізації з псевдобулевими функціями з використанням кодів Грея. Показана ефективність запропонованого алгоритму з частковим перерахунком значень цільової функції і обмежень може застосовуватися на практиці в різних схемах розгалуження вирішального алгоритму.
Ключові слова: коди Грея, задачі комбінаторної оптимізації, час розв'язання задачі.
Цитувати так: Trofymchuk O., Vasyanin V., Sokolov V., Chikrii A., Ushakova L. On the Use of Gray Codes for Solving 0-1 Combinatorial Problems of Optimization in Environmental and Economic Systems. Cybernetics and Computer Technologies. 2022. 4. P. 15–32. https://doi.org/10.34229/2707-451X.22.4.2
Список літератури
1. Martello S., Toth P. Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc., 1990.
2. Drezner Z. Facility Location. A Survey of Applications and Methods. Springer, 1995.
3. Nemhauser G.L., Wolsey L.A. Integer and combinatorial optimization. John Wiley & Sons, Inc., 1999.
4. Schrijver, Combinatorial optimization. Polyhedra and efficiency. Berlin: Springer, 2003.
5. Kellerer H., Pferschy U., Pisinger D. Knapsack problems. Springer-Verlag Berlin Heidelberg, 2004. https://doi.org/10.1007/978-3-540-24777-7
6. Korte B., Vygen J. Combinatorial Optimization. Theory and Algorithms. Springer, 2005.
7. Hifi M., Michrafy M., Sbihi A. Heuristc algorithms for the multiple-choice multidimensional knapsack problem. J. of Oper. Res. Soc. 2004. 55 (12). P. 1323–1332. https://doi.org/10.1057/palgrave.jors.2601796
8. Akbar M.M., Rahman M.S., Kakobad M., Manning E.G., Shoja G.C. Solving the Multidimensional Multiple-choice Knapsack Problem by constructing convex hulls. Comp. and Oper. Res. 2006. 33 (5). P. 1259–1273. https://doi.org/10.1016/j.cor.2004.09.016
9. Shahriar Z., Akbar M.M., Rahman M.S., Newton M. M. A multiprocessor based heuristic for multi-dimensional multiple-choice knapsack problem. The J. of Supercomputing. 2008. 43 (3). P. 257–280. https://doi.org/10.1007/s11227-007-0144-2
10. Lazarev A.A., Werner F. A graphical realization of the dynamic programming method for solving NP-hard combinatorial problems. Computers & Mathematics with Applications. 2009. 58 (4). P. 619–631. https://doi.org/10.1016/j.camwa.2009.06.008
11. Leblet H.J., Simon G. Hard multidimensional multiple choice knapsack problems: an empirical study. Comp. and Oper. Res. 2010. 37 (1). P. 172–181. https://doi.org/10.1016/j.cor.2009.04.006
12. Posypkin M.A., Sin S.T.T. Comparative analysis of the efficiency of various dynamic programming algorithms for the knapsack problem. Computer Science. 2016 IEEE NW Russia Young Researchers in Electrical and Electronic Engineering Conference (EIConRusNW). 2016. https://doi.org/10.1109/EIConRusNW.2016.7448182
13. Gary M.R., Johnson D.S. Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman & Co. New York, NY, USA, 1979.
14. Hammer P.L., Rudeanu S. Boolean Methods in Operations Research and Related Areas. Berlin, Springer-Verlag; New York, Heidelberg, 1968. https://doi.org/10.1007/978-3-642-85823-9
15. Береснев В.Л., Агеев А.А. Алгоритмы минимизации некоторых классов многочленов от булевых переменных. Модели и методы оптимизации. 1988. № 10. С. 5–17.
16. Boros E., Hammer P.L. Pseudo-Boolean Optimization. Discrete Applied Mathematics. 2002. 123 (1–3). P. 155–225. https://doi.org/10.1016/S0166-218X(01)00341-9
17. Crama Y., Hammer P.L. Boolean Functions: Theory, Algorithms, and Applications. New York, Cambridge University Press, 2011. https://doi.org/10.1017/CBO9780511852008
18. Васянин В.А., Ушакова Л.П. Коды Грея в задачах комбинаторной оптимизации. Математичне моделювання в економіці. 2019. № 1–2. С. 63-69. http://dspace.nbuv.gov.ua/handle/123456789/162110
19. Trofymchuk O.M., Vasyanin V.A. Choosing the Capacity of Arcs with Constraint on Flow Delay Time. Cybernetics and Systems Analysis. 2019. 55 (4). P. 561–569. https://doi.org/10.1007/s10559-019-00165-0
20. Trofymchuk O.M., Vasyanin V.A. Simulation of Packing, Distribution and Routing of Small-Size Discrete Flows in a Multicommodity Network. Journal of Automation and Information Sciences. 2015. 47 (7). P. 15–30. https://doi.org/10.1615/JAutomatInfScien.v47.i7.30
21. Vasyanin V.A. Problem of Distribution and Routing of Transport Blocks with Mixed Attachments and Its Decomposition. Journal of Automation and Information Sciences. 2015. 47 (2). P. 56–69. https://doi.org/10.1615/JAutomatInfScien.v47.i2.60
22. Васянин В.А., Трофимчук А.Н., Ушакова Л.П. Экономико-математические модели задачи распределения потоков в многопродуктовой коммуникационной сети. Математичне моделювання в економіці. 2016. № 2. С. 5–21. http://dspace.nbuv.gov.ua/handle/123456789/131848
23. Gray F. Pulse code communication. U.S. Patent 2632058, March 17, 1953.
24. Гарднер М. Математические головоломки и развлечения. М: «Мир», 1999. 447с.
25. Knuth E. The Art of Computer Programming. Volume 4A / Combinatorial Algorithms. Part 1. Addison Wesley Longman, Inc., 2011.
26. Bitner J.R., Ehrlich G., Reingold E.M. Efficient Generation of the Binary Reflected Gray Code and its Applications. Comm. ACM. 1976. No. 19. P. 517–521. https://doi.org/10.1145/360336.360343
27. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений. М.: МФТИ, 2008. 326 с.
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна