c# - 選択した頂点でのルーティングのアルゴリズム

Question

通過しなければならない始点、終点、頂点を選択したいのですが、アルゴリズムはルーティングの最短パスを見つける必要があります。Routes Id|Name|StoreA|StoreB|Kilometers を格納するテーブルがあります。ここで、StoreA と StoreB は Store テーブルの FK です。データは片道だけ保存します。例: テーブル Routes 1|Lidl-Kaufland|1|2|157 では、距離が同じであるため、帰り道ではありません。QuickGraph ライブラリの BidirectionalGraph または UndirectedGraph を使用するかどうかはわかりません。

たとえば、この Road Network: 1 : http://i.stack.imgur.com/mxcWe.png 最初にこの 4 つの頂点を選択し、次に始点と終点を選択します。私は QuickGraph 3.6 を使用していますが、ここでの最大の疑問は、どのグラフを使用すればよいか、目的に合ったアルゴリズムがあるかどうかです。ありがとうございました。私に答えるために必要なすべてを説明したことを願っています。

Answer 1

間違いなく、巡回セールスマンの問題のように聞こえます。これにアプローチしたのは2つあります。

1. グラフの合計コストが最小になるツリーにグラフを刈り込みたい場合は、Prim または Kruskal の最小スパニング ツリー アルゴリズムを試してください。これにより、最終的に、既存のグラフから最小の総コスト グラフが得られます。
2. 最短時間でグラフ内のすべてのノードを通過し、開始ノードに戻りたい場合は、巡回セールスマン アルゴリズムを試すことができます。
3. これが実際の道路網である場合は、有向グラフを使用することができます。一方通行の道路と双方向の道路があります。したがって、戻ってくる距離が常に同じであるとは言えません。
4. すぐに使えるソリューションが必要な場合は、PostGis、PostGreSql、およびPgRoutingを試してください。すでにデータベースにデータを保存しているので、必要なアルゴリズムを自分ですぐに使用できます。

お役に立てれば。