問題タブ [graph-theory]

グラフのノードに重みがある場合、有向非巡回グラフのクリティカル パスを計算する (パフォーマンスに関して) 最良の方法は何ですか?

たとえば、次の構造があるとします。

クリティカル パスは A->B->F (合計重み: 10) である必要があります。

従来のGIS形式の地理データに基づいています。これらの行列は、さまざまな配車ルートの問題などの基本的な入力です。それらは通常、最良の時間または最短距離で作成できます。

ウェブ上のどこでクリークを見つけるためのブロン・ケルボッシュアルゴリズムの説明を見つけることができるか、またはここでそれがどのように機能するかを説明できますか?

「アルゴリズム 457: 無向グラフのすべてのクリークを見つける」という本に掲載されていることは知っていますが、アルゴリズムを説明する無料のソースが見つかりません。

アルゴリズムのソース コードは必要ありません。アルゴリズムの仕組みの説明が必要です。

次のようなツリー/有向非巡回グラフの実装が必要です。

• いかなる種類のソートもありません。
• これTreeNodeは、キーと可能な値の単なるラッパーです (ノードに値を設定する必要はありません)。
• 親と子の両方へのリンクが必要です。

私のためにこれを行う標準APIやコモンズなどに何かありますか?

私はそれを自分で書いてもかまいません (そして、私は確かに皆さんにそうするように求めているわけではありません) 私は車輪の再発明をしたくないだけです.

有向非巡回グラフの強度、特に特定のノードの強度を判断するための堅実なアルゴリズム/アプローチとして認識されているものは興味深いものです。これに関する主な質問は、次の 2 つのグラフに要約できます。

(グラフが表示されない場合は、ここをクリックするか、次のリンクにアクセスしてください: http://www.flickr.com/photos/86396568@N00/2893003041/

私の目には、A は A よりも強い立場にあります。リンクがノックアウトされた場合に、ノードがどれだけ強く残るかで強さを判断しています. 最初のものは細い「竹馬」、2番目のものは太い「茎」と呼んでいます。

ノードの強さを判断するためにこれまでに検討したアプローチは次のとおりです。

1) 下のノードの数をカウントし、上のノードの数を引きます。

• A=7、a=7、B=5、b=1

2) 各ノードの (終端までの) 完全なパスの数を数え、それらの長さを合計します。

• A=17 (1+5+5+5+1)、B=12 (4+4+4)、a=9 (3+3+3)、b=2
• これにより、茎ではなく支柱が強くなります。

3) すべての可能なパスを数え、すべてのノードを宛先として扱います。

• A=9 (A->B、A->C、A->D、A->E、A->G、2xA->F、2xA->H)、B=6、a=9、b= 2

これまでのところ、3 が最良の選択肢のように思えますが、DAG 用に一般化された、より優れた選択肢はありますか? これは既知の最善のアプローチを持っているものですか？原則は、グラフ内のできるだけ多くの情報を使用し、解決策を直感的に説明できるようにすることです。

いくつかのタイプのエンティティがあり、それぞれに独自のフィールドがあり、別々のテーブルに格納されています。
このようなテーブルの各レコードは、異なるテーブルの 0 個以上のレコードに接続できます。つまり、異なるエンティティ タイプのレコードにリンクできます。
ルックアップ テーブルを使用すると、(m(m-1))/2=O(m^2) 個の個別のルックアップ テーブルを初期化する必要があります。
6 つまたは 7 つの異なるエンティティ タイプに対してはまだ実行可能ですが、50 以上のそのようなタイプに対しても関連がありますか?
特に、特定のレコードには他のほとんどのエンティティ タイプへのリンクが必要になるため、理論的に言えば、ほぼ完全で無向の n 面グラフを扱うことになります。
この構造をリレーショナル DBMS に格納する方法を誰かが明らかにすることはできますか?
(重要な場合は Postgresql を使用していますが、他の DBMS のソリューションも同様に役立ちます)。
お時間をいただきありがとうございます！

ユヴァル

私は、グラフを解決する必要がある問題 (グラフによって解決するのが最適です) について、よりよく知ろうとしています。

誰かがグラフを利用した古い ACM プログラミング コンペティションの問題を抱えている場合、または解決したときに特に啓発的であると感じた別の問題を抱えている場合は、感謝します。グラフに慣れ、グラフ タイプの問題を簡単に特定し、基本的なグラフ トラバーサル アルゴリズムを利用できるようになりたいです。

誰でも私に送ることができる甘い問題を抱えていますか?

私はグラフの問題をより良く解こうとして、過去数年間の ACM プログラミング コンペティションの問題に取り組んでいます。

私が現在取り組んでいるのは、任意の数の無向グラフ ノード、それらの隣接ノード、およびノー​​ドを接続するエッジの距離が与えられていることです。私が必要とするのは、互いに最も遠い2つのノード間の距離です(ノードの数ではなく、重みの距離です)。

今、私はダイクストラのアルゴリズムを次の形式で持っています:

この実装では、特定のノードを与えることができ、そのノードからのすべての距離のリストが表示されます。したがって、その距離のリストで最大の距離を取得できますが、特定のノードがどちらかの端にある 2 つの最も遠いノードの 1 つであるかどうかはわかりません。

したがって、私が考えることができる唯一の解決策は、このダイクストラのアルゴリズムをすべてのノードで実行し、返された距離の各リストを調べて、最大の距離を探すことです。距離のリストを返す各ノードを使い果たした後、任意の 2 つのノード間の最大距離の値が必要です (2 つの最も広く離れた村の間の「道路」距離)。これは非常に計算コストがかかるように思われるため、これを行うためのより簡単な方法が必要です。問題は、最大 500 ノードのサンプル入力が存在する可能性があることを示しているため、非常に長くかかることは望ましくありません。これは私がそれを行うべき方法ですか？

問題のサンプル入力は次のとおりです。

合計ノード: 5

エッジ:
ノード 2 - 接続 - ノード 4. 距離/重量 25
ノード 2 - 接続 - ノード 5. 距離/重量 26
ノード 3 - 接続 - ノード 4. 距離/重量 16
ノード 1 - 接続 - ノード 4. 距離/重量 14

この入力例の答えは「67 マイル」です。これは、最も離れた 2 つの村の間の道路の長さです。

それで、私が説明した方法でそれを行うべきですか、それとももっと簡単で計算コストの低い方法がありますか?

Garmin や TomTom のようなナビゲーション システムは、常に私を魅了してきました。小さなマップ/ナビゲーション アプリケーションを実装して、さまざまなパス アルゴリズムを試し、それらに関する知識を広げたいと考えていました。

これは 2 つの部分からなる質問です。

1.) 地図データはどのように保存されますか? - 道路のネットワークがある場合、このデータは通常どのように保存されますか? 後で地図を再現するために、データのどの部分が保持されますか? 各道路は、方向を変える一連のポイントとして保存されていますか? このデータはどのようなファイル形式で保存されますか? これらのファイルを簡単に解析するために公開されているライブラリはありますか? 地図/道路データがどのように保存/表現されるかについての詳細を誰かが持っていますか?それは非常に役に立ちます.

2.) ナビゲーション/パス- このマップ データ (ガーミン風) で基本的なパスを実行する場合、有向グラフに変換されるという私の仮定は正しいですか? 各道路交差点は、頂点間の距離を重み付けするエッジを持つ頂点ですか? これは私がやろうと思っていたことなので、基本的なよく知られているパスアルゴリズムを試してみて、何が得られるかを確認してください。

米国で公開されているこの地図データを見たことがありますが、それがどのように表されているか、また有向グラフを作成できるほど詳細であるかどうかはわかりません。

誰かが情報を持っていれば、私はそれを感謝します。詳しい知識があればあるほど有利です。

誰かが良い C++ ツリーの実装を推奨できるかどうか疑問に思っています。

記録として、私はこれまで何度もツリー アルゴリズムを作成しており、それが楽しいものであることはわかっていますが、可能であれば実用的で怠惰になりたいと思っています。したがって、実用的なソリューションへの実際のリンクがここでの目標です。

注:バランスの取れたツリーやマップ/セットではなく、一般的なツリーを探しています。この場合、内部のデータだけでなく、構造自体とツリーの接続性が重要です。したがって、各ブランチは任意の量のデータを保持できる必要があり、各ブランチは個別に反復可能でなければなりません。