問題タブ [shortest-path]

Oracle 11g Spatial Databases の調査を開始しています。2 つのポイント間、またはポイントとラインストリング間の最短ルート (またはパス) を返すクエリがあるかどうかを知りたいです。

ラインストリング (ハイキング トレイル) とポリゴン (地理的な事故) を含むマップがあり、事故を回避しながら、現在地と最寄りのトレイルとの間の最短ルートを見つけたいと考えています。最寄りのトレイルを返すクエリが既にありますが、事故の輪郭を描いていません。

どうもありがとうございました。

問題: 重み付けされていない無向グラフで最短経路を見つける。

幅優先探索は 2 つのノード間の最短経路を見つけることができますが、これには最大で O(|V| + |E|) の時間がかかる場合があります。事前に計算されたルックアップ テーブルを使用すると、O(1) 時間でリクエストに応答できますが、O(|V|^2) スペースが犠牲になります。

私が疑問に思っていること:よりきめの細かい時空トレードオフを提供するアルゴリズムはありますか? 言い換えれば、次のようなアルゴリズムはありますか?

1. O(1) よりも長い時間で最短経路を見つけますが、双方向の幅優先検索よりも高速です
2. O(|V|^2) より少ないスペースを占有する事前計算されたデータを使用しますか?

実用面:グラフは 800,000 ノードであり、スモールワールド ネットワークであると考えられています。すべてのペアの最短パス テーブルはギガバイトのオーダーになります。これは最近では法外なことではありませんが、私たちの要件には合いません。

しかし、私は好奇心から質問しています。夜、私を悩ませているのは、「どうすれば全ペア ルックアップ テーブルのキャッシュ ミスを減らすことができるか?」ではなく、「聞いたことのないまったく異なるアルゴリズムが世の中にあるのだろうか?」ということです。

答えはノーかもしれませんが、それは問題ありません。

QuickGraph で A-star を使用して、ノード A からノード B への最短パスを、他のすべてのノードへの最短パスを生成せずに生成する方法 (ノード B が調査済みセットにある場合は停止) があるかどうかを尋ねたいと思います。

QuickGraph をゲームにプラグインしたいのですが、環境が課す時間制限から、すべてのパスを生成することはできません。

C＃で私の問題を解決するための他の提案は大歓迎です

事前に感謝します、Xtapodi

いくつかの最短経路検索アルゴリズムの小さなライブラリがあります。これらは、単純な無向グラフ (通常の表現 - 頂点とエッジ) 用に開発されました。ここで、マップが共有エッジ (つまり、ポリゴンのエッジ) で接続された 2 次元形状として表される、少し異なるシナリオにそれらを何らかの方法で適用したいと思います。このシナリオでは、検索はマップ オブジェクトまたは特定のポイント (x,y) で開始/終了できます。最善のアプローチは何ですか？アルゴリズムを形状に適用してみませんか? または、形状から「通常の」グラフを抽出しようとしますか (前処理時間を利用できます)? どちらの道を進むべきか本当にわからず、多くのオプションを検討するのに十分な時間（およびスキル）がないため、アドバイスをいただければ幸いです...

どうもありがとう

Rが統計パッケージであることは知っていますが、おそらくグラフを操作して2つのノード間の最短パスを見つけるためのライブラリがあります。

PS 実は、igraph と e1071 を見つけました。どちらが優れていますか? ありがとうございました

複数のスレッドで BGL の dijkstra_shortest_paths および astar_search 関数を使用し、結果の頂点とエッジのプロパティ マップを読み取るようにしたいと考えています。

スレッドセーフを確保するためにミューテックスを使用する必要があるかどうか疑問に思っています。

だからここに私の質問があります：

1. Boost.Graph スレッドの dijkstra_shortest_paths および astar_search 関数は安全ですか?

2. 複数のスレッドからグラフのプロパティ マップのみを読み取ろうとする場合、スレッド セーフについて心配する必要はありますか?

エッジの重みが正の有向非巡回グラフがあります。単一のソースと一連のターゲット (ソースから最も遠い頂点) があります。ソースから各ターゲットへの最短経路を見つけます。これらのパスの一部は重複しています。私が欲しいのは、すべてのエッジの重みの合計を最小化する最短パス ツリーです。

たとえば、2 つのターゲットを考えてみましょう。すべてのエッジの重みが等しい場合、それらの長さの大部分で 1 つの最短パスを共有する場合、2 つのほとんど重複しない最短パスよりも望ましい方法です (ツリー内のエッジが少ないほど、全体的なコストが低くなります)。

別の例: 2 つのパスは、その長さのごく一部が重複していません。重複していないパスのコストは高くなりますが、長い共有パスのコストは低くなります (結合コストが低い)。一方、2 つのパスはその長さの大部分が重複しておらず、重複していないパスのコストは低くなりますが、短い共有パスのコストは高くなります (合計コストも低くなります)。多くの組み合わせがあります。ソースからターゲットへのすべての最短経路を考慮して、全体のコストが最も低いソリューションを見つけたいと考えています。

言い換えれば、最短、最短パス ツリーが必要です。

これは誰かと何か鐘を鳴らしますか? 関連するアルゴリズムや類似のアプリケーションを教えてもらえますか?

乾杯！

次のグラフで A から B への 2 つのパスを計算する必要がありますが、パスがエッジを共有できないという制約があります。

うーん、わかりました。画像を投稿できません。ここにリンクがあります。

すべてのエッジには正の重みがあります。この例では、それらが等しいと仮定できると思います。私の素朴なアプローチは、上の画像の 2 番目のグラフに示されているように、Djikstra のアルゴリズムを使用して最初のパスを計算することです。

次に、グラフからエッジを削除し、2 番目のパスを計算しようとしましたが、失敗しました。上記の 3 番目の図に示されているパスを計算する Djikstra、Bellman-Ford (またはその他のもの) のバリエーションはありますか? (特別な知識やサブテンド リンクの削除なしで、という意味です)

巨大なグラフ内のノード間の最短経路をリアルタイムで見つける方法を探しています。数十万の頂点と数百万のエッジがあります。この質問は以前に尋ねられたことを知っており、答えは幅優先検索を使用することだと思いますが、それを実装するために使用できるソフトウェアを知りたいと思っています。たとえば、無向グラフで bfs を実行するためのライブラリ (python バインディング付き!) が既に存在する場合、それは完全に完璧です。

JUNG APIを使用して、中規模のグラフ（20〜100ノード）の複数のノード間の最短パスを計算します。現在、ノードを反復処理しており、単純な「ShortetsPath」関数を使用して、2つのノードの最短パスを計算しています。最短パスはすべてArrayListに入れられます。

}

多くのグラフやノードで計算する必要があるため、計算を高速化したいと思います。私の知る限り、JUNGAPIで使用できるのはダイクストラだけです。だから私の質問は次のとおりです：パフォーマンスを向上させるためにダイクストラを使用できますか？JUNG APIで他のアルゴリズムを利用できますか？最短経路に対してより多くの異なる方法を提供する別のグラフ実装を使用することは理にかなっていますか？

これまでのところありがとう:)