行列の鎖の乗法の問題を研究しました。最近、私はカタロニア語の数字に遭遇しました。これはparenthesization problemを解決すると便利です。この問題はMatrix Chain Multiplicationと非常によく似ています。実際、CLRSでは、Matrix Chain Multiplicationの章でカタロニア語の数を述べています。カタロニア数字でマトリックス鎖の突然変異を計算する
カタロニア数字アルゴリズムを使用してマトリックスチェーンの乗算を解くことができますか？私の考えは、カタロニア数は行列をかっこにする方法の数を表しているのに対し、元の行列チェーン問題は最小のコストを与える括弧を配置する別の質問固有の方法を求めているからです。
私の考えは正しいですか？
マトリックスチェーンの乗算と括弧内の問題は、お互いの平等な形です。 1つを別のものに減らすことができます。
チェーンマトリクス乗算問題
i = 1, 2, ..., n
n行列A1, A2, ... An、及びそれらの寸法p0, p1, p2, ..., pnのシーケンスが与えられると、行列Aiは寸法pi − 1 × piを持つ、スカラーの数を最小限に乗算の順序を決定します乗算。
等価形態：カッコ問題
は1 ≤ i ≤ nため、Aiはpi − 1 × pi、行列でn行列、A1, A2, ... Anを考えると、総コストを最小にするように製品A1, A2, ... Anを括弧、コストが乗算と仮定は、単純なアルゴリズムを使用してpi × pi + 1行列によるpi − 1× pi行列です。pi − 1× pi × pi + 1
上記の問題の反復関係を書こうとすると、tuカタロニア語の数と同じになる。したがって、カタラン数は、行列チェーンの乗算の問題を解決するために使用できます。