Хабы: Python, Алгоритмы, GPGPU
Мы уже решали задачу коммивояжёра точно методом динамического программирования. С тех пор прошло немало времени. Мне бы хотелось поделиться некоторыми соображениями по улучшению алгоритма, а также представить алгоритм пригодный для расчёта задачи коммивояжера на GPU.
Динамическое программирование — это метод решения сложных задач путём разбиения их на более мелкие подзадачи, решение которых легче и проще.
Основная идея метода заключается в том, чтобы не решать одну и ту же подзадачу многократно, а сохранять результаты решения подзадач и повторно использовать их для ускорения общего процесса решения.
Читать далее