###### tags: `ML數學分部`
# Template Matching & Bellman's Optimality Priciple

:::info
- **問題介紹**
當今天有兩序列資料 "test pattern"、"Template" 要做對照比較
並找出其相似的最小路徑，會計算 node 和 node 之間的資料"距離"，並進行優化

**Distance 定義** :
$$d(i_k,j_k\ |\ i_{k-1},j_{k-1})$$
**總和 Distance 定義**
$$D=\sum{d(i_k,j_k\ |\ i_{k-1},j_{k-1})}$$

<br>


- **符號簡介**
I : Template 序列長度
J : test pattern 序列長度
k : node 數量

:::

:::warning

**Bellman's Optimality Priciple**

是優化 Distance D 的方法

$D_{min}(i_k,j_k)=min[\ D_{min}(i_{k-1},j_{k-1}) \ | \ d(i_k,j_k\ |\ i_{k-1},j_{k-1}) \ ]$

- $D_{min}(i_{k-1},j_{k-1})$ : 到 $(i_{k-1},j_{k-1})$ 總和的 Distance ( Cost )
- $d(i_k,j_k\ |\ i_{k-1},j_{k-1})$ : $(i_{k-1},j_{k-1})$ 到 $(i_{k},j_{k})$ 之間的 Cost

<br>

- 備註 : min 是適用於此狀況的優化，可能會因為優化的情況不同而有所改變 
ex : 馬可夫鍊的優化

:::