• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Версия для слабовидящихЛичный кабинет сотрудника ВШЭПоискМеню

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

ФИО студента: Чичилева Наталия Игоревна

Руководитель: Авдошин Сергей Михайлович

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

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

Год защиты: 2018

Одна из самых известных задач комбинаторики, предложенная в 1934 году и широко применяемая в современной жизни, является задача коммивояжера. К сожалению, до сегодняшнего дня не было предложено такого решения этой задачи, которое давало бы нам верное решение за полиномиальное время, хотя классическая задача коммивояжера может использоваться не только для поиска оптимального решения, но и для множества задач в области логистика и бизнеса. Целью данной работы является исследование симметричной задачи коммивояжера. В данной работе объектом исследования является алгоритм решения задачи коммивояжера – метод штрафования вершин. Предмет исследования - сложность алгоритма для матриц номеров порядка симметричной задачи коммивояжер. Для достижения поставленной цели необходимо для различных методов штрафования вершин определить следующие параметры: • выборочное среднее и выборочную дисперсию числа итераций для заданного класса эквивалентных задач; • выборочное среднее и выборочную дисперсию времени вычисления для заданного класса эквивалентных задач для данных характеристик ЭВМ; • выборочное среднее и выборочную дисперсию числа итераций для задач заданной размерности из разных классов эквивалентности; • выборочное среднее и выборочную дисперсию времени вычисления для задач заданной размерности из разных классов эквивалентности для данных характеристик ЭВМ. Результаты данной работы будут способствовать дальнейшему сокращению временных и вычислительных затрат при решении задачи коммивояжера.

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

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

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

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

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

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