34 подписчика
Предложенная Уильямом Гамильтоном головоломка «кругосветного путешествия» по додекаэдру состояла в том, чтобы пройти через все вершины додекаэдра (символизирующие города), побывав в каждой ровно один раз.
Позднее гамильтоновы #графы легли в основу нового направления в математике и каждый, кто начинал изучать эту тему, начинал с задачи коммивояжера.
Имеется p городов, расстояния между которыми известны. Коммивояжер должен посетить все p городов по одному разу, вернувшись в тот, с которого начал. Требуется найти такой маршрут движения, при котором суммарное пройденное расстояние будет минимальным.
Очевидно, что задача сводится к отысканию кратчайшего гамильтонова цикла в полном графе.
Умеете такое решать?
Около минуты
24 мая 2024