1

これがよく知られた解決策を伴うよく知られたクラスの問題である場合は、ご容赦ください。私は検索してきましたが、明らかに成功していません。

ある間隔 ([0,1] など) で発生する必要がある n 個のイベントがあるとします。各イベントは、事前定義された分布から確率的に引き出された期間に関連付けられています。間隔は、すべてのイベント期間を合わせたものよりもはるかに大きいと仮定します。有効なスケジュールは常に存在します。[0,1] 間隔でイベントが発生する確率は一様ではありませんが、イベントが重複しない限り、イベントは独立しています。

これらのイベントをスケジュールするための効率的で正確な (ランダムな) 方法は何ですか?

ここに私の現在の疑似コードがあります:

下限 = 分 (間隔)
上限 = 最大 (間隔)
numEvents の n について {
  描画開始時間
  描画終了時間
  while ( startTime が lowerBound 未満 || endTime が upperBound を超えている ) {
    描画開始時刻
    描画終了時間
  }
  イベントを追加
  lowerBound と upperBound をリセットして、残りの最大 (イベントのない) 間隔を定義します
}

新しいイベントをスケジュールする残りの間隔を大きくすることで、イベントを過分散にしています。つまり、他の方法よりも間隔を空けています。それでも、イベント数が少ない場合、これは非常に効率的で、おそらく非常に正確です。

私は C++ を使用していますが、それはおそらく無関係です。

この種の問題が何と呼ばれているか知っていれば、検索用語も大いに感謝します。

コンテキスト: ここでは正確さが最も重要です。これは、プログラム全体で時間のかかる手順ではありません。

4

1 に答える 1

2

各イベントをランダムに配置して衝突をチェックし、衝突があればスレートをきれいに拭き取り、最初からやり直します。

間隔はイベント期間の合計よりもはるかに大きいため、衝突はまれになるため、この方法は実際には非常に高速であるとあなたは言います。

あなたは正確な結果が欲しいと言います。それが何を意味するのかはわかりませんが、推測では、有効な解決策はすべて同じ確率であるはずです。問題の現在のソリューションはその要件を満たしていませんが、これは満たしています。

于 2013-03-15T23:25:42.407 に答える