推 hilorrk:有很多做法吧 像是機率高的重複多次 機率小的重複少次 隨 06/10 04:57
※ 引述《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)