Тезисы по дипломной работе
Студент: 4 курс группа 9-201. КФУ, Институт ВМиИТ, кафедра анализа данных и исследования операций
Тема: Методы иерархической кластеризации для приближенного решения задачи коммивояжера.
Цель дипломной работы состояла в том, чтобы исследовать эвристический алгоритм решения задачи коммивояжера. Алгоритм состоит из 3-х шагов:
1 Разбиение исходного множества городов на подмножества с помощью иерархической кластеризации. В зависимости от того, как определять расстояние между кластерами выделяют несколько методов кластеризации. Я исследовал 5 из них: метод ближайшего соседа, метод дальнего соседа, метод средней связи, метод центров и метод Уорда.
2 В каждом из получившихся кластеров решается задача коммивояжера в данном случае с помощь метода ветвей и границ. Из каждого получившегося контуров удаляется ребро максимальной длины.
3 Локальные маршруты соединяются. Сначала с помощью задачи коммивояжера определяется какой маршрут с каким соединять. После этого полным перебором находится кратчайший путь соединяющий локальные маршруты в глобальный (гамильтонов цикл для исходной задачи).
Для исследования алгоритма была разработана программа на языке Java в среде Intellij Idea. Программа решает задачу коммивояжера вышеописанным алгоритмом. Входные данные: множество точек. Выходные данные: гамильтонов контур.
После проведенных экспериментов были сделаны следующие выводы:
При использовании метода Уорда, получаются кластеры примерно равных размеров. Остальные 4 метода дают примерно одинаковое разбиение, кластеры получаются разных размеров. Метод дальнего соседа и метод средней связи дают наиболее хорошее разбиение. Наиболее плохое разбиение дает метод Уорда. При этом метод дальнего соседа и метод средней связи дают наибольшее число кластеров меньшей размерности, чем другие методы. Метод ближайшего соседа дает наибольшее число кластеров большой размерности, чем другие методы
При использовании метода дальнего соседа получается лучшее решение, чем при использовании других методов. У метода центров и метода средней связи примерно одинаковая погрешность. При увеличении размерности увеличивается погрешность. Также при высокой плотности множества точек погрешность меньше чем при сильном разбросе множества точек
