Об объектно-ориентированной реализации метода ветвей и границ для задачи коммивояжёра
Часть II
Аннотация
Многие задачи дискретной оптимизации очень сложны для решения на компьютере – откуда и идёт их название "труднорешаемые". Точнее, сложны для решения (для описания алгоритмов, для программирования) возможные подходы к быстрому решению этих задач – переборное же решение, как правило, программируется просто, но работает соответствующая программа гораздо медленнее.
Настоящую статью, как и предыдущую на эту тему, можно назвать "методической". В предыдущей статье на эту тему мы описали наш подход к методу ветвей и границ, прежде всего – для классической задачи коммивояжёра. Мы рассматривали как классические эвристики этого метода, так и их современную интерпретацию. У настоящей статьи основная цель – совсем иная, чем была в предыдущей: сейчас мы рассматриваем именно программные аспекты реализации этого метода. Сам программный комплекс мы выполнили на языке Си++ – и при этом пытались использовать все такие возможности языка, которые можно применять для программирования практически любых алгоритмов дискретной математики; конечно, в первую очередь мы имеем в виду объектно-ориентированные возможности.
В конце статьи (в части II) мы приводим некоторые результаты вычислительных экспериментов. А в заключении мы рассматриваем несколько интересных тем для дальнейшего исследования студентами: обе статьи (предыдущая и настоящая) описывают только начало очень большого количества возможных тем, связанных с применением метода ветвей и границ для задач дискретной оптимизации, в частности – с объектно-ориентированной реализацией этого метода.
Литература
2. Melnikov B.F., Melnikova E.A. On the classical version of the branch and bound method. Computer Tools in Education journal. 2021;(1):21-44. (In Russ., abstract in Eng.) doi: https://doi.org/10.32603/2071-2340-2021-1-21-45
3. Melnikov B.F., Melnikova A.A. Infinite Trees in the Algorithm for Checking the Equivalence Condition of Iterations of Finite Languages. Part I. International Journal of Open Information Technologies. 2021;9(4):1-11. Available at: https://elibrary.ru/item.asp?id=45595955 (accessed 30.08.2022). (In Russ., abstract in Eng.)
4. Melnikov B.F., Melnikova A.A. Infinite Trees in the Algorithm for Checking the Equivalence Condition of Iterations of Finite Languages. Part II. International Journal of Open Information Technologies. 2021;9(5):1-11. Available at: https://elibrary.ru/item.asp?id=45671876 (accessed 30.08.2022). (In Russ., abstract in Eng.)
5. Shen A. Algorithms and Programming: Problems and Solutions. In: Springer Undergraduate Texts in Mathematics and Technology. New York, NY: Springer; 2010. 272 p. doi: https://doi.org/10.1007/978-1-4419-1748-5
6. Gutin G., Punnen A.P. The Traveling Salesman Problem and Its Variations. In: Combinatorial Optimization. Vol. 12. Boston, MA: Springer; 2007. 830 p. doi: https://doi.org/10.1007/b101971
7. Dorigo M., Gambardella L.M. Ant colonies for the travelling salesman problem. Biosystems. 1997;43(2):73-81. doi: https://doi.org/10.1016/S0303-2647(97)01708-5
8. Hromkovič J. Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. In: Texts in Theoretical Computer Science. An EATCS Series. Berlin, Heidelberg: Springer; 2004. 538 p. doi: https://doi.org/10.1007/978-3-662-05269-3
9. Posypkin M.A. [Multiplatform software package for solving optimization problems in a distributed computing environment]. Proceedings of the Institute for Systems Analysis Russian Academy of Sciences. 2009;46:24-42. Available at: https://www.elibrary.ru/item.asp?id=15323432 (accessed 30.08.2022). (In Russ.)
10. Melnikov B., Melnikova E. On the Classical Version of the Branch and Bound Method. Computer Tools in Education journal. 2022;(2):41-58. doi: https://doi.org/10.32603/2071-2340-2022-2-41-58
11. Melnikov B.F., Meshchanin V.Y., Terentyeva Y.Y. Implementation of optimality criteria in the design of communication networks. Journal of Physics: Conference Series. 2020;1515:042093. doi: https://doi.org/10.1088/1742-6596/1515/4/042093
12. Melnikov B.F., Panin A.G. The parallel implementation of the multiheuristical approach in the nucleotide sequence comparison problem. Science Vector of Togliatti State University. 2012;(4):83-86. Available at: https://elibrary.ru/item.asp?id=18755384 (accessed 30.08.2022). (In Russ., abstract in Eng.)
13. Melnikov B.F., Melnikova E.A. Situation Clustering in Real-Time Algorithms for Discrete Optimization Problems. Sistemy upravleniya i informatsionnye tekhnologii. 2007;(2):16-20. Available at: https://elibrary.ru/item.asp?id=11717006 (accessed 30.08.2022). (In Russ., abstract in Eng.)
14. Pokorni S., Janković R. Reliability estimation of a complex communication network by simulation. In: 2011 19thTelecommunications Forum (TELFOR) Proceedings of Papers. IEEE Computer Society; 2011. p. 226-229. doi: https://doi.org/10.1109/TELFOR.2011.6143532
15. Yu H., Oh J. Anytime 3D Object Reconstruction Using Multi-Modal Variational Autoencoder. IEEE Robotics and Automation Letters. 2022;7(2):2162-2169. doi: https://doi.org/10.1109/LRA.2022.3142439
16. Geldenhuys J., van der Merwe B., van Zijl L. Reducing Nondeterministic Finite Automata with SAT Solvers. In: Yli-Jyrä A., Kornai A., Sakarovitch J., Watson B. (eds.) Finite-State Methods and Natural Language Processing. FSMNLP 2009. Lecture Notes in Computer Science. Vol. 6062. Berlin, Heidelberg: Springer; 2010. p. 81-92. doi: https://doi.org/10.1007/978-3-642-14684-8_9
17. Han Y.-S. State Elimination Heuristics for Short Regular Expressions. Fundamenta Informaticae. 2013;128(4):445-462. (In Eng.) doi: https://doi.org/10.3233/FI-2013-952
18. Grandcolas S., Pain-Barre C. A hybrid metaheuristic for the two-dimensional strip packing problem. Annals of Operations Research. 2022;309(1):79-102. doi: https://doi.org/10.1007/s10479-021-04226-6
19. Baumgertner S.V., Melnikov B.F. Multi-heuristic approach for the star-height minimization of non-deterministic finite automata. Proceedings of Voronezh State University. Series: Systems Analysis and Information Technologies. 2010;(1):5-7. Available at: https://elibrary.ru/item.asp?id=15199639 (accessed 30.08.2022). (In Russ., abstract in Eng.)
20. Melnikov B., Romanov N. [Once again about heuristics for the traveling salesman problem]. Teoreticheskie problemy informatiki i ee prilozhenij. 2001;(4):81-92. Available at: https://www.elibrary.ru/item.asp?id=48722725 (accessed 30.08.2022). (In Russ.)
21. Makarkin S.B., Melnikov B.F. Geometric methods for solving the pseudo-geometric version of the traveling salesman problem. Stochastic optimization in informatics. 2013;9(2);54-72. Available at: https://www.elibrary.ru/item.asp?id=20960443 (accessed 30.08.2022). (In Russ., abstract in Eng.)
22. Bulynin A.G., Melnikov B.F., Meshchanin V.Y., Terentyeva Y.Y. Optimization problem, arising in the development of high-dimensional communication networks, and some heuristic methods for solving them. Informatization and Communication. 2020;(1):34-40. (In Russ., abstract in Eng.) doi: https://doi.org/10.34219/2078-8320-2020-11-1-34-40
23. Melnikov B., Dudnikov V., Pivneva S. Heuristic Algorithm and Results of Computational Experiments of Solution of Graph Placement Problem. In: Sukhomlin V., Zubareva E. (eds.). Modern Information Technology and IT Education. SITITO 2017. Communications in Computer and Information Science. Vol. 1204. Cham: Springer; 2021. p. 157-166. doi: https://doi.org/10.1007/978-3-030-78273-3_16
24. Melnikov B.F., Radionov A.N. A choice of strategy in nondeterministic antagonistic games. Programming and Computer Software. 1998;24(5):247-252.
25. Melnikov B., Eyrih S.N. On the approach to combining truncated branch-and-bound method and simulated annealing. Proceedings of Voronezh State University. Series: Systems Analysis and Information Technologies. 2010;(1):35-38. Available at: https://www.elibrary.ru/item.asp?id=15199645 (accessed 30.08.2022). (In Russ., abstract in Eng.)
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
