Задача коммивояжера: на плоскости (в пространстве) расположены N городов, заданы расстояния между каждой парой городов. Требуется найти маршрут минимальной длины с посещением каждого города ровно один раз и с возвращением в исходную точку.
Задача решается 5-ю методами:
- метод полного перебора
- муравьиный алгоритм
- генетический алгоритм
- метод имитации отжига
- метод ветвей и границ
Пользователем вводится число городов. Программа случайным образом распределяет на карте города. В форме всего 5 карт для каждого алгоритма. Для алгоритмов предусмотрен ввод параметров. Есть возможность сохранить результаты 5ти расчетов для всех алгоритмов в Exel-документ. В результате строятся на карте рассчитанные маршруты и выводятся их длина и время, затраченное на расчеты.
Реализации программного кода самих алгоритмов поиска маршрутов взяты из разных источников.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent