私は次の問題を検討しています（非常に大まかな説明です）。
エッジに非負のコスト、開始ノードs、およびコスト定数が割り当てられているグラフがあると仮定しますC。次のことを調べます。
- 開始ノードから内の任意のノードまでの最短経路のコストがを超えない場所
Nから到達可能なノードの集合。ssNC - 上記のセット内のそれぞれについて
e、最短経路のコスト。
基本的にダイクストラコスト制約付き。
私の主な質問は、この問題に対するグラフ理論の正しい用語は何ですか?
私は「アクセシビリティ」や「到達可能性」しかし、これらは間違ったキーワードのようです。
最終的に、私は、1 つの (変更不可能な) かなり大きな (潜在的に約 1 億のエッジ) グラフ上で、このような多くのクエリに並列で効率的に回答できるアルゴリズムを探しています。文献を確認したいのですが、適切なキーワードに関するヒントが必要です。
アップデート：私の実際的な問題は次のとおりです。
大陸規模の道路網（歩行者専用道路か高速道路かといったエッジとノードのいくつかのプロパティを持つ有向グラフとしてモデル化されている）が与えられていると仮定します。エッジ コストは移動時間です。
特定の位置 (グラフ ノード) から開始して、1 時間以内に到達可能なノードはどれか、といったユーザー クエリに回答したいと思います。
また、多数のユーザー（可能であれば 10000 人以上）に対して、これらのクエリに非常に高速（可能であれば 200 ～ 300 ミリ秒未満）で並行して回答したいと考えています。
少なくとも 2 つの最適化が可能であると考えます。
- 適度なサイズの事前計算、たとえば、選択された「中心」ノードの事前計算された距離行列など。
- 検索を並行して実行すると、互いの「一時的な結果」から利益を得られる可能性があります。
私自身もいくつかアイデアを持っていますが、車輪の再発明を避けるために、まずは文献を調べたいと思います。
ベストアンサー1
あなたが扱っている問題の正しい用語は、「最短経路アルゴリズム」のファミリーです。到達可能性問題 (つまり Warshal) は、「ノード A と B の間に経路があるか?」という質問を扱います。この質問には 2 進数の答えがあり、この場合重みは必要なく、エッジを探すだけです。ただし、あなたの場合は、すべてのケースでノード A からノード B までの移動にかかる時間を考慮する必要があります。
現在、この問題に「正確に」適合するものはありません。ダイクトラ法、フロイド法、BFS または DFS に小さな変更を加えることでこの問題を解決できますが、グラフのサイズによって複雑さが増すため、ソリューションの構築方法を理解することが重要です。どのアルゴリズムを使用するかは、時間制約と使用可能なハードウェアの特定の組み合わせによって異なります。
この問題には 2 つのアルゴリズムによる解決策があります (すべてのエッジがすでにどこかに保存されており、何らかの方法でこのデータベースを照会できると想定しています)。
理想的な（架空の）世界では、フロイドのアルゴリズムを実行し、結果のマトリックスを Redis などに保存するだけで、10 ミリ秒未満でリクエストを処理できます。クライアントの数が増えた場合は、グラフが頻繁に変更される可能性は低いため（特定の問題では道路情報があるため）、必要に応じて Redis サーバーを追加できます。これの問題はソリューションのスペースの複雑さです。最も優れている点は、すべてが事前に計算されているため、リクエストへの応答時間が最小限に抑えられることです。これを何らかの形で実装するには、多くのスペースが必要です。DB がディスク（メモリではなくディスク）に保存されている Redis クラスターでも、すべてのサーバーに SSD があれば十分です。このオプションは、同時クライアントの数が増えても適切に拡張でき、応答時間も非常に高速です。ただし、このソリューションを使用できるかどうかは、グラフ内のノードの数によって異なります。各エッジを使用して距離を事前計算する必要がありますが、グラフ内のノードの数 N である NxN のマトリックスを格納するためのスペースのみが必要です。このマトリックスが Redis に収まる場合は、このアルゴリズムを使用して、すべてのノード間のすべての「距離」(この場合、コストの合計、つまり「移動時間」) を事前計算できます。後でリクエストを受け取ったときに、結果のマトリックスをクエリして、移動時間が指定された値未満のすべてのノードを取得する必要があります。このマトリックスを Redis に格納するときに、ソートされたセットを使用してノード番号を非常に高速に取得できる追加の最適化があります。
次に、コストに基づいて検索をプルーニングするように Dijktra、BFS、または DFS を変更する 2 番目のソリューションがあります。このシナリオでは、空間の複雑さが高いため Floyd をすでに破棄しています。つまり、グラフはノードとエッジの両方でかなり巨大です。この場合、ソリューションは、いずれかのアルゴリズムのバリエーションを使用してもほぼ同じですが、違いはグラフの保存方法です。3 つのアルゴリズムはすべて、必要な時間内に効率的に応答するように変更できますが、10,000 を超えるクライアントをサポートするには、グラフの保存に使用するデータベースが違いを生みます。ここでは、さらに 2 つのオプションがあります。
- 標準 SQL/NoSQL データベースの使用: このデータベースは、グラフ上で検索を実行するコード サーバー (C10K 問題のため複数) にサービスを提供するため、何らかの方法でシャーディングする必要があります。グラフ データ自体のサイズに応じて、この領域での研究を続けることをお勧めしますが、すべてのデータを Cassandra クラスターまたは同様のテクノロジに配置することができれば、必要な応答時間に合わせて最適化でき、非常に適切に拡張できます。
- グラフは実際には「地図」であるという事実を利用し、データに対して距離クエリを実行する方法を見つけます。これには、緯度や経度などを追加するためにグラフの保存方法を変更する必要がある可能性があります。したがって、アルゴリズムをグラフ全体に対して実行するという不合理な方法ではなく、特定のノードから一定の時間だけ離れると、それをマイル単位の距離 D に変換できるという事実 (概算で、安全のために 10 ～ 20 マイル程度を追加できます) を利用してプロセス全体を最適化し、データベースに対してクエリを実行してその距離 D までのすべてのノードを取得し、その小さなグラフに対して選択したアルゴリズムを実行します。この方法を使用してデータベースから取得したグラフは、エッジの実際の移動時間が移動距離にある程度比例している場合 (これは常に当てはまるとは限らないため、概算です)、すでにソリューションの近似値を提供していることに注意してください。これを小規模に実装するには、このようなクエリを実行できる PostgreSQL + PostGIS を使用しますが、最適な拡張/機能するソリューションを見つけるために、ここで調査を行う必要があります。
それが役に立てば幸い！