27 Feb
2015
27 Feb
'15
6:50 p.m.
Volodymyr Litovka:
Eсть населенные пункты есть дороги между ними
а есть какая-нибудь бесплатная тулза, чтобы на ней можно было считать расстояние, которое проходит коммивояжер по определенному маршруту?
В стандартном гугломапсе можно вбить сколько угодно промежуточных пунктов маршрута - и расстояние он покажет. По дорогам, вестимо. Для решения задачи коммивояжёра - поиска отпимальной последовательности обхода пунктов - есть, например, студенческая поделка над гугломапсом: http://gebweb.net/optimap/ У прямого решения задачи коммивояжёра экспоненциальная сложность. Сотня точек в общем виде не решается. А вообще, "курвиметр" - это совсем не то, что вы подумали, а прибор для решения упомянутой задачи ;) -- Олег