Об объектно-ориентированной реализации метода ветвей и границ для задачи коммивояжёра

Часть I

Аннотация

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

Сведения об авторе

Boris Feliksovich Melnikov, Совместный Университет МГУ-ППИ в Шэньчжэне

профессор факультета вычислительной математики и кибернетики, доктор физико-математических наук

Опубликована
2022-07-20
Как цитировать
MELNIKOV, Boris Feliksovich. Об объектно-ориентированной реализации метода ветвей и границ для задачи коммивояжёра. Современные информационные технологии и ИТ-образование, [S.l.], v. 18, n. 2, july 2022. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/850>. Дата доступа: 29 sep. 2022
Раздел
Прикладные проблемы оптимизации