Автор: Задача из теории графов
Коммивояжеру надо посетить N городов. У него плоскостопие, тяжелый чемодан с образцами, ему надоели отели и ресторанная еда. Он скучает по жене и дочери, хочет посетить каждый город только один раз и вернуться домой, покрыв минимальное расстояние и затратив минимум времени. Существует (N — 1)! возможных маршрутов, и, если N не слишком велико, допустим 5, можно взять карту, таблицу расстояний, карандаш, сложить все и определить какой из 24 маршрутов самый короткий. Как только N становится хотя бы двузначным, вычисление всех возможных маршрутов, даже если вы отличный вычислитель и быстро складываете в уме, растягивается на неопределенное число лет. Для 15 городов число маршрутов уже 1 триллион. Необходимо найти алгоритм, позволяющий определить оптимальный маршрут без долговременных вычислений.
Источник: роман Майкла Шейбона «Лунный свет», М. ;издательство «Иностранка», Азбука-Аттикус, 2017 (Большой роман).