О классическом варианте метода ветвей и границ

Аннотация

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