1

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

各エッジには、[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 でなければなりません (これは既存の回答を無効にするものではありません。乗法定数は問題ありません)。

4

5 に答える 5

2

多分：

exp(-d)

編集：の行に沿ったもの

exp(k(1-d)), k real

あなたの追加の要件に適合します（あなたはそれを知っていたと思いますが、ちょっと）。

于 2009-01-26T16:23:22.087 に答える
1

上記の回答のいくつかは、ガウス分布のバージョンであり、これは良い選択であることに同意します。ガウス分布または正規分布は、自然界でよく見られます。次数無限の B-Spline 基底関数です。

これをブレンディング関数として使用することの欠点の 1 つは、その無限サポートが有限ブレンディング関数よりも多くの計算を必要とすることです。ブレンドは、製品シリーズの合計として検出されます。実際には、次の項が許容範囲を下回ると、合計が停止することがあります。

値の計算には計算コストがかかるため、可能な場合は静的テーブルを形成して離散ガウス関数値を保持します。必要に応じてテーブルの値を補間します。

于 2009-01-27T06:49:33.507 に答える
1

1/ln (d + k) はどうですか?

于 2009-01-26T16:25:00.600 に答える
0

これはどう？

w（ d）=（1 + k）/（ d + k）いくつかの大きなkの場合

d = 2 + kは、 w（d）=1/2の場所になります

于 2009-01-26T16:58:48.287 に答える
0

あなたは事実上、無限の線に沿った直線的な減少を探しているようです - d. 明らかに、このソリューションはガベージですが、距離に任意精度のデータ型を使用していない可能性があるため、 yourDatatype.MaxValue - d を使用して、線形減少関数を取得できます。

実際、(yourDatatype.MaxValue - d) + 1 を使用して double を使用することを検討することもできます。これは、距離が「無限大」の場合に 0 の重みを割り当てることができるためです (double には実際にその値があるため)。

もちろん、w(d) = double.infinity や w(d) = integer.MaxValue などの実装の詳細を考慮する必要がありますが、使用している実際のデータ型を知っていれば、これらは簡単に見つけることができます;)

于 2009-02-13T21:22:29.747 に答える