c# - 最短ルートの計算方法は？

Question

それぞれの地理的な経度と緯度を含む 80 の町のリストがあります。最短の閉じたルートを見つける必要があります (地球の曲率を考慮して)。私は、それぞれの間の距離を計算し (大円距離式を使用)、最短距離のものをリストすることができると考えていました (6400 回の計算になります)。プログラミングの経験はあまりありませんが、C# と PHP は少し知っています。この問題を解決するために何を学ぶべきか、誰かが教えてくれますか (たとえば、距離を整理するためにデータベースまたは何かを使用するために、php と mysql についてもっと学ぶべきですか?)

Answer 1

この問題は巡回セールスマン問題として知られており、 NP困難です-決定論的に解決し、ブルートフォースのみを使用できる最適なルートを取得する代わりに、ほとんどの場合素晴らしい結果をもたらすヒューリスティックを使用できますが、最適ではありません。

Answer 2

緯度/経度を指定して距離を計算する方法はいくつかあります。実装するのにプログラミングの経験はそれほど必要ないと思います。

編集

都市の数が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

ダイクストラアルゴリズムは、複雑さの少ないこの問題に最適です.TSPは非常にハードワークが必要であり、ツリーサイズは80都市で巨大です（n都市にはn！の可能性があるため、この数の都市では実用的ではありません）。都市のグラフを作成し、可能なルートを見つけてから、ダイクストラ法を適用します。*アルゴリズムが最適ですが、初心者がこのような問題を実装するのは困難です。