0

重みと乱数発生器を含むグラフがある場合、より望ましいエッジを選択するにはどうすればよいですか? x の重みの制約があり、x の重みを含む式が必要で、次のエッジなどを選択できるようにします。たとえば、重みが 5,10,15,20 の 4 つのエッジがあります。ランダム ジェネレーターを使用して重み 5 のエッジをより望ましいものにする方法はありますが、既にエッジ 5 を選択している場合は、制約を超えているため、重み 20 のエッジを選択する必要はありません。

4

2 に答える 2

2

1 つの特定のエッジが選択される確率を次のように定義します。

  P(select_this_edge) = (x - Weight_of_this_edge) / x

これにより、重みが低いエッジが選択される可能性が高くなり、「制約」x よりも重みが大きいエッジは選択できなくなります。

RNG (乱数ジェネレーター) が 0 から 1 の間の値を生成すると仮定すると、特定のエッジを選択するかどうかを決定するプロセスは、乱数を描画し、それが式で計算された確率以下かどうかを確認することです。

特定のニーズに応じて、式をわずかに変更できます。たとえば、重みが 0 のエッジが体系的に選択されるのを防ぐ小さな係数を導入して (選択されない可能性を残して)、逆に「制約」x エッジ値よりも高いエッジが選択されないようにします。

さて...上記では、確率を割り当てて、特定のエッジを選択する必要があるかどうかを決定する方法について説明しました。これは、実際にプログラム ロジックに個々のエッジを選択する方法があり、「この特定のエッジを選択する必要があるか?」という単純な質問を自問するだけで十分です。ただし、プログラム ロジックがエッジのリスト (エッジの完全なコレクションである可能性があります) を作成し、「これらの n 個のエッジのうち、どれを選択すればよいか?」というより複雑な質問に答えたい場合があります。
この 2 番目のタイプの問題に対処する方法を説明しようとしていましたが、さまざまなコメントの - 行間 - を読んで、目前の問題をよりよく理解していると思います...

編集（コメントでさまざまな説明の後）
疑わしいように、根本的な問題は確率の問題ではなく最適化問題の問題です（ただし、この場合、確率は確率論的な方法で解空間に検索を向けるために使用されます）。具体的には、この問題は、 Capacitated Vehicle Routing Problem
の多くのバリエーションの 1 つです。

最適化しようとしている特定のパラメーター (またはその組み合わせ) の詳細を知らなくても、OP の質問の 1 つに答えようとして、大まかにしか話せません:
重みに関連付けられた確率と確率を組み合わせても問題ありません。距離に関連？

一言で言えば、そうです。次のような式を提案したいと思いますが、単純な乗算でうまくいくかもしれません。

P(e) = Kw * Pw(e) + Kd Pd(e) + some_random_term
Where 
   P(e) is the probability of picking edge e, "all things considered"
   Kw and Kd are constant parameters which can be used to tweak the algorithm
   Pw(e) is the probability of picking egde e, with consideration to the Weight
   Pd(e) is the probability of picking egde e, with consideration to the Distance
   some_random_term is used to soften the algorithm in its tendency to favor too
      much high probability edges resulting in allowing the search process to get
      stuck in local minima.
      Rather than a added term, this can also be performed by a simple function
      which prevents the probability to be less than say 0.05 or more than say
      0.95.  A fancier sigmoid function may also do the trick.
于 2012-10-24T14:23:15.587 に答える
1

「より望ましい」とはどういう意味かによって異なります。また、「xの重みの制約があります」という意味もよくわかりません。しかし、一般に、位置 i で i 番目のエッジを選択する確率を格納する配列確率を作成できます。次に、0 から 1 の間の乱数を生成し、配列を反復処理します。数値が現在の位置での確率よりも小さい場合は、そのエッジを取ります。それ以外の場合は、現在の確率を数値から差し引いて、次の位置に移動します。したがって、擬似コードでは、次のようになります。

x = random([0.0, 1.0])
for i in 0..n
  if x < probabilities[i]
    choose(i)
    break
  else
    x -= probabilities[i]
  end
end

多くのエッジがある場合は、位置 i の 0 から i までのエッジの確率の合計を配列 accuracy_sums に保存し、その配列で x のバイナリ検索を実行して、その位置。

于 2012-10-24T14:24:22.730 に答える