行列チェーン乗算の問題を研究し、アルゴリズムが何をするかを理解しています。最近、かっこの問題を解くときに重宝するカタロニア語の数字に出くわしました。この問題は、Matrix Chain Multiplication と非常によく似ているように見えました。実際、CLRS では、行列連鎖乗算の章でカタロニア語の数について言及しています。
行列連鎖乗算をカタロニア語のアルゴリズムで解くことができますか? 私の考えは: いいえ、カタロニア語の数字は行列を括弧で囲む方法の数を記述しているため、解決できませんが、元の行列チェーンの問題は別の質問をします-最小のコストを与える括弧を配置する特定の方法.
私の考えは正しいですか？
行列チェーン乗算と括弧の問題は、互いに同等の形式です。1 つを別のものに減らすことができます。
連鎖行列乗算問題
一連のn行列A1, A2, ... Anとその次元p0, p1, p2, ..., pn(ここでi = 1, 2, ..., n、行列のAi次元は ) が与えられた場合pi − 1 × pi、スカラー乗算の数を最小化する乗算の順序を決定します。
同等の形式: 括弧の問題
与えられたn行列 、A1, A2, ... Anここで、 for1 ≤ i ≤ nはAi行列pi − 1 × piであり、単純なアルゴリズムを使用して行列を行列A1, A2, ... Anで乗算するコストがpi − 1× pipi × pi + 1pi − 1× pi × pi + 1
上記の問題の再帰関係を書こうとすると、カタロニア語の数と同じになってしまう。したがって、カタロニア数を使用して行列連鎖乗算の問題を解決できます。