概率區間和圖表排序？

Question

當我有一個帶有權重和隨機生成器的圖表時，我如何選擇更合意的邊緣？我有一個x權重約束，我需要一個包含x權重的公式，並讓我選擇下一個邊，等等。例如，我有4,10,10,20,20的重量。如何使用隨機生成器使重量更加理想5的邊緣，而且當我已經選擇邊緣5時，我不需要選擇重量爲20的邊緣，因爲它超出了我的約束條件。

Answer 1

通過定義概率一個特定邊緣被選擇爲：

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

這將使具有低重量更可能被選擇的邊，和邊緣與比「約束」更大的權重，X ，不可能選擇。

假設RNG（隨機數發生器）產生0到1之間的值，決定是否應該選擇給定邊的過程是繪製一個隨機數並查看它是否小於或等於計算的概率在公式。

根據您的具體需要，您可以稍微改變公式，例如通過引入一個小系數來防止系統選擇權重爲0的邊（通過引入不會被選中的剩餘機會）並且相反地防止具有高於「約束」x邊緣值的邊緣從不被選擇。

現在......上述討論分配概率的方式來決定如果給邊緣應選擇。如果程序邏輯確實有選擇單個邊的方法，並且簡單地問自己一個簡單的問題「這個特定的邊是否應該被選中？」，這就足夠了。然而，程序邏輯可能已經提出了一個邊緣列表（可能是完整的邊緣集合），並且想要回答一個更復雜的問題：「這些邊緣中應該選擇哪一個？」。
我正要解釋如何去這第二類的問題，但在閱讀-between的各種意見的線 - ，我想我更好地理解手頭的問題...

---

編輯
涉嫌（在評論各種澄清之後），潛在的問題是，一個優化問題，而不是概率的一個（雖然在這種情況下，概率用於直接搜索到解決方案中的空間一個隨機的時尚）。
具體來說，問題是在Capacitated Vehicle Routing Problem

的許多變化的一個不知道的細節什麼具體的參數（或組合），我們正在設法優化，我可以從廣義上講只說，試圖回答的一個OP的問題：
可以將與Weight相關的概率與距離相關的概率組合起來嗎？

簡而言之，是是的。雖然我想建議一個類似於下面的公式：

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. 

Answer 2

這取決於您所說的「更理想」的含義。我也不太明白你的意思是「我有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 

如果你有很多的邊緣，你也可以讓這個更有效的通過我的位置在一個陣列probability_sums從0邊緣的概率之和存儲到我然後對該數組中的x進行二分搜索，並選擇該位置處的邊緣。