В данном репозитории представлена реализация решения задачи Коммивояжера с помощью паралельных вычислений и сравнение времени, которое затрачивается на решение данной задачи различными способами.

Всего реализовано 4 метода решения:

• Рекурсия ( перебор всех подходящих маршрутов в графе рекурсивным способом )
• Цикл ( аналогичный перебор всех маршрутов, но уже без использования рекурсии )
• Многопоточность ( модификация метода с циклом, включающая в себя распределение обработки всех маршрутов на несколько потоков )
• Шейдер ( аналогичная реализация многопоточности, но уже на графическом процессоре с помощью MetalAPI)

Следующий график отображает сравнение скорости решения задачи для различного количества вершин (график представлен в логарифмической шкале и отображает количество затраченных секунд на решение задачи, все вычисления производились на процессоре Apple M1. В реализации многопоточности использовалось распаралеливание вычислений на 8 потоков)

// в данный график не включена реализация метода Цикл так как время на решение задачи аналогично рекурсивному методу.

Ниже представлены численные значения затрачиваемого времени различными методами и с различным количеством вершин (значения так же даны в секундах)