跳到主要內容

Efficient Counting Number Of Paths



本文介紹比較有效率計算路徑個數的演算法，以及一些數學概念的整合

[符號定義]
考慮點集 $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

留言

張貼留言

這個網誌中的熱門文章

Chain Rule & Identity Function Trick

本文為筆者學習微積分，函數概念與Chain Rule 的時候，遇到的一些概念大坑。本文一一澄清一些個人看法，並分享 Chain Rule 廣義的樣子，以及對於遞迴系統該如何計算...等等看法。 [坑1 : 變數/值符號的認識] 一切從 $y = f(x)$ 開始，我們習慣把 Input 變數用"括號"刮起來，Output y 代表值，f 代表函數。或是可以想成這樣:   $$ x \overset{f}{\longrightarrow} y $$ 這種表示法概念上很嚴謹，但缺點是你必須要用三個符號 $x$，$y$，$f$ 而在微分方程領域出現這種寫法 $y = y(x)$  (把 $f$ 換成 $y$) ，這種寫法就頗簡潔，Chain Rule 通常都是這類表示法。缺點是心裡要能確實明白在哪個場合 $y$ 到底是給定的"值"還是"函數"(註: 通常大多代表函數 $y$，值的話通常會這樣寫 $y(x_{0})$,$y_{0}$) ============================================================== [Bonus] $y=y(x)$這種表示法還有一個好處，如果允許 $f$ 是一對多，那麼 $y(x)$ 就是 $y \text{ is depend on } x$ 的意思，如果你喜歡用集合論來表示可以先定義$f$ 的定義域/對應域 $$ f : X \rightarrow Y$$ 然後 $y(x)$ 可以寫成這樣 $y \in Y_{x}$，其中值域為 $$ f(X):=\bigcup_{x \in X}Y_{x} \subseteq Y$$ ============================================================== [坑2 : Input 的變數到底是哪些] 這邊舉兩個例子提醒： (Ex1) 代換法會重新改變函數的 Input 例如 : $y = f(x) = x+1$ , $ z = g(y) = 2y$ 　可以代換一下，寫成 $z = g[f(x)] = 2(x+1)$ 如果你用簡記你會發現　$y(x) , z(y) , z(y(x)) \equiv z...
張貼留言
閱讀完整內容

General Solution Of Eigen System In Linear Algebra

本文從淺白的角度回顧線性代數( Linear Algebra )，了解特徵值( eigenvalue )，特徵向量( eigenvector )，還有特徵多項式( Characteristic Polynomial ) 的框架，並推廣其概念，還有它在解差分方程式，微分方程式，差分方程組，微分方程組的關係。 ----------------------------------------------------------- [預備知識]    向量空間( vector space ) $V$，field over $\mathbb{C}$ ，線性獨立( linear independent )， Span ， Basis 等概念。 線性函數的定義為 $L : V \longrightarrow V$ ， $$\forall \alpha , \beta  \in \mathbb{C} , v_1 ,v_2 \in V \quad L(\alpha v_1 + \beta v_2) =\alpha L(v_1) + \beta L(v_2) $$ 其中 $L(0) = 0 \in V$ 其中 $+$ 都是$V$裡的加法，線性函數空間記做 $L \in \mathcal{L}^{V}$ 其中存在 $O \in \mathcal{L}^{V}$ 零函數 $O(V) = \{0\}$ ，即 $\forall v \in V ,  O(v) = 0 \in V $ 其中存在 $I \in \mathcal{L}^{V}$ 送到自己函數 ，即 $\forall v \in V ,  I(v) = v \in V $ ----------------------------------------------------------- [主要動機] 給定 $b \in V$ ,  $L \in \mathcal{L}^{V}$ 如何解線性系統 $L(x) = b$ ，換句話說就是構造出 $$ S_{b}:= \left\{x \in V : L(x) = b  \right\} $$ ，而 $Ker(L) := S_{0}$ ( Kernel ) 註: 構造出...
張貼留言
閱讀完整內容

All Different Expansion & Bell Numbers

本文分享筆者在計算排列組合(combinatorics)時，發現並描述系統性的窮舉公式 :) 暫時命名為 $\color{red}{\text{All Different Expansion }}$ ??  (有歷史文獻名詞歡迎筆者補充) [情境/動機] 假設箱子裡面有很多種物品，種類集記做 $I$ , 每種物品 $i$ 各有 $\#_i$ 個，向量記做 $\#_{I} := (\#_{i})_{i \in I}$ $$\text{箱子裡共有 } \sum_{i \in I} \#_i  \text{ 個物品}$$    令 $T := \{1,2,3,....|T|\}$，今從箱子裡"逐一"抽取物品共 $|T|$ 次 (抽出 $|T|$ 個物品) ============================================================= $$\color{blue}{\text{形成序列 : } x_{T} := (x_{t})^{|T|}_{t=1} \in I^{|T|}} $$ 註: $x_{t}$ 代表第 $t$ 次抽到的物品 ============================================================= 以下舉個小小的例子，來說明動機~ $I := \{a,b,c,d\}$，$|T| = 4 $，且假設物品個數無上限  $\color{red}{ \forall i \in I \quad \#_{i} = \infty}$ 於是我們可以開始窮舉(brute & force)情況 ~~ $\color{green}{(1)}$  $aaaa$，$bbbb$，$cccc$，$dddd$ 代表全同的情況 $\color{green}{(2)}$  $abcd$，$bcda$，$acbd$，....  代表全異的情況，共 $4!$種 $\color{green}{(3)}$  $abad$，$cbcd$，$bcba$，....  代表二同二異(且$x_{1}=x_{3}$) $\color{green}{(4)...
張貼留言
閱讀完整內容