Разработка и экспериментальное исследование точных методов и алгоритмов оптимизации (на примере задачи коммивояжёра).
В интерфейсе есть область для вывода графика с элементами управления (возврат графика к изначальным координатам, предыдущее действие, следующее действие, движение по графику, масштабирование, настройки графика, сохранение графика в файл). Рядом с графиком расположена область для ввода координат. Координаты вводятся столбцом сверху в них. X и Y разделены запятой. Координаты с плавающей точкой следует вводить через запятую.
Был разработан алгоритм для перебора всех возможных способов решения задачи. Итоговый алгоритм содержит несколько допущений:
- Количество посещённых «городов» равно количеству «городов».
- «Города» должны быть посещены хотя бы один раз.
Алгоритм работает следующим образом:
- Генерируются всевозможные комбинации посещений городов.
- Отбрасываются варианты не соответствующие вышеописанному допущению.
- Для всех остальных вариантов считается длинна пути.
- Выбирается вариант с наименьшей длинной.
Алгоритм позаимствован из этого репозитория
Итоговая программа работала по следующему алгоритму:
- В каждой строке матрицы находится минимальный элемент и вычитается из всех остальных элементов строки. Также это было сделано и для столбцов. Таким образом получается матрица стоимости, каждая строка и каждый столбец которой содержат хотя бы один нулевой элемент.
- Для каждого нулевого элемента матрицы рассчитается коэффициент, который равен сумме наименьшего элемента строки и наименьшего элемента столбца. Из всех коэффициентов выбирается такой, который является максимальным.
- Удаляется строка и столбец, элементы получают значение бесконечности.
- Алгоритм повторяется до получения контура.
Алгоритм взят из данной статьи
Алгоритм динамического программирования строится на том, что минимальный путь между пятью городами, это минимальный путь между четырёх городов плюс расстояние до пятого. Таким образом расстояние задачу коммивояжёр можно разбить на множество подзадач, которые разбиваются на подзадачи.
Алгоритм взят из данной статьи
Особенность жадного алгоритма состоит в то, что при построении маршрута, он всегда выбирает между городами самый короткий путь.
