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.

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. Schrijf hiervoor een Python-functie minimumVermenigvuldigingen(matrix: list).

Voorbeeld

>>> minimumVermenigvuldigingen([('A', 50, 10), ('B', 10, 40), ('C', 40, 30), ('D', 30, 5)])
('A', ('B', ('C', 'D')))
>>> minimumVermenigvuldigingen([('A', 10, 10), ('B', 10, 20), ('C', 20, 2), ('D', 2, 30), ('E', 30, 10)])
(('A', ('B', 'C')), ('D', 'E'))
>>> minimumVermenigvuldigingen([('A', 1, 10), ('B', 10, 20), ('C', 20, 1)])
('A', ('B', 'C'))
>>> minimumVermenigvuldigingen([('A', 210, 210)])
'A'