Find The Best Choice By Backward Computation

本文為筆者自行設計圖論演算法解離散不確定決策過程，含動態規劃(Dynamic Programming) 與 Bellman principle of optimality(Bellman Equation) 相關概念，分享其 Idea 框架！！

給定有向圖 $G(N,A)$ ，其中 $N = D \cup R \cup T $，$D,R,T$為互斥的集合，
其中 $i,j \in N$ 代表 State 實作上可以想成 string representation
定義 Forward Set  of $i$ : $F_i$
$$ (i,j) \in A \Longleftrightarrow  j \in F_i $$
其中: $d \in D$ 稱為 Decision Nodes  (決策點集) ，代表該情境決策當下
          $r \in R$ 稱為  Random  Nodes  (隨機點集) ，代表不確定性的開端
          $t \in T$ 稱為  Terminate Nodes (停止點集) ，代表得到報酬或離開
註: $\forall i \in T \quad F_{i} = \emptyset $

定義機率函數(ArcCost) $p : R\times F_r \longrightarrow \mathbb{[0,1]}  \quad p_{ij} \text{ are given }$ 並滿足機率公設

定義累計報酬函數:  $g : N \longrightarrow  \mathbb{R}$
$$ g(i):= \left\{\begin{array}{lll}
\displaystyle{\underset{j\in F_i}{\text{max }}g(j)}&,& \text{if }  i \in D \\
\displaystyle{\sum_{j\in F_i}p_{ij}g(j)} &,& \text{if }  i \in R \\
\text{Initial Value }&,& \text{if }  i \in T \\
 \end{array} \right. $$

定義選擇函數:  $s : D \longrightarrow F_d  $
$$ s(d):=  \underset{j\in F_d}{\text{argmax }}g(j)  $$

給定 $o \in D$ 為當下狀態(Current State)，則$g(o)$ 的值為最大期望報酬，$s$ 為最佳決策!!

演算法虛擬碼 :

+++++++++++++++++++++++++++++++++++++++++++++++++++

Given $g(T)$

Let $Q := T$

For ($i\in N\setminus Q \  \text{ and } \  F_i \subseteq Q$)

$\qquad$ If ($i \in R$) $\quad$  Compute $p(i,F_i)$ 

$\qquad$ If ($i \in D$) $\quad$  Compute $s(i)$ 

$\qquad$ Compute $g(i)$ 

$\qquad$ $Q \leftarrow Q \cup \{i\}$

$\qquad$If ($i == o$)  output $g(o)$ + $s$  and break ;

EndFor

++++++++++++++++++++++++++++++++++++++++++++++++++++

演算法概念:

不斷的搜尋可以計算的點 $i$  (當$F_i$都被算過了已放進$Q$裡)!!

如果遇到隨機點 $i \in R$ 則利用 $F_i$ 把期望值算出來並存起來

如果遇到決策點 $i \in D$ 則選擇 $F_i$ 裡面最好的值當當下決策

計算完 $o$ 點演算法即可停止 !!

實作上關鍵與難題:
$N$的空間複雜度通常很大，如何在不生成$N$的情況下，快速一直找到 $i \notin Q$，而且$F_i \subseteq Q$

[以上純為學術經驗交流知識分享，如有錯誤或建議可留言~~] 

by Plus & Minus 2017.08