Как рассчитать кратчайший маршрут?

Question

У меня есть список из 80 городов с географической долготой и широтой.Мне нужно найти кратчайший закрытый маршрут (с учетом искривления земли).Я думал, что смогу вычислить расстояние между ними (используя формулу расстояния по большому кругу), а затем перечислить те, у которых самые короткие расстояния (это будет 6400 вычислений).Дело в том, что у меня нет большого опыта программирования, но я немного знаю C # и PHP.Может ли кто-нибудь подсказать мне правильное направление того, что я должен узнать, чтобы решить эту проблему (например, я должен узнать больше о php и mysql, чтобы использовать базу данных или что-то еще, чтобы разобраться в расстояниях?)

Answer 1

Эта проблема известна как Задача коммивояжера и является сложной задачей NP - решить ее детерминистически и получить оптимальный маршрут, вы можете использовать только грубую силу, в качестве альтернативы вы можете использовать эвристику, которая в большинстве случаеввремя дает отличный результат, но может быть неоптимальным.

Answer 2

Проблема «поиска кратчайшего пути» заставила меня задуматься об алгоритме dijkstra или A *. * Должен быть хорошим способом найти кратчайший путь между двумя точками, если вы уже рассчитали все эти расстояния.

• http://en.wikipedia.org/wiki/Dijkstras_algorithm
• http://en.wikipedia.org/wiki/A*_search_algorithm

Answer 3

Алгоритм Dijkstras является лучшим для решения этих задач с меньшей сложностью. TSP требуется очень тяжелая работа, и размер дерева огромен для 80 городов (это нецелесообразно для такого количества городов, поскольку для n городов существует n! Возможностей). Я предлагаюсначала нарисуйте график городов и выясните возможные маршруты, затем примените алгоритм Dijkstras.A * лучше, но новичкам трудно реализовать такие проблемы, как здесь.

Answer 4

Существует несколько способов определения расстояния по широте / длине . Я не думаю, что вам понадобится большой опыт программирования для его реализации.

EDIT

Если число городов статично и равно 80, и вы знаете, как рассчитать расстояние между городами, тогда простой способ - сохранить эту информацию в базе данных; со структурой типа:

--City
CityId
CityName
Latitude
Longitude

--CityCityDistance
StartCityId
FinishCityId
RouteDistance

Ваша таблица CityCityDistance будет иметь только несколько тысяч строк (если я помню, как работает математика), а затем, если вам когда-нибудь понадобится узнать город, ближайший к другому городу, sql будет выглядеть примерно так (в t-sql):

select top 1 ccd.FinishCityId, c.CityName 
from CityCityDistance ccd
join City c on ccd.StartCityId = c.CityId
where ccd.RouteDistance = (select min(RouteDistance) from CityCityDistance where StartCityId = <chosen city id> )