graph-algorithm

3熱

1答えて

Weighted Directed Acyclic Graphs：距離関数を定義するようなエッジ加重を求めるアルゴリズム？

私はDAG（Directed Acyclic Graph）で作成できるこの技術的な問題を抱えています。ノードはイベントを表します（タイミングは不明です）。リレーションシップをエンコードする方向性のあるエッジがあります。「私はあなたより若い/私はあなたの前で起こった」加重DAG（WDAG）がDAG上の距離関数を意味するように、エッジ加重（すなわち、「動的加重」）を推定する必要があります。言い換え

1熱

1答えて

有向グラフによる有向パスの類似性を比較するアルゴリズム

私はそこに2つの有向パスを持つ有向グラフを持っています。 2つのパス間の類似性を判断するアルゴリズムが必要です。 This postは、近似類似性を決定するためにLevenshtein distanceを使用して言及しています。私はまた、Hamming distanceが同様の指標を使用していることを認識しています。私の質問は：どのように2つのパスが互いに平行を実行ケースを処理します。つまり、

0熱

1答えて

有向グラフ内に存在するサイクルでノードを出力する

DFSアルゴリズムを使用してサイクルを検出できることは理解していますが、バックエッジhttp://cs.wellesley.edu/~cs231/fall01/dfs.pdfを検出してください。私は、上記の方法に従うと同時に、効率的で「クリーン」な方法でノードをノードに出力する方法を理解することができません。は、これは私が自分自身の実装でそれをやった方法ですおかげ

4熱

2答えて

一般シーケンシャルパターンアルゴリズムのMapReduce

Wikipediaの記事は、擬似コードを提供し、その少し混乱し、私はいくつかの適切なコードを見てみたいけれども、私は一般シーケンシャルパターンアルゴリズム（GSP）http://en.wikipedia.org/wiki/GSP_Algorithm の実装例を探しています（理想的にはPythonまたはJava）。誰も良いリファレンスを知っていますか？私はアルゴリズムを最初に理解してから、MapR

0熱

3答えて

有向グラフ内のある頂点から別の頂点への最短経路

私のグラフは非常に大きく、大きなグラフです。グラフの頂点は町を表し、辺は町から町へのバス旅行ルートを表します。目的は、ある頂点から別の頂点へのパスを見つけることです。アルゴリズムがバス間の転送時間を考慮することは非常に重要です。私はDijkstraのアルゴリズムを使用しますが、それはグラフ全体からわかり、一方向を見つけます。私は、頂点から頂点までの「最良の」方法のいくつかを見つける必要があります

3熱

2答えて

この分散データベースのデータロケーション最適化アルゴリズムの名前は？

データベースの大きなグラフが相互に接続されているとします。事実上、1つの巨大な分散データベースです。グラフ上の任意のノードは、近隣ノードから取得した結果を受け取り、結合された結果をクエリ・パスに戻すことで、近隣ノードを再帰的に照会することによってデータベース全体を照会できます。また、ノードのデータベースに「十分な」結果が含まれている場合、再帰を停止する機能があると仮定して、まともな結果が既に存在

0熱

2答えて

重み付け無向グラフ分割

頂点重みW（V）、E（G）と2つのノードsおよびtを埋め込んだ固定平面の無向循環平面グラフG（V、E）が与えられた場合、GそれをS（G）にsを、T（G）にtをとった2つの連結成分S（G）とT（G）に分割する。頂点sとtは両方とも埋め込みE（G）の外面に属する。私はパーティションのバランスが取れていることを望んでいます。頂点の重みの総和がほぼ同じである必要があります。いいアルゴリズムのアイデアを

-1熱

1答えて

グラフアルゴリズムの記述方法

2つのグラフを入力とするアルゴリズムの疑似コード（ラテックス）を作成しようとしています - グラフ内の各ノードを比較していますが、 1つのグラフのノードが他のグラフのノードと等しい場合は0、そうでない場合は1を返します。グラフのノードは別のグラフです。したがって、チェックは再帰的です。

2熱

2答えて

Java 2dを使用して描画するグラフノードを構成する方法

Java awtを使用してJFrameに入れ子にされた循環グラフを作成して描画するプログラムを作成しました。ノードの位置が明示的に指定されていないか、ランダムに作成されていると、グラフが非常に乱雑になり、エッジが交差して頂点が衝突するという問題があります。より均質でクリーンな方法でノードをより良く配布するために、再配置のアルゴリズムを実装したいと思います。誰かが私を助けることができますか？

25熱

2答えて

出発点に戻ることを考慮せずにトラベリングセールスマン問題（TSP）の問題名は何ですか？

私は、開始点に戻る方法とこれを解決するアルゴリズムを考慮して、TSPなしの問題名を知りたいと思います。私は、最短経路問題に見えたが、それは私が探していますものではありません、問題は2つの割り当てられたポイントからの最短経路を見つけます。しかし、私が探しているのは、私たちがnポイントを与え、開始点を1つだけ入力するという問題です。次に、すべてのポイントを正確に1回移動する最短経路を見つけます。（