c# - 如何计算最短路径？

Question

我有一个 80 个城镇的列表，每个城镇都有它们的地理经度和纬度。我需要找到最短的封闭路线（考虑到地球的曲率）。我在想我可以计算每个之间的距离（使用大圆距离公式），然后列出距离最短的距离（即 6400 次计算）。问题是我没有太多的编程经验，但我知道一点 C# 和 PHP。有人能告诉我我应该学习什么来解决这个问题的正确方向吗（例如，我应该了解更多关于 php 和 mysql 以使用数据库或其他东西来整理距离吗？）

Answer 1

这个问题被称为旅行推销员问题并且是 NP 难题 - 要确定性地解决它并获得最佳路线，您只能使用蛮力，作为替代方案，您可以使用大多数时间产生很好结果的启发式方法，但可能次优。

Answer 2

有多种方法可以计算给定 lat/long 的距离。我认为你不需要太多的编程经验来实现一个。

编辑

如果城市数量固定为 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> )

Answer 3

Dijkstras 算法是解决这个问题的最佳算法，复杂度较低。TSP 需要非常努力，80 个城市的树大小很大（对于这个没有城市是不切实际的，因为有 n！n 个城市的可能性）。我建议先画城市图并找出可能的路线，然后应用 Dijkstras.A * 算法是最好的，但初学者很难实现像这里这样的问题。