Re: [問題] 平均的亂數產生數字個數 C++[新問題]

看板C_and_CPP作者 (閉上眼的魚)時間13年前 (2012/05/03 07:53), 編輯推噓1(101)
留言2則, 2人參與, 最新討論串4/7 (看更多)
※ 引述《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
不重複亂數方法,以前討論過 #1BTNMaV6 (C_and_CPP)
05/04 01:02, 2F
文章代碼(AID): #1FeZbuKL (C_and_CPP)
討論串 (同標題文章)
本文引述了以下文章的的內容:
以下文章回應了本文 (最舊先):
完整討論串 (本文為第 4 之 7 篇):
文章代碼(AID): #1FeZbuKL (C_and_CPP)