Задача коммивояжёра решается несколькими методами: 2

1. Метод перебора. 3 Нужно построить все возможные маршруты, сложить вес всех рёбер в каждом маршруте и найти путь с минимальной суммой. 3 Однако даже для небольшого количества городов решать задачу таким способом практически невозможно. 5
2. Метод ветвей и границ. 23 Концентрируется на том, чтобы отбрасывать заведомо плохие варианты. 3 Как и перебор, метод ветвей и границ гарантирует нахождение лучшего решения, но при этом он может найти его за приемлемое время. 3
3. Венгерский метод. 2

Для решения задачи коммивояжёра её надо представить как математическую модель. 1 При этом исходные условия можно записать в формате матрицы — таблицы, где строкам соответствуют города отправления, столбцам — города прибытия, а в ячейках указываются расстояния (время, стоимость) между ними. 1