Re: [問題] 機率的實用
※ 引述《lakb (Jerry)》之銘言:
: 開發平台(Platform): (Ex: VC++, GCC, Linux, ...)
: Dev c++
: 問題(Question):
: 我目前在寫ACO(蟻群演算法),裡面有一個部份我不知該如何實作。隨著螞蟻的經過,
: 該路徑的費洛蒙濃度會提高,當下一隻螞蟻來的時候,費洛蒙濃度高的路經被選擇的機率
: 將會較高。
: 正題: 我不知道該如何寫出高濃度的路徑將有較高的機率會被選上(低濃度路徑仍有
: 被選上的可能),不知道有無函式可使用? 先謝謝大家的回答!
: 補充說明(Supplement):
假設 path[i] 的機率為 p[i]
那麼
N-1
Σ p[i] = 1
i=0
i
令path[i]的累積分佈 a[i] 為 Σ p[j]
j=0
http://en.wikipedia.org/wiki/Cumulative_distribution_function
然後你 random 一個 0..1 間的值 r,
如果 a[i-1] <= r < a[i]
那就選 path[i]
實作上, 因為 i==0時, 不存在 a[i-1]
如果還要做邊界查檢比較麻煩,
你可以在 a[0] 前面多塞一個 sentinel node 來避開這個special case
http://en.wikipedia.org/wiki/Sentinel_node
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.169.170.127
※ 編輯: cole945 來自: 1.169.170.127 (06/10 03:43)
※ 編輯: cole945 來自: 1.169.170.127 (06/10 03:44)
推
06/10 04:57, , 1F
06/10 04:57, 1F
討論串 (同標題文章)