この記事では、Java Matrix乗算問題（動的プログラミング）アルゴリズムについて説明します。次のように、参照のために共有してください。
問題の説明： nマトリックスを指定：a1、a2、...、an、aiおよびai+1は乗算可能です、i = 1、2 ...、n-1。マトリックス連続積を計算する計算順序を決定し、この順序でマトリックス連続積を計算するために必要な乗算の数が最小になります。入力データは行列の数と各マトリックスのサイズであり、出力結果は計算順序とマトリックスの連続積の乗算の最小数です。
問題分析：マトリックスの乗算は関連の法則を満たすため、マトリックスの連続積を計算するために多くの異なる計算順序があります。この計算順序は、ブラケットを追加することで決定できます。マトリックス連続積の計算の順序が完全に決定される場合、つまり連続積が完全に括弧で囲まれている場合、この順序で2つのマトリックスの乗算の標準アルゴリズムを繰り返し呼び出すことができ、マトリックス連続積を計算できます。
完全に括弧付きのマトリックス製品は、次のように再帰的に定義できます。
（1）単一のマトリックスは完全に括弧で囲まれています。
（2）マトリックス製品Aは完全に括弧で囲まれており、Aは完全に括弧付きの2つのマトリックス製品BとCおよび追加されたブラケットの積として表すことができます。つまり、A =（BC）
たとえば、マトリックス製品A1A2A3A4を完全にブラケットするには、5つの異なる方法があります。完全な括弧の各方法は、マトリックス接続製品の計算順序に対応し、製品の作成に必要な計算量を決定します。
次の例を参照して、3つのマトリックス乗算{a1、a2、a3}を計算します。寸法はそれぞれ10*100、100*5、5 50です。この順序で必要な回数を計算する（（a1*a2）*a3）：10x100x5+10x5x50 = 7500回、この順序で必要な回数を計算します（a1*（a2*a3））：10*5*50+10*100*50 = 75000回
そのため、問題は次のとおりです。計算額を最小限に抑えるために、操作の順序を決定する方法。
アルゴリズムのアイデア：
例：各マトリックスの寸法は次のとおりです。
A1：30*35; A2：35*15; A3：15*5; A4：5*10; A5：10*20; A6：20*25
再帰関係：
設計計算a [i：j]、1≤i≤j≤n、および必要な乗算の最小数[i、j]、元の問題の最適値はm [1、n]です。
i = j、a [i：j] = ai、したがって、m [i] [i] = 0、i = 1,2、…、n
i <jの場合、a [i：j]の最適な順序がakとak+1の間で切断されている場合、i <= k <j、then：m [i] [j] = m [i]+m [k+1] [j]+pi-1pkpj。切断点Kの位置は計算中に知られていないため、Kはまだ決定されていません。ただし、Kの位置にはJIのみが可能です。したがって、KはJIの位置が計算額を最小化する位置です。
要約すると、次のように再帰的な関係があります。
最適なソリューションを構築します。
対応するm [i] [j]の切断位置kがs [i] [j]として示される場合、最適な値m [i] [j]を計算した後、対応する最適解はs [i] [j]から再帰的に構築できます。 s [i] [j]の数は、マトリックスチェーンa [i：j]を計算する最良の方法は、マトリックスAKとAK+1の間で切断する必要があることを示しています。つまり、最適な括弧は（a [i：k]）（a [k+1：j）である必要があります。したがって、s [1] [n]によって記録された情報から、[1：n]を計算するための最適な括弧は（a [1：s [1] [n]]）（a [s [1] [n] +1：n]）であることがわかります。さらに再帰的に、[1：S [1] [s [1] [s [1] [n]]）の最適な括弧は（a [s [1] [s [1] [n]]+1：s [1] [s [1] [s [1] [n]）です。同様に、[s [1] [n] +1：n]の最適な括弧がs [s [1] [n] +1] [n]で壊れていると判断できます。
パッケージマトリックス;パブリッククラスマトリックス{public static void matrixchain（int [] p、int n、int [] [] m、int [] [] s）{for（int i = 1; i <= n; i ++）{m [i] [i] = 0; } for（int r = 2; r <= n; r ++）{for（int i = 1; i <= n-r+1; i ++）{int j = i+r-1; m [i] [j] = m [i + 1] [j] + p [i-1]*p [i]*p [j]; s [i] [j] = i; for（int k = i+1; k <j; k ++）{int t = m [i] [k]+m [k+1] [j]+p [i-1]*p [k]*p [j]; if（t <m [i] [j]）{m [i] [j] = t; s [i] [j] = k; }}}}}} public static void traceback（int i、int j、int [] [] s）{if（i == j）return; traceback（i、s [i] [j]、s）; Traceback（s [i] [j] + 1、j、s）; System.out.println（ "a" + i + "、" + s [i] [j] + "およびa" +（s [i] [j] + 1） + "、" + j）; } public static void main（string [] args）{system.out.println（ "wulin.comテスト結果："）; Matrix MC = new Matrix（）; int n = 7; int p [] = {30、35、15、5、10、20、25}; int m [] [] = new int [n] [n]; int s [] [] = new int [n] [n]; int l = p.length-1; Mc.MatrixChain（P、L、M、S）; for（int i = 1; i <n; i ++）{for（int j = 1; j <n; j ++）{system.out.print（m [i] [j]+"/t"）; } system.out.println（）; } system.out.println（）; for（int i = 1; i <n; i ++）{for（int j = 1; j <n; j ++）{system.out.print（s [i] [j]+""）; } system.out.println（）; } mc.traceback（1、6、s）; }}実行結果：
Javaアルゴリズムの詳細については、このサイトに興味のある読者は、「Javaデータ構造とアルゴリズムのチュートリアル」、「Java操作DOMノードのヒントの要約」、「Javaファイルの要約およびディレクトリ操作のヒント」、「Java Cache操作のヒントの要約」というトピックを見ることができます。
この記事がみんなのJavaプログラミングに役立つことを願っています。