maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2020-1-72-85mais-1289Research ArticleAlgorithmsАлгоритм ветвей и границ для задачи коммивояжера не является алгоритмом прямого типаBranch and Bound Algorithm for the Traveling Salesman Problem is not a Direct Type Algorithmhttps://orcid.org/0000-0002-0887-1500МаксименкоАлександр НиколаевичMaksimenkoAleksandr N.

канд. физ.-мат. наук, доцент

PhD

maximenko.a.n@gmail.comЯрославский государственный университет им. П. Г. ДемидоваРоссияP. G. Demidov Yaroslavl State UniversityRussian Federation2020190320202717285Copyright © Максименко А.Н., 20202020Максименко А.Н.Maksimenko A.N.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1289

В настоящей работе рассматривается понятие линейного разделяющего алгоритма прямого типа, введенное В. А. Бондаренко в 1983 г. Понятие алгоритма прямого типа определяется с помощью графа решений задачи комбинаторной оптимизации. Вершинами этого графа служат все допустимые решения задачи. Два решения называются смежными, если существуют входные данные, для которых эти решения и только они являются оптимальными. Ключевой особенностью алгоритмов прямого типа является то, что их трудоемкость оценивается снизу кликовым числом графа решений. В 2015–2018 гг. было опубликовано пять работ, основными результатами которых являются оценки кликовых чисел графов многогранников, ассоциированных с различными задачами комбинаторной оптимизации. В качестве основной мотивации в этих работах приводится тезис о том, что класс алгоритмов прямого типа является широким и включает в себя многие классические комбинаторные алгоритмы, в том числе алгоритм ветвей и границ для задачи коммивояжера, предложенный J. D. C. Little, K. G. Murty, D. W. Sweeney, C. Karel в 1963 г. Мы покажем, что этот алгоритм не является алгоритмом прямого типа. Ранее, в 2014 г., автором настоящей работы было показано, что венгерский алгоритм для задачи о назначениях не является алгоритмом прямого типа. Таким образом, класс алгоритмов прямого типа не является настолько широким, как предполагалось ранее.

In this paper, we consider the notion of a direct type algorithm introduced by V. A. Bondarenko in 1983. A direct type algorithm is a linear decision tree with some special properties. the concept of a direct type algorithm is determined using the graph of solutions of a combinatorial optimization problem. ‘e vertices of this graph are all feasible solutions of a problem. Two solutions are called adjacent if there are input data for which these and only these solutions are optimal. A key feature of direct type algorithms is that their complexity is bounded from below by the clique number of the solutions graph. In 2015-2018, there were five papers published, the main results of which are estimates of the clique numbers of polyhedron graphs associated with various combinatorial optimization problems. the main motivation in these works is the thesis that the class of direct type algorithms is wide and includes many classical combinatorial algorithms, including the branch and bound algorithm for the traveling salesman problem, proposed by J. D. C. Little, K. G. Murty, D. W. Sweeney, C. Karel in 1963. We show that this algorithm is not a direct type algorithm. Earlier, in 2014, the author of this paper showed that the Hungarian algorithm for the assignment problem is not a direct type algorithm. ‘us, the class of direct type algorithms is not so wide as previously assumed.

метод ветвей и границзадача коммивояжералинейное разделяющее деревокликовое числоалгоритм прямого типаbranch and boundtraveling salesman problemlinear decision treeclique numberdirect type algorithmReferencesV. Bondarenko, A. Nikolaev, and D. Shovgenov, “1-skeletons of the spanning tree problems with additional constraints”, Automatic Control and Computer Sciences, vol. 51, no. 7, pp. 682–688, 2017.V. Bondarenko, A. Nikolaev, and D. Shovgenov, “1-skeletons of the spanning tree problems with additional constraints”, Automatic Control and Computer Sciences, vol. 51, no. 7, pp. 682–688, 2017.V. Bondarenko and A. Nikolaev, “On graphs of the cone decompositions for the min-cut and max-cut problems”, International Journal of Mathematics and Mathematical Sciences, vol. 2016, 2016.V. Bondarenko and A. Nikolaev, “On graphs of the cone decompositions for the min-cut and max-cut problems”, International Journal of Mathematics and Mathematical Sciences, vol. 2016, 2016.V. Bondarenko and A. Nikolaev, “Some properties of the skeleton of the pyramidal tours polytope”, Electronic Notes in Discrete Mathematics, vol. 61, pp. 131–137, 2017.V. Bondarenko and A. Nikolaev, “Some properties of the skeleton of the pyramidal tours polytope”, Electronic Notes in Discrete Mathematics, vol. 61, pp. 131–137, 2017.V. A. Bondarenko, A. V. Nikolaev, and D. Shovgenov, “Polyhedral characteristics of balanced and unbalanced bipartite subgraph problems”, Automatic Control and Computer Sciences, vol. 51, no. 7, pp. 576–585, 2017.V. A. Bondarenko, A. V. Nikolaev, and D. Shovgenov, “Polyhedral characteristics of balanced and unbalanced bipartite subgraph problems”, Automatic Control and Computer Sciences, vol. 51, no. 7, pp. 576–585, 2017.V. Bondarenko and A. Nikolaev, “On the skeleton of the polytope of pyramidal tours”, Journal of Applied and Industrial Mathematics, vol. 12, no. 1, pp. 9–18, 2018.V. Bondarenko and A. Nikolaev, “On the skeleton of the polytope of pyramidal tours”, Journal of Applied and Industrial Mathematics, vol. 12, no. 1, pp. 9–18, 2018.V. Bondarenko, “Nonpolynomial lowerbound of the traveling salesman problem complexity in one class of algorithms”, Automation and Remote Control, vol. 44, no. 9, pp. 1137–1142, 1983.V. Bondarenko, “Nonpolynomial lowerbound of the traveling salesman problem complexity in one class of algorithms”, Automation and Remote Control, vol. 44, no. 9, pp. 1137–1142, 1983.V. Bondarenko, “Geometricheskie metody sistemnogo analiza v kombinatornoy optimizatsii”, diss. ... dokt.fiz.-mat. nauk, Yaroslavl, 1993.V. Bondarenko, “Geometricheskie metody sistemnogo analiza v kombinatornoy optimizatsii”, diss. ... dokt.fiz.-mat. nauk, Yaroslavl, 1993.V. Bondarenko and A. Maksimenko, Geometricheskie konstruktsii i slozhnost v kombinatornoy optimizatsii. Moskva: URSS, 2008, 182 pp.V. Bondarenko and A. Maksimenko, Geometricheskie konstruktsii i slozhnost v kombinatornoy optimizatsii. Moskva: URSS, 2008, 182 pp.A. Maksimenko, “Kharakteristiki slozhnosti: klikovoe chislo grafa mnogogrannika i chislo pryamougolnogo pokrytiya”, Modelirovanie i analiz informatsionnykh sistem, vol. 21, no. 5, pp. 116–130, 2014.A. Maksimenko, “Kharakteristiki slozhnosti: klikovoe chislo grafa mnogogrannika i chislo pryamougolnogo pokrytiya”, Modelirovanie i analiz informatsionnykh sistem, vol. 21, no. 5, pp. 116–130, 2014.J. Little, K. Murty, D. Sweeney, and C. Karel, “An algorithm for the traveling salesman problem”, Operations research, vol. 11, no. 6, pp. 972–989, 1963.J. Little, K. Murty, D. Sweeney, and C. Karel, “An algorithm for the traveling salesman problem”, Operations research, vol. 11, no. 6, pp. 972–989, 1963.E. Reingold, J. Nievergelt, and N. Deo, Combinatorial algorithms: theory and practice. Pearson College Div, 1977, 433 pp.E. Reingold, J. Nievergelt, and N. Deo, Combinatorial algorithms: theory and practice. Pearson College Div, 1977, 433 pp.M. Padberg and M. Rao, “The travelling salesman problem and a class of polyhedra of diameter two”, Mathematical Programming, vol. 7, no. 1, pp. 32–45, 1974.M. Padberg and M. Rao, “The travelling salesman problem and a class of polyhedra of diameter two”, Mathematical Programming, vol. 7, no. 1, pp. 32–45, 1974.

The authors declare that there are no conflicts of interest present.