選択された頂点でルーティングするアルゴリズム

Question

私は通過する必要がある開始点、終了点、頂点を選択したいので、アルゴリズムはルーティングの最短経路を見つけるはずです。私はテーブルを持っていますRoutes Id |名前| StoreA | StoreB | StoreAとStoreBはStoreテーブルからのFKsです。私は片方だけのためにデータを保存します。 例：テーブルルート1 | Lidl-Kaufland | 1 | 2 | 157で、距離は同じですので戻ってはいけません.QuickGraphライブラリからBidirectionalGraphまたはUndirectedGraphを使用するかどうかはわかりません。

たとえば、このロードネットワーク：1：http://i.stack.imgur.com/mxcWe.png まず、この4つの頂点を選択して、開始点と終了点を選択します。 私はQuickGraph 3.6を使用しています。ここで最大の問題は、どのグラフを使用すればいいのですか？目的に合わせてアルゴリズムがありますか？ありがとう、私は私が私に答えるために必要なすべてを説明したことを願っています。

Answer 1

Traveling Sales Manの問題のようです。これには2つのアプローチがありました。

1. あなたはグラフの最小総コストを持っていると思いツリーにグラフを剪定したい場合は、プリムまたはクラスカルから最小スパニングツリーアルゴリズムを試してみてください。これは、最終的に、あなたが持っている既存のグラフから最小総コストグラフを得るでしょう。
2. 最小時間でグラフのすべてのノードを通過して開始ノードに戻したい場合は、Traveling Salesmanアルゴリズムを試すことができます。
3. これは実際の道路ネットワークであれば、有向グラフを使用したい場合もあれば、一部の道路は片道で、一部は2通りです。だから、あなたはいつも同じ距離が戻ってくると言うことはできません。
4. すぐに使用できるソリューションをご希望の場合は、PostGis、PostGreSql、PgRoutingとお試しください。すでにデータをデータベースに保存しているので、自分で必要なアルゴリズムを自分で手助けすることができます。

これが役に立ちます。