Об объектно-ориентированной реализации метода ветвей и границ для задачи коммивояжёра. Часть I
Authors: Мельников Б.Ф. 
Published: December 2024

Многие задачи дискретной оптимизации очень сложны для решения на компьютере – откуда и идёт их название «труднорешаемые». Точнее, сложны для решения (для описания алгоритмов, для программирования) возможные подходы к быстрому решению этих задач – переборное же решение, как правило, программируется просто, но работает соответствующая программа гораздо медленнее. Настоящую статью, как и предыдущую на эту тему, можно назвать «методической». В предыдущей статье на эту тему мы описали наш подход к методу ветвей и границ, прежде всего – для классической задачи коммивояжёра. Мы рассматривали как классические эвристики этого метода, так и их современную интерпретацию. У настоящей статьи основная цель – совсем иная, чем была в предыдущей: сейчас мы рассматриваем именно программные аспекты реализации этого метода. Сам программный комплекс мы выполнили на языке Си++ – и при этом пытались использовать все такие возможности языка, которые можно применять для программирования практически любых алгоритмов дискретной математики; конечно, в первую очередь мы имеем в виду объектно-ориентированные возможности. В конце статьи (в части II) мы приводим некоторые результаты вычислительных экспериментов. А в заключении мы рассматриваем несколько интересных тем для дальнейшего исследования студентами: обе статьи (предыдущая и настоящая) описывают только начало очень большого количества возможных тем, связанных с применением метода ветвей и границ для задач дискретной оптимизации, в частности – с объектно-ориентированной реализацией этого метода.

Many discrete optimization problems are very difficult to solve on a computer; hence they are titled “intractable”. More precisely, the possible approaches to solving these problems quickly are difficult to solve (for describing algorithms, for programming), and the iterative solution, as a rule, is programmed simply, but the corresponding program works much slower. This paper, like the previous one on this topic, can be called “methodical”. In the previous paper on this topic, we described our approach to the method of branches and boundaries, primarily for the classical traveling salesman problem. We considered both the classical heuristics of this method and their modern interpretation. The main purpose of this article is quite different from that of the previous article: now we consider the software aspects of the implementation of this method. We executed the software package in C++ – and at the same time tried to use all such language features that can be used for programming practically any algorithms of discrete mathematics; of course, first and foremost we mean object-oriented capabilities. At the end of the article (in Part II), we present some results of computational experiments. And in conclusion, we consider several interesting topics for further study by students: both papers (the previous one and the present one) describe only the beginning of a very large number of possible topics related to the application of the branches and bounds method for discrete optimization problems, in particular, with the object-oriented implementation of this method.