両帰式 (動的計画法における)

【りょうきしき (bicursive formula) 】

動的計画法における単調性 (monotonicity) は目的関数の「非減少性」を意味している. これを「非減少性または非増加性のいずれか」と広義に解釈した両調性 (bitonicity) の下で, 所与の「最大化問題」を解くには, 部分最大問題群ばかりでなく部分最小問題群をも考える必要がある. このとき, 最大値関数と最小値関数の間に成り立つ連立再帰式を両帰式という. 利得関数が負値にもなる乗法型評価関数などの最適化は両帰式で解ける.