We consider one of the cybernetic methods in biology related to the study of DNA chains. Namely, we are considering the problem of reconstructing the distance matrix for DNA chains. Such a matrix is formed on the basis of any of the possible algorithms for determining the distances between DNA chains. The objects of research of these algorithms (for mammals), as a rule, are one of the following 3 variants: the main histocompatibility complex, the mitochondrial DNA, and “the tail” of the Y chromosome. In the paper we give an improved algorithm for restoring the distance matrix for DNA chains. Compared to our previous publications, the following changes have been made to the algorithm. We abandoned the use of the branches and bounds method, but at the same time significantly improved the greedy auxiliary algorithm used in it. In this paper, we apply only this greedy algorithm to the general solution of the distance matrix reconstruction problem. As a result of the conducted computational experiments carried out on one of the two considered criteria for the quality of the algorithms, significant improvements were obtained compared to the results given in our previous publications. At the same time, the total running time of the algorithm remained almost the same as in the previous version.

Булынин А.Г., Мельников Б. Ф., Мещанин В. Ю., Терентьева Ю. Ю. Оптимизационные задачи, возникающие при проектировании сетей связи высокой размерности, и некоторые эвристические методы их решения Резюме: Рассмотрены две часто возникающие задачи при моделировании/модернизации сети связи, связанные с построением графа сети связи, удовлетворяющего определенным условиям. Данные задачи касаются оптимальной топологии графа сети

В литературе описано очень много задач, которые могут быть названы задачами дискретной оптимизации: от шифровки информации в Интернете (включая создание программ для криптовалют) до поиска групп «по интересам» в социальных сетях. Ча- сто эти задачи очень сложны для решения на компьютере, откуда и идёт их название «труднорешаемые». Точнее, сложны для решения (описания алгоритмов, програм- мирования) возможные подходы к быстрому решению этих задач, переборное же решение, как правило, программируется просто, но работает соответствующая про- грамма гораздо медленнее. Практически каждую из таких труднорешаемых задач можно назвать математиче- ской моделью. При этом часто и сама модель, и алгоритмы, предназначенные для её решения, создаются для одной предметной области, но могут найти применение и во многих других областях. Примером такой модели является задача коммивояжёра. Особенностью задачи является то, что при относительной простоте её постанов- ки нахождение оптимального решения (оптимального маршрута) является весьма сложным и относится к так называемому классу NP-полных проблем. Более того, согласно имеющейся классификации, задача коммивояжёра является примером оптимизационной проблемы, входящей в самый сложный подкласс этого класса. Однако основной предмет статьи — это не задача, а метод её решения, метод ветвей и границ. Он состоит из нескольких связанных между собой эвристик, и в моногра- фической литературе подобная мультиэвристичость метода ветвей и границ ранее отмечена, по-видимому, не была: разработчики алгоритмов и программ это должны были понимать сами. При этом сам метод может быть применён с небольшими изменениями и ко многим другим задачам дискретной оптимизации. Итак, классический вариант метода ветвей и границ — основной предмет настоящей статьи, но почти столь же важен и второй её предмет — задача коммивояжёра, тоже в классической её постановке. Речь идёт о применении метода ветвей и границ при решении задачи коммивояжёра, причём в отношении этого применения также можно употребить прилагательное «классическое». Однако в дополнение к класси- ческой версии этой реализации мы рассматриваем новые эвристики, связанные с необходимостью разработки алгоритмов реального времени.