Исследование влияния стоимости предвычисленного тура на ресурсные характеристики метода ветвей и границ для решения задачи коммивояжёра

ФИО студента: Фомичёв Михаил Игоревич

Руководитель: Ульянов Михаил Васильевич

Кампус/факультет: Факультет компьютерных наук

Программа: Системная и программная инженерия (Магистратура)

Год защиты: 2018

Не смотря на тот факт, что классический метод ветвей и границ для решения несимметричной задачи коммивояжёра был представлен в 1963 году J.D.C. Little, K.G. Murty, D.W. Sweeney, и C. Karel, он и по настоящий день остается одним из наиболее применимых алгоритмов точных алгоритмов для решения задачи. Однако, его временная сложность растет экспоненциально. С другой стороны, существует алгоритмы, которые не гарантируют нахождения оптимального решения. Такие алгоритмы принято называть метаэврестическими алгоритмами, они могут найти решение, которое будет близко к оптимальному (или даже оптимальное) для задач большой размерности за приемлемое время. В данной работе уделено вниманию анализу комбинации метода ветвей и границ с метаэврестическими алгоритмами для решения задачи коммивояжёра.

Выпускные квалификационные работы (ВКР) в НИУ ВШЭ выполняют все студенты в соответствии с университетским Положением и Правилами, определенными каждой образовательной программой.

Аннотации всех ВКР в обязательном порядке публикуются в свободном доступе на корпоративном портале НИУ ВШЭ.

Полный текст ВКР размещается в свободном доступе на портале НИУ ВШЭ только при наличии согласия студента – автора (правообладателя) работы либо, в случае выполнения работы коллективом студентов, при наличии согласия всех соавторов (правообладателей) работы. ВКР после размещения на портале НИУ ВШЭ приобретает статус электронной публикации.

ВКР являются объектами авторских прав, на их использование распространяются ограничения, предусмотренные законодательством Российской Федерации об интеллектуальной собственности.

В случае использования ВКР, в том числе путем цитирования, указание имени автора и источника заимствования обязательно.

Реестр дипломов НИУ ВШЭ