• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

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

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

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

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

Программа: Программная инженерия (Бакалавриат)

Оценка: 10

Год защиты: 2016

Объектом исследования в данной работе являются точные алгоритмы решения задачи коммивояжёра, реализующие метод ветвей и границ и его различные эффективные модификации. Предмет исследования —— время и выделенная память, затраченная на решение задачи коммивояжёра. Целью данной работы является анализ различных подходов, которые могут привести к уменьшению времени решения задачи коммивояжёра с помощью метода ветвей и границ. В процессе работы проводились экспериментальные исследования случайно сгенерированных полных графов. Результаты исследования можно применять в задачах логистики и прикладного программирования, например, при реализации навигаторов. Работа содержит 37 страниц, 4 главы, 6 рисунков, 9 таблиц, 30 источников. Ключевые слова: задача коммивояжёра, метод ветвей и границ, гамильтонов цикл, двоичная куча, упорядоченный список, самобалансирующиеся деревья, муравьинный алгоритм.

Текст работы (работа добавлена 29 мая 2016 г.)

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

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

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

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

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

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