Zij gegeven \(n\) matrices \(A_i\), \(i = 0,...,n-1\), met consistente dimensies zodat het matrixproduct \(A_0 A_1 \cdots A_{n-1}\) kan berekend worden. Matrixvermenigvuldiging is niet commutatief maar wel associatief. Het matrixproduct kan dus in willekeurige volgorde geëvalueerd worden. De standaardmanier om twee matrices met dimensies \(p \times q\) en \(q \times r\) respectievelijk te vermenigvuldigen, gebruikt \(pqr\) scalaire vermenigvuldigingen.

Voorbeeld

Neem vier matrices \(A\), \(B\), \(C\) en \(D\) met dimensies \(50 \times 10\), \(10 \times 40\), \(40 \times 30\) en \(30 \times 5\), respectievelijk.

Wanneer we \(ABCD\) evalueren als \(A((BC)D)\), zijn er in totaal \(16000\) scalaire vermenigvuldigingen nodig. Immers, het evalueren van \(BC\) vereist \(10 \cdot 40 \cdot 30 = 12000\) vermenigvuldigingen. Het evalueren van \((BC)D\) vereist de \(12000\) vermenigvuldigingen om \(BC\) te berekenen, plus een bijkomende \(10 \cdot 30 \cdot 5 = 1500\), dus in totaal \(13500\) vermenigvuldigingen. Het evalueren van \(A((BC)D)\) vraagt de \(13500\) vermenigvuldigingen voor het berekenen van \((BC)D\) plus bijkomend \(50 \cdot 10 \cdot 5 = 2500\). Het totaal aantal vereiste vermenigvuldigingen voor deze berekening is dus \(16000\).

Evalueren we echter \(ABCD\) als \(A(B(CD))\), dan zijn slechts \(10500\) scalaire vermenigvuldigingen nodig. Dit is de meest efficiënte manier om deze vier matrices te vermenigvuldigen.

Opgave

Ontwerp en implementeer een algoritme volgens de techniek van dynamisch programmeren dat een volgorde van vermenigvuldigen bepaalt om \(A_0 A_1 \cdots A_{n-1}\) te evalueren zodat het aantal vereiste scalaire vermenigvuldigingen minimaal is. Implementeer hiervoor de gegeven interface MatrixOrdening¹ in een klasse DynamischeMatrixOrdening, die een methode public MatrixVermenigvuldiging minimumVermenigvuldigingen(List<Matrix> matrices) bevat. De input van deze methode is een lijst met objecten van de klasse Matrix², die een naam en de dimensies van een matrix bijhoudt. Als output geeft deze methode een object van de klasse MatrixVermenigvuldiging³ terug. Zo’n object bevat ofwel een matrix, of anders twee andere MatrixVermenigvuldiging objecten. De volgorde van vermenigvuldigen is dan om eerst deze twee vermenigvuldigingen uit te werken volgens de daarin aangegeven volgorde, en vervolgens de twee resulterende matrices te vermenigvuldigen. De oplossing van het voorbeeld is dus:

new MatrixVermenigvuldiging(
  new MatrixVermenigvuldiging(A),
  new MatrixVermenigvuldiging(
    new MatrixVermenigvuldiging(B),
    new MatrixVermenigvuldiging(
      new MatrixVermenigvuldiging(C),
      new MatrixVermenigvuldiging(D)
    )
  )
)

Gebruik eventueel de testklasse SimpleTest⁴ om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.