Реализация и оценка качества эвристических алгоритмов для смешанной задачи китайского почтальона

В отчете представлены результаты исследовательской работы на тему «Реализация и оценка качества эвристических алгоритмов для смешанной задачи китайского почтальона», выполненной в соответствии с Приказом Национального исследовательского университета «Высшая школа экономики» № 2.3-02/0304-01 от 03.04.2017. Объектом исследования является задача поиска маршрута китайского почтальона в смешанном мультиграфе. Предметом исследований являются эвристические алгоритмы решения задачи китайского почтальона в смешанном мультиграфе. Цель исследования – реализация и оценка качества эвристических алгоритмов решения задачи китайского почтальона в смешанном мультиграфе. Задачи исследования.  Сделать обзор вариантов задачи китайского почтальона.  Сделать обзор алгоритмов решения смешанной задачи китайского почтальона.  Выбрать алгоритмы решения смешанной задачи китайского почтальона для модификации и последующей реализации.  Модифицировать и реализовать алгоритмы решения смешанной задачи китайского почтальона на языке С++.  Разработать методику оценки качества реализованных алгоритмов.  Определить входные данные для тестирования реализованных алгоритмов.  Экспериментальным путем оценить качество реализованных алгоритмов. Методы исследования:  изучение монографических публикаций и статей;  сравнительный анализ;  дискретная оптимизация. Научная новизна.  Предложены эвристические алгоритмы решения смешанной задачи китайского почтальона в мультиграфе.  Найдены Парето-оптимальные алгоритмы решения смешанной задачи китайского почтальона в мультиграфе. Эффективность полученных результатов подтверждена экспериментальными исследованиями реализованных алгоритмов на тестовых данных следующих размерностей: 50, 100, 200, 500, 1000, 1500, 2000 и 3000 вершин по критериям – время работы алгоритма и точность полученного решения.