Задача коммивояжёра
Дан взвешенный граф. Нужно составить наименьший общий путь который включает в себя все вершины графа.
В разных версиях задачи начальный узел может быть задан или его нужно так же вычислить.
Сложность задачи , задача относится к NP-полным.
Ссылки
- Грокаем алгоритмы. Адитья Бхаргава. Питер. 2018. Глава 1. Знакомство с алгоритмами. Упражнения. Задача о коммивояжере
- Грокаем алгоритмы. Адитья Бхаргава. Питер. 2018. Глава 8. Жадные алгоритмы. NР - полные задачи. Задача о коммивояжере - шаг за шагом