如何進行有替換和無替換的有效加權隨機選擇？

帶替換和不帶替換的加權隨機選擇

為了應對編程挑戰，我們尋求從列表中進行加權隨機選擇的有效算法，有替換和無替換。

有替換的加權選擇

有替換的加權選擇的一種有效方法是別名方法。此技術為每個加權元素建立一組相同大小的箱子。透過利用位元操作，我們可以有效地索引這些容器，而無需訴諸二分搜尋。每個 bin 儲存一個百分比，表示原始加權元素之間的邊界。

考慮五個具有相等權重的元素的例子：(a, b, c, d, e)。

別名方法實作

1. 歸一化權重：將每個權重除以總和，使其總和為 1.0。
2. 確定大於或等於該數字的最小 2 次冪元素（此處為 8）。
3. 為每個元素分配一個空分區。

4. 重複以下步驟，直到分配所有權重：

   • 將盡可能多的剩餘重量最小的元素放入空分區中。
   • 如果分區未填滿，則加入剩餘最重的元素。

對於我們的範例，經過幾次迭代後，我們有以下分割區：

• p1: {a, 1.0}
• p2: {a, b, 0.6}

運行時選擇

1. 產生0 到1 之間的隨機數。
2. 對隨機數進行位移以尋找分區索引。
3. 如果分區被分割，則使用移位數的小數部分來決定傳回哪個元素。

加權選擇而不替換

而演算法就像加權水庫方法存在用於無替換的非加權選擇一樣，這個問題仍然沒有解決。

以上是如何進行有替換和無替換的有效加權隨機選擇？的詳細內容。更多資訊請關注PHP中文網其他相關文章！