動的プログラミング：サブ問題グラフが非循環グラフではない場合

Question

動的プログラミングでは、副問題グラフは有向非循環グラフ（dag）と見なされますが、副問題グラフにサイクルが含まれているときの解決方法はありますか？例えば部分問題の溶液（A）は部分問題（B）とサブ問題（C）のソリューションに依存し、サブ問題の再度溶液を、（B）が部分問題（A）の溶液に依存します...

Answer 1

この問題は、単にが解決できないです。 Bを解決せずにAを解くことはできず、その逆もありません。 もっと具体的な問題がありますか？多分あなたの分析は間違っていて、部分問題は周期的ではありません。

おそらくdynamic programmingを除いて循環依存関係を解決するcritical stepを解決できるように、サブ問題を分割できます。

Answer 2

場合によっては、関数の値が線形に依存する場合には、問題を軽減して線形方程式を解くことができます。たとえば、それがわかっている場合は

sub(a) = sub(b) + sub(c) 
sub(b) = sub(c) * 2 + 5 
sub(c) = sub(a) - 1 

となり、行列のような線形システムを作ることができます。この場合、それはそう

 a b c value 
eq.1 1 -1 -1  0 
eq.2 0 1 -2  5 
eq.3 -1 0 1  -1 

だろう、あなたは行列AとベクトルCを持っている、とあなたはX = CXな見つけたいです。ベクトルxには、変数の値が順番に格納されます。これは、標準の線形代数アルゴリズム、おそらくガウス変換で行うことができます。