本文介紹比較有效率計算路徑個數的演算法，以及一些數學概念的整合
[符號定義]
考慮點集 $k \in K = \{1,2,.....|K|\}$ (stages) ，以及每個 stage $k$ 的可能值 $x_k$ 與其空間集 $X_{k}$ (state space) 也就是
$$ \bigwedge_{k \in K}\bigg( x_k \in X_{k} \bigg)$$
另外我們把 $K$ 集定義有序陣列的概念(list,array) !! $K^{<} := [1,2,3,4,....|K|] , K^{>} := [|K|,....,2,1]$
而現實生活中有許多分類的層狀結構，數學上可寫成
$$ \bigwedge_{k \in K^{<}}\bigg(x_k\in \color{red}{X_{k}(x_{k-1})} \bigg)$$
其中 $\color{red}{X_{k}(x_{k-1})} \subseteq X_{k}$ 為 DependSet 的概念，代表給定 $x_{k-1}$ 下，$X_{k}$ 的可能值，這些 $\color{red}{X_{k}(x_{k-1})}$ 是已經被定義的，而且 $X_{1}(\underset{=\emptyset}{x_0}) \equiv X_{1}$
註: 每個 $X_{k}$ 只跟上一層 $x_{k-1}$ 值有關，而與前幾個值 $x_{k-2},x_{k-3}, ...$ 無關，
即類似馬可夫鍊(Markov Chain)相依，而非路徑相依 (Path-dependent)
==================================
舉例: 生物分類的界門綱目科屬種的概念
可以想成 $X_1 = $ 界 ，$X_2(x_1) = $ 門 ，$X_3(x_2) = $ 綱 ....
==================================
[問題定義]
定義
$$\mathcal{R} := X_{1} \times X_{2}(x_1) \times X_3(x_2) .... \times X_{|K|}(x_{|K|-1}) \subseteq \prod_{ k\in K^{<}} X_{k} $$
今天我們要計算 $\mathcal{R}$ 的個數，即 $|\mathcal{R}|$ ，直覺的概念是窮舉法(Brute & Force) ~ 先選定 $x_1 \in X_1$ ，再選定 $x_2 \in X_2(x_1)$ .... 最後選完 $x_{k} \in X_{k}(x_{k-1})$ ，我們把 $x_{K} = (x_1,x_2,....x_{|K|}) $相當於一條路徑，列入 +1 計算，這可利用深度搜尋演算法(DFS)達到，但是當 $|\mathcal{R}|$ 很大的時候就要數很久，甚至數不完，計算效率應該跟 $|\mathcal{R}|$ 一樣多，計算複雜度可寫為 $$\text{complexity } = O\left(\prod_{k \in K} |X_{k}| \right)$$
但事實上在大多數情況下存在簡單易懂，更快的算法 :D
[遞迴公式推導]
如果仔細把 $|\mathcal{R}|$ 寫開會得到
$$ |\mathcal{R}| = \sum_{x_K \in \mathcal{R}} 1 = \sum_{x_1\in X_1} \sum_{x_2 \in X_2(x_1)} \sum_{x_3 \in X_3(x_2)} ....\sum_{x_{|K|-1} \in X_{|K|-1}(x_{|K|-2})}\sum_{x_{|K|} \in X_{|K|}(x_{|K|-1})} 1 $$
注意: 請區分符號定義
$X_k$ (state space of stage $k$)
$x_k$(state value of stage $k$)
$x_{K}$ (vector of state values of all stages $k \in K$)
這時候會發現以下遞迴式跟上面的等價 !!
$$ \bigwedge_{k \in K^{>}} \left[\bigwedge_{x_{k-1} \in X_{k-1}} \bigg( S_{x_{k-1}} := \sum_{x_k \in X_{k}(x_{k-1})} S_{x_k} \bigg) \right]$$
其中 $$\bigwedge_{x_{|K|} \in X_{|K|}} \bigg( S_{x_{|K|}} = 1 \bigg) , S_{x_{0}} \equiv |\mathcal{R}|$$
註: 可以定義 $X_{0} := \{x_0\}$ 為單一虛擬點，彙整所有來自 $X_{1}$的邊 !!
而且會發現遞迴式的本質就是排列組合裡的"加法原理"，而且總共只需要$|K|$次兩層 for 迴圈，外圈掃過 $x_{k-1} \in X_{k-1}$，內圈掃過 $x_{k} \in X_{k}(x_{k-1})$做相加，計算複雜度約為
$$\text{complexity} = O\left(\sum_{k \in K^{<}} |X_{k-1}|\cdot |X_{k}|\right)$$
效率快很多，原因在於有些值已經算好不必每次都鑽到最深層 !! 不過需要多紀錄一些算好的數字，正所謂空間換取時間 !!!
[計算複雜度方程式比較]
如果令 $|K| = 4 $，$a = |X_1|$ , $b = |X_2|$ , $c = |X_3|$ , $d = |X_4|$
則窮舉法類似 $abcd$ ，而優化法類似 $ab+bc+cd$ ，所以在 $a,b,c,d$ 很小的時候不易察覺其差異，甚至可能窮舉法比優化法快，窮舉法需要 "路徑個數"的計算，優化法只需要"邊的個數"計算 !!
[矩陣向量乘法本質]
如果仔細看遞迴式某部分 ~
$$\bigwedge_{x_{k-1} \in X_{k-1}} \bigg( S_{x_{k-1}} := \sum_{x_k \in X_{k}(x_{k-1})} S_{x_k} \bigg)$$
改寫成
$$\bigwedge_{x_{k-1} \in X_{k-1}} \bigg( S_{x_{k-1}} := \sum_{x_k \in X_{k}} \underbrace{\color{blue}{[x_k \in X_{k}(x_{k-1})]}}_{\text{Iverson bracket}} \cdot S_{x_k} \bigg) $$
今把 $(S_{x_{k-1}})_{x_{k-1} \in X_{k-1}}$，$(S_{x_k})_{x_k \in X_k}$ 想成向量們，$\color{blue}{[x_k \in X_{k}(x_{k-1})]}$ 想成 0-1 $|X_{k-1}| \times |X_{k}|$ 鄰接矩陣(adjacency matrix) $A_k := [a_{x_{k-1},x_{k}}] = \color{blue}{[x_k \in X_{k}(x_{k-1})]}$
則我們把原問題可以寫成矩陣的連乘 :D
$$|\mathcal{R}| = A_{1} A_{2} ... A_{|K|} \vec{1}$$
[小結]
"算數"/"計數"是數學的初衷，而遞迴的概念，讓我們能夠有更快計算出答案的可能 !! 而且事實上這些遞迴式的精神不僅使用在計算路徑個數，也可使用在機率計算如 Chapman-Kolmogorov equation 與微積分Chain Rule 梯度更新(gradient update) 如: backpropagation ，詳細日後再寫一篇 !!
[符號定義]
考慮點集 $k \in K = \{1,2,.....|K|\}$ (stages) ，以及每個 stage $k$ 的可能值 $x_k$ 與其空間集 $X_{k}$ (state space) 也就是
$$ \bigwedge_{k \in K}\bigg( x_k \in X_{k} \bigg)$$
另外我們把 $K$ 集定義有序陣列的概念(list,array) !! $K^{<} := [1,2,3,4,....|K|] , K^{>} := [|K|,....,2,1]$
而現實生活中有許多分類的層狀結構，數學上可寫成
$$ \bigwedge_{k \in K^{<}}\bigg(x_k\in \color{red}{X_{k}(x_{k-1})} \bigg)$$
其中 $\color{red}{X_{k}(x_{k-1})} \subseteq X_{k}$ 為 DependSet 的概念，代表給定 $x_{k-1}$ 下，$X_{k}$ 的可能值，這些 $\color{red}{X_{k}(x_{k-1})}$ 是已經被定義的，而且 $X_{1}(\underset{=\emptyset}{x_0}) \equiv X_{1}$
註: 每個 $X_{k}$ 只跟上一層 $x_{k-1}$ 值有關，而與前幾個值 $x_{k-2},x_{k-3}, ...$ 無關，
即類似馬可夫鍊(Markov Chain)相依，而非路徑相依 (Path-dependent)
==================================
舉例: 生物分類的界門綱目科屬種的概念
可以想成 $X_1 = $ 界 ，$X_2(x_1) = $ 門 ，$X_3(x_2) = $ 綱 ....
==================================
[問題定義]
定義
$$\mathcal{R} := X_{1} \times X_{2}(x_1) \times X_3(x_2) .... \times X_{|K|}(x_{|K|-1}) \subseteq \prod_{ k\in K^{<}} X_{k} $$
今天我們要計算 $\mathcal{R}$ 的個數，即 $|\mathcal{R}|$ ，直覺的概念是窮舉法(Brute & Force) ~ 先選定 $x_1 \in X_1$ ，再選定 $x_2 \in X_2(x_1)$ .... 最後選完 $x_{k} \in X_{k}(x_{k-1})$ ，我們把 $x_{K} = (x_1,x_2,....x_{|K|}) $相當於一條路徑，列入 +1 計算，這可利用深度搜尋演算法(DFS)達到，但是當 $|\mathcal{R}|$ 很大的時候就要數很久，甚至數不完，計算效率應該跟 $|\mathcal{R}|$ 一樣多，計算複雜度可寫為 $$\text{complexity } = O\left(\prod_{k \in K} |X_{k}| \right)$$
但事實上在大多數情況下存在簡單易懂，更快的算法 :D
[遞迴公式推導]
如果仔細把 $|\mathcal{R}|$ 寫開會得到
$$ |\mathcal{R}| = \sum_{x_K \in \mathcal{R}} 1 = \sum_{x_1\in X_1} \sum_{x_2 \in X_2(x_1)} \sum_{x_3 \in X_3(x_2)} ....\sum_{x_{|K|-1} \in X_{|K|-1}(x_{|K|-2})}\sum_{x_{|K|} \in X_{|K|}(x_{|K|-1})} 1 $$
注意: 請區分符號定義
$X_k$ (state space of stage $k$)
$x_k$(state value of stage $k$)
$x_{K}$ (vector of state values of all stages $k \in K$)
這時候會發現以下遞迴式跟上面的等價 !!
$$ \bigwedge_{k \in K^{>}} \left[\bigwedge_{x_{k-1} \in X_{k-1}} \bigg( S_{x_{k-1}} := \sum_{x_k \in X_{k}(x_{k-1})} S_{x_k} \bigg) \right]$$
其中 $$\bigwedge_{x_{|K|} \in X_{|K|}} \bigg( S_{x_{|K|}} = 1 \bigg) , S_{x_{0}} \equiv |\mathcal{R}|$$
註: 可以定義 $X_{0} := \{x_0\}$ 為單一虛擬點，彙整所有來自 $X_{1}$的邊 !!
而且會發現遞迴式的本質就是排列組合裡的"加法原理"，而且總共只需要$|K|$次兩層 for 迴圈，外圈掃過 $x_{k-1} \in X_{k-1}$，內圈掃過 $x_{k} \in X_{k}(x_{k-1})$做相加，計算複雜度約為
$$\text{complexity} = O\left(\sum_{k \in K^{<}} |X_{k-1}|\cdot |X_{k}|\right)$$
效率快很多，原因在於有些值已經算好不必每次都鑽到最深層 !! 不過需要多紀錄一些算好的數字，正所謂空間換取時間 !!!
[計算複雜度方程式比較]
如果令 $|K| = 4 $，$a = |X_1|$ , $b = |X_2|$ , $c = |X_3|$ , $d = |X_4|$
則窮舉法類似 $abcd$ ，而優化法類似 $ab+bc+cd$ ，所以在 $a,b,c,d$ 很小的時候不易察覺其差異，甚至可能窮舉法比優化法快，窮舉法需要 "路徑個數"的計算，優化法只需要"邊的個數"計算 !!
[矩陣向量乘法本質]
如果仔細看遞迴式某部分 ~
$$\bigwedge_{x_{k-1} \in X_{k-1}} \bigg( S_{x_{k-1}} := \sum_{x_k \in X_{k}(x_{k-1})} S_{x_k} \bigg)$$
改寫成
$$\bigwedge_{x_{k-1} \in X_{k-1}} \bigg( S_{x_{k-1}} := \sum_{x_k \in X_{k}} \underbrace{\color{blue}{[x_k \in X_{k}(x_{k-1})]}}_{\text{Iverson bracket}} \cdot S_{x_k} \bigg) $$
今把 $(S_{x_{k-1}})_{x_{k-1} \in X_{k-1}}$，$(S_{x_k})_{x_k \in X_k}$ 想成向量們，$\color{blue}{[x_k \in X_{k}(x_{k-1})]}$ 想成 0-1 $|X_{k-1}| \times |X_{k}|$ 鄰接矩陣(adjacency matrix) $A_k := [a_{x_{k-1},x_{k}}] = \color{blue}{[x_k \in X_{k}(x_{k-1})]}$
則我們把原問題可以寫成矩陣的連乘 :D
$$|\mathcal{R}| = A_{1} A_{2} ... A_{|K|} \vec{1}$$
[小結]
"算數"/"計數"是數學的初衷，而遞迴的概念，讓我們能夠有更快計算出答案的可能 !! 而且事實上這些遞迴式的精神不僅使用在計算路徑個數，也可使用在機率計算如 Chapman-Kolmogorov equation 與微積分Chain Rule 梯度更新(gradient update) 如: backpropagation ，詳細日後再寫一篇 !!
[以上純為學術經驗交流知識分享，如有錯誤或建議可留言~~]
by Plus & Minus 2018.07
留言
張貼留言