О классической версии метода ветвей и границ
Аннотация
В литературе описано очень много задач, которые могут быть названы задачами дискретной оптимизации: от шифровки информации в Интернете (включая создание программ для криптовалют) до поиска групп «по интересам» в социальных сетях. Ча- сто эти задачи очень сложны для решения на компьютере, откуда и идёт их название «труднорешаемые». Точнее, сложны для решения (описания алгоритмов, програм- мирования) возможные подходы к быстрому решению этих задач, переборное же решение, как правило, программируется просто, но работает соответствующая про- грамма гораздо медленнее.
Практически каждую из таких труднорешаемых задач можно назвать математиче- ской моделью. При этом часто и сама модель, и алгоритмы, предназначенные для её решения, создаются для одной предметной области, но могут найти применение и во многих других областях. Примером такой модели является задача коммивояжёра. Особенностью задачи является то, что при относительной простоте её постанов- ки нахождение оптимального решения (оптимального маршрута) является весьма сложным и относится к так называемому классу NP-полных проблем. Более того, согласно имеющейся классификации, задача коммивояжёра является примером оптимизационной проблемы, входящей в самый сложный подкласс этого класса. Однако основной предмет статьи — это не задача, а метод её решения, метод ветвей и границ. Он состоит из нескольких связанных между собой эвристик, и в моногра- фической литературе подобная мультиэвристичость метода ветвей и границ ранее отмечена, по-видимому, не была: разработчики алгоритмов и программ это должны были понимать сами. При этом сам метод может быть применён с небольшими изменениями и ко многим другим задачам дискретной оптимизации.
Итак, классический вариант метода ветвей и границ — основной предмет настоящей статьи, но почти столь же важен и второй её предмет — задача коммивояжёра, тоже в классической её постановке. Речь идёт о применении метода ветвей и границ при решении задачи коммивояжёра, причём в отношении этого применения также можно употребить прилагательное «классическое». Однако в дополнение к класси- ческой версии этой реализации мы рассматриваем новые эвристики, связанные с необходимостью разработки алгоритмов реального времени.
Литература
M. R. Garey and D. S. Johnson, Computers and Intractability, Moscow: Mir, 1982 (in Russian).
S. E. Goodman and S. T. Hedetniemi, Introduction to the Design and Analysis of Algorithms, Moscow: Mir, 1981 (in Russian).
J. Hromkovic, ˇ Theoretical computer science: introduction to Automata, computability, complexity, algori- thmics, randomization, communication, and cryptography, St. Petersburg, Russia: BKhV-Peterburg, 2010 (in Russian).
J. Hromkovic, ˇ Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomi- zation, Approximation, and Heuristics, Berlin: Springer, 2004.
R. Gera, S. Hedetniemi, and C. Larson, eds., Graph Theory. Favorite Conjectures and Open Problems, vol. 1, Berlin: Springer, 2016.
R. Gera, S. Hedetniemi, and C. Larson, eds., Graph Theory. Favorite Conjectures and Open Problems, vol. 2, Berlin: Springer, 2016.
B. F. Melnikov, E. A. Melnikova, and S. V. Pivneva, “Mahjongg Solitaire: a High School Student Scientific Project, Containing Elements of Artificial Intelligence,” Computer tools in education, no. 5, pp. 41–51, 2018 (in Russian); doi: 10.32603/2071-2340-2018-5-41-51
M. E. Abramyan, B. F. Melnikov, and E. A. Melnikova, “Finite Automata Table: a Science Project for High School Students,” Computer tools in education, no. 2, pp. 87–107, 2019 (in Russian); doi:10.32603/2071- 2340-2019-2-87-107
D. Applegate, R. Bixby, V. Chvatal, and W. Cook, The Traveling Salesman Problem: A Computational Study, NJ: Princeton University Press, 2007.
G. Gutin and A. Punnen, eds. Combinatorial Optimization. The Traveling Salesman Problem and Its Variations, Berlin: Springer, 2007.
Th. H. Cormen, Ch. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Moscow: Viljams, 2013 (in Russian).
V. N. Lyalikov, “Kompleks programm dlya issledovaniya metodov resheniya zadachi o kommi- voyazhere. Dissertation of the candidate of technical sciences,”, Ulyanovsk State Technical University, Ul’yanovsk, Russia, 2008 (in Russian).
M. Dorigo and L. M. Gambardella, “Ant Colonies for the Traveling Salesman Problem,” Biosystems, vol. 43, no. 2, pp. 73–81, 1997.
G. Bulynin, B. F. Melnikov, V. Y. Meshchanin, and Y. Y. Terentyeva, “Optimization problem, arising in the development of high-dimensional communication networks, and some heuristic methods for solving them,” Informatizatsiya i svyaz’, no. 1, pp. 34–40, 2020 (in Russian); doi: 10.34219/2078-8320- 2020-11-1-34-40
B. F. Melnikov, V. Y. Meshchanin, and Y. Y. Terentyeva, “Implementation of optimality criteria in the design of communication networks,” Journal of Physics: Conference Series, vol. 1515, no. 4, p. 042093, 2020; doi: 10.1088/1742-6596/1515/4/042093
B. F. Melnikov and M. A. Trenina, “The application of the branch and bound method in the problem of reconstructing the matrix of distances between DNA strings,” International Journal of Open Information Technologies, vol. 6, no. 8, pp. 1–13, 2018 (in Russian).
B. Melnikov, M. Trenina, and E. Melnikova, “Different Approaches to Solving the Problem of Reconstructing the Distance Matrix Between DNA Chains,” in Proc. SITITO 2018: Modern Information Technology and IT Education, vol. 1201, 2020, pp. 211–223; doi: 10.1007/978-3-030-46895- 8_17
B. F. Melnikov, E. V. Davydova, A. V. Nichiporchuk, and M. A. Trenina, “Clustering of situations in the algorithms for solving the traveling salesman problem and its application in some applied tasks. Part II. List metrics and some related optimization problems,” University proceedings. Volga region, vol. 4, no. 48, pp. 62–77, 2018 (in Russian).
B. F. Melnikov and A. N. Radionov, “O vybore strategii v nedeterminirovannykh antagonisticheskikh igrakh” [On the choice of strategy in nondeterministic antagonistic games], Izvestiya RAN. Programmi- rovanie, no. 5, pp. 55–62, 1998 (in Russian).
B. Melnikov and N. Romanov, “Eshche raz ob evristikakh dlya zadachi kommivoyazhera” [Once again about heuristics for the traveling salesman problem], Teoreticheskie problemy informatiki i ee prilozhenii, vol. 4, pp. 81–89, 2001 (in Russian).
B. F. Melnikov and S. V. Pivneva, “Prinyatie reshenii v prikladnykh zadachakh s primeneniem dinami- cheski podobnykh funktsii riska” [Decision making in applied problems using dynamically similar risk functions], Vestnik transporta Povolzhya, vol. 3, no. 23, pp. 28a–33, 2010 (in Russian).
N. Wirth, Algorithms + Data Structures, Moscow: Mir, 1989 (in Russian).
Kh. Sigal and A. P. Ivanova, Introduction to Applied Discrete Programming: Models and Computational Algorithms, Moscow: Fizmatlit, 2007 (in Russian).
B. Melnikov and E. Melnikova, “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, no. 2, pp. 16–20, 2007 (in Russian).
Материал публикуется под лицензией:
