竹園論壇

標題: [解法]轉移矩陣之組合數算法 [打印本頁]

作者: Sylveon 時間: 2014-5-10 21:44
標題: [解法]轉移矩陣之組合數算法
(LaTeX測試)
我們看一3-3轉移矩陣之例題：

今有甲乙兩箱，甲箱有一白球及一紅球，乙箱有二白球及二紅球。今天有一個很無聊的人，會隨機的挑甲箱的一顆球及乙箱的一顆球，然後互相交換。已知所有的白球、紅球都是一樣的。

Q1.當交換2次時，甲箱為一個白球一個紅球的機率是多少？
Q2.交換無限多次，呈穩定狀態時，甲箱為兩白球的機率是多少？

傳統解法：
想當然好孩子們會爆一個轉移矩陣，或是畫個噁心的樹狀圖。我們推出轉移矩陣：
[tex]A%3D%5Cbegin%7Bbmatrix%7D%20%5Cfrac%7B1%7D%7B4%7D%20%26%20%5Cfrac%7B1%7D%7B4%7D%20%26%200%20%5C%5C%20%5Cfrac%7B3%7D%7B4%7D%20%26%20%5Cfrac%7B1%7D%7B2%7D%20%26%20%5Cfrac%7B3%7D%7B4%7D%20%5C%5C%200%20%26%20%5Cfrac%7B1%7D%7B2%7D%20%26%20%5Cfrac%7B1%7D%7B4%7D%20%5Cend%7Bbmatrix%7D[/tex]

得Q1的解為[tex]A%5Cbegin%7Bbmatrix%7D%200%5C%5C%201%5C%5C%200%20%5Cend%7Bbmatrix%7D[/tex]

Q2的解即求[tex]AX=X[/tex]

該方法的缺點在於求矩陣乘積時的小數及順序容易把人搞得暈頭轉向的，有沒有方法能規避掉這討厭的運算呢？

另類解法：

定義下參數[tex]RR_x,RW_x,WW_x[/tex]，分別代表甲在第[tex]x[/tex]次交換後，使球變為紅紅、紅白、白白的方法數有幾種。

顯然的[tex]RR_0=0 , RW_0=1 , WW_0=0[/tex]，那我們怎麼知道第K次交換有幾種可能？顯然的[tex]RR,WW[/tex]是一樣的，我們可以一起考慮。

1.考慮 RR (WW)
若要形成RR，原本只能有兩狀況：[tex]RR,RW[/tex]，由RR變成RR的方法有2種，即把紅球的其中一球跟乙箱的紅球交換，共[tex]1\times2[/tex]種，以及由RW變成RR有[tex]2\times1[/tex]種，得下方方程式：

[tex]RR_x=2RR_x_-_1+2RW_x_-_1[/tex]

2.考慮 RW
形成RW可由所有狀況推移出來，但RR、WW基本上算出來是一樣的，我們一起算。由RR變成RW有6種方法，把R換成W或把W換成R，共[tex]1\times3+1\times3[/tex]，由RW換成RW有4種方法，就是把R跟乙箱的兩個R換，或是把W跟乙箱的兩個W換，共[tex]1\times2+1\times2[/tex]，得下方程式：

[tex]RW_x=4RW_x_-_1+6RR_x_-_1+6WW_x_-_1[/tex]

顯然[tex]RR=WW[/tex]，合併兩項得：

[tex]RW_x=4RW_x_-_1+12RR_x_-_1[/tex]

你覺得這有什麼用呢？我們來算算看x=2的狀況好了，帶入上述方程：
[tex]%5Cleft%5C%7B%5Cbegin%7Bmatrix%7D%20RR%20%26%200%20%26%202%20%26%2012%5C%5C%20RW%20%26%201%20%26%204%20%26%2040%5C%5C%20WW%20%26%200%20%26%202%20%26%2012%20%5Cend%7Bmatrix%7D%5Cright.[/tex]

得到答案：[tex]Q_1=40/(12+40+12)=40/64=5/8[/tex]

Q2即求[tex]\frac{RR_x}{RW_x}=\frac{RR_x+RW_x}{2RW_x+6RR_x}[/tex]後帶回比例求[tex]\frac{RR_x}{RR_x+RW_x+WW_x}[/tex]，得解[tex]\frac{1}{5}[/tex]。

我們稱方程組：
[tex]%5Cleft%5C%7B%5Cbegin%7Bmatrix%7D%20RR_x%20%3D%202RR_x_-_1%20+%202RW_x_-_1%5C%5C%20RW_x%20%3D%204RW_x_-_1%20+%2012RR_x_-_1%20%5Cend%7Bmatrix%7D%5Cright.[/tex]

為[tex]RR_x,RW_x,WW_x[/tex]「動態規劃方程式」之「轉移方程」，該算法用到了遞迴，並且避免了除法運算，只需精簡的計算即可達到我們所需的項數。動態規劃通常用於電腦程式之計算，是一個相當重要的技巧，不過該方法對大的缺點是求一般式相當困難，要求複變數遞迴，我也不會啊！

短短介紹，給大家一個參考 XD
[tex]sin_2[/tex]

歡迎光臨竹園論壇 (http://forum.tfcis.org/)