在加權隨機選擇中何時使用替換與非替換？

加權隨機選擇：替換與非替換

加權隨機選擇是各種應用中使用的基本技術。它涉及從給定列表中採樣元素，機率分佈由指定權重確定。當選擇具有替換的元素時，每個項目可以被選擇多次，從而導致選擇具有較高權重的項目的可能性更高。相比之下，無替換選擇會在選擇項目後限制其選擇。

尋找有效的加權隨機選擇演算法（尤其是替換演算法）可能具有挑戰性。現有方法（包括修改後的儲層演算法）被證明不適合從小列表大小中選擇顯著分數。

一種有效的方法：別名方法

在此場景中表現出色的一種方法是別名方法。該技術創建一組結構化的箱，每個箱代表加權清單的一部分。透過利用位元操作，可以有效地對容器進行索引，從而避免二進位搜尋。每個 bin 包含原始列表中的兩個元素，從而能夠有效地表示分佈。

例如，考慮五個等權重選擇的清單：(a:1, b:1, c:1, d: 1、e:1)。別名方法建立一組八個箱，每個箱的機率質量為 0.125。

1. 歸一化： 調整權重使其總和為 1.0。在這種情況下， (a:0.2 b:0.2 c:0.2 d:0.2 e:0.2).
2. 分區： 分配權重低於分區機率(0.125) 的bin，從重量最低。這裡，(p1{a|null,1.0},p2,p3,p4,p5,p6,p7,p8).
3. 填滿：用最高的填充分區中的剩餘空間權重變數。例如，(p1{a|null,1.0},p2{a|b,0.6},p3,p4,p5,p6,p7,p8)。

運行時選擇：

在運行時，我們產生一個隨機數並使用位運算來有效地確定與機率分佈相對應的 bin。如果 bin 被分割，我們使用隨機數的小數部分在 bin 中的兩個元素之間進行選擇。

總之，別名方法提供了一種有效的帶有替換的加權隨機選擇技術。它利用位元操作進行快速 bin 索引，並透過仔細地將權重劃分為可管理的 bin 來實現準確的機率分佈。

以上是在加權隨機選擇中何時使用替換與非替換？的詳細內容。更多資訊請關注PHP中文網其他相關文章！