Re: [問題] 平均的亂數產生數字個數 C++[新問題]
※ 引述《csihcs (非天夜翔)》之銘言:
: 請不要在問題獲得回答之後,
: 卻把原文的問題敘述給修掉,
: 感覺這種作法,
: 像是把這邊的版友們當作是"呼之則來,揮之則去"、"利用完就可以丟的免洗筷"。
: 也讓之前沒有參與討論的人,
: 沒辦法知道當初問題是什麼,
: 回答的內容是回答什麼樣的問題,
< 恕刪 >
難得有前輩願意一起討論亂數問題,
小弟舉個較常被問到的瓶頸問題一起討論,
原 po 之問題可能只是其中之一小角,
甚至更精確的說,原 po 所列舉出之限制,
可能已造成矛盾現象 < 恕我理解力弱,一直猜錯原 po 要的是什麼 >
前面將敘述幾個簡單已解的問題,
放碼太長,只敘述其概念。
後半段是目前較多人想找到解答,
卻苦於一好之方式,我不知道方法或沒實做過或沒得到一好的解法的,
會打上 *
--------------------------------------
BASIC
(0) 獨立測試
這是我最不能理解原 po 給限制的原因。
< 可能我對他問題的 background 不了解 >
講擲銅板這件事,測試 100 次出現正面可能是 49 次;
測試 10000 次,出現正面可能是 5011 次,
所以我不懂硬要設平均值的意義在哪裡?
不就不符合亂數的本質了嗎?
(1) 大亂數問題
a. 線性組合 : ( rand() << 15 ) | rand() ; 但會有一堆數值不會被產生到,
甚至需求是一些較高密度的浮點亂數也會有此問題。
< 所以蒙地卡羅法用的亂數... >
* b. ieee754 : ieee754 欄位分 signed/exp/mantissa 欄位, 直接針對
這此欄位給整數亂數, 轉回 floating,
拿到 NAN / non-normalize 再重新產生一次, 這方法沒驗證過。
(2) 不重覆亂數
a. 暴力法 : 適用 get/gen 較低之情況。
b. 洗牌法 : 唯一經過均勻性證明的只有 knuth shuffle
<每張牌至少換一次的方法也被證過沒 knuth 來得勻,恕沒記來源>
這也是一般猜測 algorithm 裡面用的。
c. 排序法 : 再產生一相同大小 array, 塞 random, 排序時一起交換。
(3) 不均勻亂數
假設3個數字為 num={1,3,5} , 出現機率為 {0.5, 0.2, 0.3} , 一次產生一個。
a. 改善式洗牌法 : 如一個 array, 1有5個, 3有2個, 5有3個,共10個,
做 knuth shuffle。注意的是,
由於亂數本質必須是「獨立事件」,且考慮均勻性後,
不該做完一次 shuffle 就有 10 個亂數,而是每次要產生時,
就要做一次 shuffle ,只取一次。
b. 累計機率法 : 累計機率為 column = {0.0, 0.5, 0.7, 1.0},
產生一浮點亂數 frnd = [0.0,1.0),
找 i 使得 column[i] <= frnd < column[i+1]
取出之數字即為 num[i]
(4) 其他機率分佈模型
上面講的只是均勻分佈, 常見其他機率分佈模型如
指數分佈、常態分佈、波松公佈、gamma 分佈... etc,可由均勻分佈拿到,
可參考數值分析用書或統計學做轉換。
要講的是常態分佈,由於是對稱圖形,故公式轉換後將會是 mean +- rand()
以「獨立事件」為考量,個人認為也不該一次取二個。
---------------------------------------
SOME TOPIC
* 1. 均勻性測試
TAOCP 裡曾提及亂數六項測試項目 < 有興趣可去翻翻 >,
其中較讓人難以判斷的是 均勻性 與 初值獨立性,
推斷最後應該是統計學 p 檢定方式,去看 p-value 之結果如何,
這裡牽涉統計學較深,略過。
* 2. 符合什麼分佈?
一般在 CS 領域裡,較關心的是如何產生某種分佈之亂數;
有時反而是「反過來」,給了一堆數列,
想驗證這堆數列和目前已知的哪種機率分佈模型最為相似。
舉個例,記錄了銀行每個客戶的到達時間,是一組數列,
怎麼檢定這數列符合什麼分佈?
這問題我沒實際深入下去,也不知道有沒有軟體在做這件事,
"猜" 必須實作所有的機率分佈模型之 p 檢定。
* 3. 線性規劃 ( 演化式算法 )
一種較常見的線性規劃模型如下 < 式子隨便列的,可能是 infesible solution >
Object Function :
max f(x1,x2,x3) = 3x1+2sin(x2)+exp(x3)
Limit :
x1 + x2 + x3 = 20
1 <= x1 <= 10
4 <= x2 <= 15
6 <= x3 <= 14
x1, x2, x3 ε I
x1,x2,x3 會不會加上整數限制式因問題而異。
解這問題有一類型的概念是一直用亂數去猜 x1, x2, x3,
中間會有評估 f(x1,x2,x3) 好壞之方式,再加上跳脫 local solution 之機制,
諸如 基因、粒子、退火、螞蟻都是。
先聲明,shuffle 在這類問題,考慮到其他限制式(未列出)時往往不適用。
讓人頭大的一點來了:針對限制式而言,怎麼產生一組 solution ?
差一點的做法
slack = 20, x1 = random(1,10) = 5 , slack-=x1=15
slack = 15, x2 = random(4, 15)= 6, slack-=6=9
slack = 9 , x3 = 9
這種作法有兩個壞處,
(a) 它產生的解是不均勻的,這裡所謂的均勻指的是,
{1,4,6}, 和 {10,10,10},與其它符合限制式的解,產生之機率應該要一樣。
但這方法愈是邊界的解,其產生機率就愈偏激 。
< 可想一下, x3=14 出現之機率明顯低非常多 >
(b) 不是每次演算,都可符合限制式,如 x1=10, x2=9,剩下的 x3=1,
就和限制式衝突了,必須重新產生一次。如果限制式本身很龜毛,
光是重覆這步驟就費時許多。
雖類似問題常出現,
但目前我找不到一個,讓所有 {x1,x2,x3} 產生機率相同之方式。
SOME TOPIC 問題我認為是我遇過較難解的,
有經驗的大神也歡迎鞭策討論。
至於原 po 到底遇到怎樣的問題,我想應再次詳述為佳。
--
「自從我學了 C# , 人都變聰明 , 考試都考一百分」
「自從我學了 VB , 皮膚都變好 , 人也變漂亮了 」
「自從我學了 Java , 明顯變壯 , 個子也變高了 」
「自從我學了 C++ , 內分泌失調 , 頭都禿了... 」
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.76.161
※ 編輯: EdisonX 來自: 180.177.76.161 (05/03 16:00)
→
05/03 17:41, , 1F
05/03 17:41, 1F
推
05/04 01:02, , 2F
05/04 01:02, 2F
討論串 (同標題文章)