Об объектно-ориентированной реализации метода ветвей и границ для задачи коммивояжёра
Часть I
Аннотация
Многие задачи дискретной оптимизации очень сложны для решения на компьютере – откуда и идёт их название "труднорешаемые". Точнее, сложны для решения (для описания алгоритмов, для программирования) возможные подходы к быстрому решению этих задач – переборное же решение, как правило, программируется просто, но работает соответствующая программа гораздо медленнее.
Настоящую статью, как и предыдущую на эту тему, можно назвать "методической". В предыдущей статье на эту тему мы описали наш подход к методу ветвей и границ, прежде всего – для классической задачи коммивояжёра. Мы рассматривали как классические эвристики этого метода, так и их современную интерпретацию. У настоящей статьи основная цель – совсем иная, чем была в предыдущей: сейчас мы рассматриваем именно программные аспекты реализации этого метода.
Сам программный комплекс мы выполнили на языке Си++ – и при этом пытались использовать все такие возможности языка, которые можно применять для программирования практически любых алгоритмов дискретной математики; конечно, в первую очередь мы имеем в виду объектно-ориентированные возможности.
В конце статьи (в части II) мы приводим некоторые результаты вычислительных экспериментов. А в заключении мы рассматриваем несколько интересных тем для дальнейшего исследования студентами: обе статьи (предыдущая и настоящая) описывают только начало очень большого количества возможных тем, связанных с применением метода ветвей и границ для задач дискретной оптимизации, в частности – с объектно-ориентированной реализацией этого метода.
Литература
2. Shen A. Algorithms and Programming: Problems and Solutions. Springer Undergraduate Texts in Mathematics and Technology. Springer, New York, NY; 2010. 272 p. (In Eng.) doi: https://doi.org/10.1007/978-1-4419-1748-5
3. Melnikov B., Trenina M., Melnikova E. Different Approaches to Solving the Problem of Reconstructing the Distance Matrix Between DNA Chains. In: Sukhomlin V., Zubareva E. (eds.) Modern Information Technology and IT Education. SITITO 2018. Communications in Computer and Information Science. Vol. 1201. Springer, Cham; 2020. p. 211-223. (In Eng.) doi: https://doi.org/10.1007/978-3-030-46895-8_17
4. Melnikov B.F., Melnikova E.A., Pivneva S.V. Mahjongg Solitaire: a high-school student scientific project, containing elements of artificial intelligence. Kompjuternye instrumenty v obrazovanii = Computer Tools in Education journal. 2018; (5):41-51. (In Russ., abstract in Eng.) doi: https://doi.org/10.32603/2071-2340-2018-5-41-51
5. Abramyan M.E., Melnikov B.F., Melnikova E.A. Finite automata table: a science project for high school students. Kompjuternye instrumenty v obrazovanii = Computer Tools in Education journal. 2019; (2):87-107. (In Russ., abstract in Eng.) doi: https://doi.org/10.32603/2071-2340-2019-2-86-107
6. Gera R., Hedetniemi S., Larson C. Graph Theory: Favorite Conjectures and Open Problems – 1. Problem Books in Mathematics. Springer, Cham; 2016. 291 p. (In Eng.) doi: https://doi.org/10.1007/978-3-319-31940-7
7. Gera R., Haynes T.W., Hedetniemi S. Graph Theory: Favorite Conjectures and Open Problems – 2. Problem Books in Mathematics. Springer, Cham; 2018. 281 p. (In Eng.) doi: https://doi.org/10.1007/978-3-319-97686-0
8. Hromkovič J. Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin, Heidelberg; 2004. 538 p. (In Eng.) doi: https://doi.org/10.1007/978-3-662-05269-3
9. Gutin G., Punnen A.P. The Traveling Salesman Problem and Its Variations. Combinatorial Optimization. Vol. 12. Springer, Boston, MA; 2007. 830 p. (In Eng.) doi: https://doi.org/10.1007/b101971
10. Dorigo M., Gambardella L.M. Ant colonies for the travelling salesman problem. Biosystems. 1997; 43(2):73-81. (In Eng.) doi: https://doi.org/10.1016/S0303-2647(97)01708-5
11. Melnikov B.F., Melnikova E.A. Klasterizatsiya situatsii v algoritmakh realnogo vremeni dlya zadach diskretnoi optimizatsii [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 16.05.2022). (In Russ., abstract in Eng.)
12. 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. Informatizacija i svjaz' = 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
13. 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. Springer, Cham; 2021. (In Eng.) doi: https://doi.org/10.1007/978-3-030-78273-3_16
14. 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 16.05.2022). (In Russ., abstract in Eng.)
15. Makarkin S.B., Melnikov B.F. Geometricheskie metody reshenija psevdogeometricheskoj versii zadachi kommivojazhera [Geometric methods for solving the pseudo-geometric version of the traveling salesman problem]. Stohasticheskaya optimizaciya v informatike = Stochastic optimization in informatics. 2013; 9(2);54-72. Available at: https://www.elibrary.ru/item.asp?id=20960443 (accessed 16.05.2022). (In Russ., abstract in Eng.)
16. 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 16.05.2022). (In Russ., abstract in Eng.)
17. 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 16.05.2022). (In Russ., abstract in Eng.)
18. Vakhitova A. The basis automaton for the given regular language. The Korean Journal of Computational and Applied Mathematics. 1999; 6(3):617-624. (In Eng.) doi: https://doi.org/10.1007/BF03009953
19. Hashiguchi K. Algorithms for determining the smallest number of nonterminals (states) sufficient for generating (accepting) a regular language. In: Albert J.L., Monien B., Artalejo M.R. (eds.) Automata, Languages and Programming. ICALP 1991. Lecture Notes in Computer Science. Vol. 510. Springer, Berlin, Heidelberg; 1991. (In Eng.) doi: https://doi.org/10.1007/3-540-54233-7_170
20. Melnikov B., Melnikova E. On the Classical Version of the Branch and Bound Method. Kompjuternye instrumenty v obrazovanii = Computer Tools in Education journal. 2022; (2):41-58. (In Eng.) doi: https://doi.org/10.32603/2071-2340-2022-2-41-58
21. 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. (In Eng.) doi: https://doi.org/10.1088/1742-6596/1515/4/042093
22. Pokorni S., Janković R. Reliability estimation of a complex communication network by simulation. 2011 19thTelecommunications Forum (TELFOR) Proceedings of Papers. IEEE Computer Society; 2011. p. 226-229. (In Eng.) doi: https://doi.org/10.1109/TELFOR.2011.6143532
23. Yu H., Oh J. Anytime 3D Object Reconstruction Using Multi-Modal Variational Autoencoder. IEEE Robotics and Automation Letters. 2022; 7(2):2162-2169. (In Eng.) doi: https://doi.org/10.1109/LRA.2022.3142439
24. 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. Springer, Berlin, Heidelberg; 2010. (In Eng.) doi: https://doi.org/10.1007/978-3-642-14684-8_9
25. Yo-Sub Han. 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
26. Grandcolas S., Pain-Barre C. A hybrid metaheuristic for the two-dimensional strip packing problem. Annals of Operations Research. 2022; 309(1):79-102. (In Eng.) doi: https://doi.org/10.1007/s10479-021-04226-6
Это произведение доступно по лицензии 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.
