無向循環加重グラフでいくつかの計算を実行しようとしています。集計加重を計算するための適切な関数を探しています。

各エッジには、[1,∞) の範囲の距離値があります。アルゴリズムは、距離が短いほど重要性を高め (単調に減少する必要があります)、距離 ∞ に値 0 を割り当てる必要があります。

私の最初の本能は、単純に 1/d でした。これは、これらの両方の要件を満たしています。(まあ、技術的には 1/∞ は定義されていませんが、プログラマーは数学者よりも簡単に 1/∞ を無視する傾向があります。) 1/d の問題は、関数が 1/1 と 1/2 の違いをより重視することです。 1/34 と 1/35 の差よりも もう少し均等にしたいです。√(1/d) または ∛(1/d) または ∜(1/d) を使用することもできますが、可能性のクラス全体を見逃しているように感じます。助言がありますか？

(ln(1/d) を考えましたが、d が ∞ になると -∞ になり、それを 0 にする良い方法が思いつきません。)

後で：

要件を忘れていました: w(1) は 1 でなければなりません (これは既存の回答を無効にするものではありません。乗法定数は問題ありません)。

私は、人々が興味深いと思うかもしれない問題に取り組んできました (そして、おそらく誰かが既存の解決策を知っています)。

オブジェクトへのポインターのペアの長いリストで構成される大きなデータセットがあります。次のようなものです。

一度にメモリに保持するにはオブジェクトが多すぎるため (数百ギガバイトになる可能性があります)、ディスクに格納する必要がありますが、メモリにキャッシュすることができます (おそらく LRU キャッシュを使用)。

すべてのペアを処理するこのリストを実行する必要があります。これには、ペアの両方のオブジェクトをメモリにロードする必要があります (まだキャッシュされていない場合)。

では、質問: リスト内のペアを並べ替えて、メモリ内キャッシュの効果を最大化する (つまり、キャッシュ ミスの数を最小化する) 方法はありますか?

ノート

1. 明らかに、並べ替えアルゴリズムは可能な限り高速である必要があり、リスト全体を一度にメモリに保持できることに依存するべきではありません (そのための十分な RAM がないため)。必要に応じて数回リストします。

2. ペアではなく個々のオブジェクトを扱っている場合、簡単な答えはそれらをソートすることです。ペアの両方の要素を考慮する必要があるため、これは明らかにこの状況では機能しません。

3. 問題は最小グラフカットを見つけることに関連している可能性がありますが、問題が同等であっても、最小カットを満たす解決策はないと思います

4. 私の仮定では、ヒューリスティックはデータをディスクからストリーミングし、より良い順序でチャンクに書き戻すというものです。これを数回繰り返す必要があるかもしれません。

5. 実際にはペアだけでなく、トリプレット、クアッドレット、またはそれ以上の場合もあります。ペアに対してこれを行うアルゴリズムが簡単に一般化できることを願っています。

prefuse グラフ ツールキットを使用した経験のある人はいますか? すでに表示されているグラフを変更することはできますか? ノードやエッジを追加/削除し、表示を正しく適応させますか?

たとえば、 prefuse には、友人のネットワークを視覚化する例が付属しています。

http://prefuse.org/doc/manual/introduction/example/Example.java

私がやりたいことは、これに沿ったものです：

しかし、うまくいかないようです。ヒントはありますか？

私のアルゴリズム クラスの課題の 1 つは、クリーク問題を解決するための徹底的な検索アルゴリズムを設計することです。つまり、サイズnのグラフが与えられた場合、アルゴリズムは、サイズkの完全なサブグラフがあるかどうかを判断することになっています。答えは出たと思いますが、改善できると思わずにはいられません。ここに私が持っているものがあります:

バージョン 1

input : 配列 A[0,... n -1] で表されるグラフ、検索するサブグラフのサイズk 。

output : サブグラフが存在する場合は True、そうでない場合は False

アルゴリズム(Python のような疑似コード):

バージョン 2

input : サイズ n × n の隣接行列、k は検索する部分グラフのサイズ

output : サイズ k の A 内のすべての完全なサブグラフ。

アルゴリズム(今回は関数型/Python 疑似コード):

ご意見、ご感想、ご提案はありますか? これには、私が見逃した可能性のあるバグと、これをより読みやすくする方法が含まれます (私は多くの疑似コードを使用することに慣れていません)。

バージョン 3

幸いなことに、課題を提出する前に教授に相談しました。私が書いた疑似コードを彼に見せたとき、彼は微笑んで、私があまりにも多くの仕事をしたと言った. 1 つには、疑似コードを提出する必要がありませんでした。問題を理解していることを証明する必要がありました。2 つ目は、彼は力ずくで解決することを望んでいたことです。それで、私が提出したものは次のようになりました。

入力: グラフ G = (V,E)、kを見つけるためのクリークのサイズ

output : クリークが存在する場合は true、そうでない場合は false

アルゴリズム:

1. デカルト積 V ^kを求めます。
2. 結果のタプルごとに、各頂点が互いに接続されているかどうかをテストします。すべて接続されている場合は、true を返して終了します。
3. false を返して終了します。

更新: 2 番目のバージョンを追加しました。(私が知っている)派手な動的プログラミングを追加していませんが、これは良くなっていると思います。

更新 2 : バージョン 2 をより読みやすくするために、いくつかのコメントとドキュメントを追加しました。これはおそらく今日私が提出するバージョンです。みんなの助けに感謝します！複数の回答を受け入れることができればいいのですが、私を最も助けてくれた人の回答を受け入れました. 先生の考えをお伝えします。

グラフ内の冗長エッジを見つけるための確立されたアルゴリズムはありますか?

たとえば、a->d と a->e が冗長であることを確認してから、次のように削除したいと思います。

=>

編集: Strilanc は、私の心を読んでくれるほど親切でした。上記の例では、a->b も a->c も冗長とは見なされませんが、a->d は冗長と見なされるため、「冗長」という言葉は強すぎます。

n個の頂点 (| V | = n ) を持つ無向グラフG =( V , E ) が与えられた場合、 O ( n )にサイクルが含まれているかどうかをどのように確認しますか?

すべてのノードが他のすべてのノードに接続されている (冗長接続なし) グラフはどのように呼び出されますか?

このグラフには N * (N - 1) / 2 個のエッジがあることがわかっています。

特定のノードから/への有向グラフのすべてのサイクルを見つける (反復する) にはどうすればよいですか?

たとえば、次のようなものが必要です。

ない: B->C->B

（その価値については.NETのコンテキストで）

私は継承を使用しない傾向があり、インターフェイスはめったに使用しません。唾を吐き出して以来、インターフェイスが最高のものだと考えている人に出会いました。彼はそれらをどこでも使用します。私はこれを理解していないので、それに続く質問です。インターフェイスの理解度を確認したいだけです。

どこでもインターフェイスを使用している場合、将来を予測できると思います。アプリの要件が明確になり、アプリで何も変わることはありません。私にとって、特に開発の初期段階では、インターフェースが邪魔になります。このアプリは、その生涯を通じて非常にダイナミックです。インターフェイスからメンバーを削除または追加する必要がある場合、多くのものが壊れます。上記の人は、新しいメンバーを処理するために別のインターフェースを作成したと言っています。何も壊れません。

構成じゃないの？インターフェイスなしでコンポジションを使用しないのはなぜですか? より柔軟に。

インターフェイスからメンバーを削除する必要がある場合、彼はどのように処理しますか? 基本的に彼はしません。物事が壊れるだけで、影響を受けたすべての領域を確認して修正できるので、それは素晴らしいことです. 関連するすべてのコード パスがどこにあるかをよりエレガントに把握する代わりに、力ずくでクラスの一部を切り取る必要がありますか?

私はソフトウェア アプリケーションをグラフと考えています。完全なグラフは最悪のケースで、n(n-1)/2 になります。これは、すべてのクラスがすべてのクラスと対話することを意味します。ややこしい蜘蛛の巣。n-1 は最高であり、コミュニケーションの厳密なヒエラルキーです。新しい必要なメンバーを補うためだけに別のインターフェイスを追加すると、グラフに頂点が追加されます。これは、より多くのエッジと n(n-1)/2 方程式のより強力な実現を意味します。インターフェイスのないコンポジションは、ミックスインに似ています。一部のクラスのみが特定のメソッドを使用します。インターフェースを使用すると、すべてのクラスはメンバーを必要としない場合でもメンバーを使用することを余儀なくされます。コンポジション/ミックスイン アプローチでは、新しい不要なエッジは追加されません。