Kurs Algorithmenkonstruktion: Modul 32

8. Dynamische Programmierung

Dynamische Programmierung - Technik zur Algorithmenkonstruktion
,,Programmierung``: Tabellenverfahren
Um ein Problem der Größe n zu lösen, werden alle zugehörigen Teilprobleme der Größen 1, 2,..., n - 1 gelöst und diese Teillösungen in Tabellenform gespeichert. Eine nächstgrößere Teillösung wird dann aus diesen Teillösungen (die einander auch überlappen können) mit Tabellenzugriff aufgebaut.
Typische Anwendungsfelder der dynamischen Programmierung sind Optimierungsprobleme (Minimum oder Maximum). Voraussetzung für die Anwendung ist dann, daß die (eine) optimale Lösung eines Problems der Größe n aus optimalen Teillösungen der Größe < n zusammengesetzt werden kann (Bellmannsches Optimierungsprinzip).

Literatur

[ 1]	R. Sedgewick. Algorithmen. Bonn, München, ... 1992
[ 2]	G. Brassard, P. Bratley. Algorithmik: Theorie und Praxis. Attenkirchen 1993
[ 3]	T.H. Cormen, C.E. Leiserson, R.L. Rivest. Introduction to Algorithms. Cambridge, London 1997
[ 4]	U. Schöning. Algorithmen - kurz gefaßt. Heidelberg, Berlin 1997
[ 5]	M. Sniedovich. Dynamic Programming. New York 1992
[ 6]	B. Soucek. Dynamic, Genetic, and Chaotic Programming: The Sixth-Generation (Sixth-Generation Computer Technology Series). New York 1992
[ 7]	A.E. Bryson. Dynamic Optimization. Reading 1998
[ 8]	G. Cole. Dynamic Programming Bibliography. http://www.maths.mu.oz.au/~moshe/dp/bibl/bibliography.html

8.1 Produkt mehrerer Matrizen (Matrix chain product)

n Matrizen sollen miteinander multipliziert werden:

$\epsfbox{modul30_abschn8_1.ps}$
$\underline{M}_{1}^{}$ - p₀ x p₁ - Matrix (p₀ Zeilen, p₁Spalten)
$\underline{M}_{2}^{}$ - p₁ x p₂ - Matrix (p₁ Zeilen, p₂Spalten)
$\underline{M}_{3}^{}$ - p₂ x p₃ - Matrix
$\vdots$
$\underline{M}_{n}^{}$ - p_{n - 1} x p_n - Matrix.

Die Matrizenmultiplikation ist assoziativ, die vorstehenden Matrizen können also beliebig geklammert (und damit entsprechende Teilprodukte zum Gesamtprodukt zusammengefaßt) werden.

Gegeben:

Größen der Matrizen $\underline{M}_{1}^{}$ , $\underline{M}_{2}^{}$ , $\underline{M}_{3}^{}$ ,..., $\underline{M}_{n}^{}$
p[0..n] = (p₀, p₁, p₂,..., p_n)

Gesucht:

Klammerung der Matrizen so, daß bei der Ausführung der Matrizenmultiplikationen möglichst wenig Skalarmultiplikationen erforderlich sind (Minimierung des Rechenaufwandes).
Minimale Anzahl der Skalarmultiplikationen m[1, n].

Vorbetrachtung:

$\epsfbox{modul30_abschn8_2.ps}$

Zur Berechnung von $\underline{C}$ aus $\underline{A}$ und $\underline{B}$ sind l^.n^.m Skalarmultiplikationen erforderlich.
n = 3
$\epsfbox{modul30_abschn8_11.ps}$
mit p₀ = 100, p₁ = 50, p₂ = 10, p₃ = 5 .
Zwei Klammerungsmöglichkeiten:
$\epsfbox{modul30_abschn8_12.ps}$
Unterschiedliche Klammerung $\longrightarrow$ stark unterschiedliche Anzahl von Skalarmultiplikationen ( $\widehat{=}$ Laufzeit); die Minimierung lohnt sich also!
n = 4
$\epsfbox{modul30_abschn8_13.ps}$
mit p₀ = 13, p₁ = 5, p₂ = 89, p₃ = 3, p₄ = 34 [4].
Für n = 4 existieren 5 Klammerungsmöglichkeiten (äußerste Klammerung hervorgehoben):
$\epsfbox{modul30_abschn8_14.ps}$
Die betrachteten Fälle n = 2, 3 und 4 werden nun in einer Tabelle zusammengefaßt:
Tabelle 1, Zeile 1 (doppelt eingerahmt).
Die in Tabelle 1 erfolgte Hinzunahme der mit 0 belegten Hauptdiagonale sowie der Zeilen 2, 3 und 4 zeigt, wie sich m[1, 4] auch rekursiv aus den schon bestimmten ,,Teillösungen`` m[1, 1], m[1, 2] und m[1, 3] (Zeile 1) sowie m[2, 4], n[3, 4] und m[4, 4] (Spalte 4) berechnen läßt.
Mittels der daraus vermuteten allgemeinen Rekursionsformel
m[i, j] = m[i, k] + m[k + 1, j] + p_{j - 1}p_kp_j
gewinnt man nun auch
- m[1, 3] aus den bereits vorliegenden Teillösungen m[1, 1] und m[1, 2] (Zeile 1) sowie m[2, 3] und m[3, 3] (Spalte 3) und
- m[2, 4] aus den bereits vorliegenden Teillösungen m[2, 2] und m[2, 3] (Zeile 2) sowie m[3, 4] und m[4, 4] (Spalte 4):
m[1, 3] = m[1, k] + m[k + 1, 3] + p₀p_kp₃
m[2, 4] = m[2, k] + m[3, 4] + p₁p_kp₄ ;
die Rekursionsformel ist also richtig für 1i4, i + 2j Verifikation für beliebige n.
Es liegt hier ein typischer Anwendungsfall der dynamischen Programmierung vor; der Aufbau der nächstgrößeren Teillösungen aus bereits bestimmten darunterliegenden Teillösungen erfolgt gemäß Tabelle 1 hauptdiagonalparallel aufsteigend.

$\epsfbox{modul30_abschn8_15.ps}$

Tabelle 1:

Zusammenfassung der Berechnung von m[1, 2], m[1, 3] und m[1, 4];
Hinzunahme von m[1, 1] = m[2, 2] = m[3, 3] = m[4, 4] = 0
und Hinzunahme von m[2, 3], m[2, 4] und m[3, 4]

$\fbox{\fbox{\parbox{15.2cm}{\small \begin{center}$m[1,4]=$\space \end{center}$(p... ...,k]+m[k+1,j]+p_{i-1}p_kp_j \right)$\\ [0.4cm] \epsfbox{modul30_abschn8_16.ps}}}}$

Tabelle 1:

Fenster m[1, 4]

Lösung:

m[i, j] -	minimale Anzahl von Skalarmultiplikationen für die Berechnung des Teilproduktes $\underline{M}_{i}^{}$ ... $\underline{M}_{j}^{}$
m[1, n] -	gesuchte minimale Anzahl von Skalarmultiplikationen für die Berechnung von $\underline{M}_{1}^{}$ $\underline{M}_{2}^{}$ $\underline{M}_{3}^{}$ ... $\underline{M}_{n}^{}$

Rekursionsgleichung:

m[i, j]	=	$\displaystyle \min_{k=i}^{j-1}$ $\displaystyle \left(\vphantom{m[i,k]+m[k+1,j]+p_{i-1}p_kp_j}\right.$ m[i, k] + m[k + 1, j] + p_{i - 1}p_kp_j $\displaystyle \left.\vphantom{m[i,k]+m[k+1,j]+p_{i-1}p_kp_j}\right)$ ; $\displaystyle {1\le i\le n \atop i+2\le j}$
		$\displaystyle \downarrow$
		k_min[i, j] = l[i, j] $\displaystyle \widehat{=}$ Position des äußersten Klammerungspaares bei
		optimaler Klammerung $\displaystyle \Big($ $\displaystyle \underline{M}_{i}^{}$ ... $\displaystyle \underline{M}_{l}^{}$ $\displaystyle \Big)$ $\displaystyle \Big($ $\displaystyle \underline{M}_{l+1}^{}$ ... $\displaystyle \underline{M}_{j}^{}$ $\displaystyle \Big)$

Initialisierungen:
m[i, i] = 0 ; 1 $\le$ i $\le$ n
m[i, i + 1] = p_{i - 1}p_ip_{i + 1} ; 1 $\le$ i $\le$ n - 1
Sequentieller Aufbau der Lösung m[1, n]:

$\mbox{$\bullet$}$

Berechnung der nächsthöheren Teillösungen (liegen auf der zweiten Parallelen der Hauptdiagonale)

m[i, i + 2]	=	$\displaystyle \min_{k=i}^{i+1}$ $\displaystyle \left(\vphantom{m[i,k]+m[k+1,i+2]+p_{i-1}p_kp_{i+2}}\right.$ m[i, k] + m[k + 1, i + 2] + p_{i - 1}p_kp_{i + 2} $\displaystyle \left.\vphantom{m[i,k]+m[k+1,i+2]+p_{i-1}p_kp_{i+2}}\right)$
	=	$\displaystyle \left(\vphantom{m[i,i]+m[i+1,i+2]+p_{i-1}p_ip_{i+2}}\right.$ m[i, i] + m[i + 1, i + 2] + p_{i - 1}p_ip_{i + 2} $\displaystyle \left.\vphantom{m[i,i]+m[i+1,i+2]+p_{i-1}p_ip_{i+2}}\right)$ $\displaystyle \perp$
		$\displaystyle \left(\vphantom{m[i,i+1]+m[i+2,i+2]+p_{i-1}p_{i+1}p_{i+2}}\right.$ m[i, i + 1] + m[i + 2, i + 2] + p_{i - 1}p_{i + 1}p_{i + 2} $\displaystyle \left.\vphantom{m[i,i+1]+m[i+2,i+2]+p_{i-1}p_{i+1}p_{i+2}}\right)$ ; 1 $\displaystyle \le$ i $\displaystyle \le$ n - 2

aus den darunterliegenden Teillösungen (Initialisierungen) m[i, i], m[i + 1, i + 2], m[i, i + 1] und m[i + 2, i + 2].

$\mbox{$\bullet$}$

Berechnung der nächsthöheren Teillösungen (liegen auf der nächsthöheren Parallelen der Hauptdiagonale)

m[i, i + 3]	=	$\displaystyle \min_{k=i}^{i+2}$ $\displaystyle \left(\vphantom{m[i,k]+m[k+1,i+3]+p_{i-1}p_kp_{i+3}}\right.$ m[i, k] + m[k + 1, i + 3] + p_{i - 1}p_kp_{i + 3} $\displaystyle \left.\vphantom{m[i,k]+m[k+1,i+3]+p_{i-1}p_kp_{i+3}}\right)$
	=	$\displaystyle \left(\vphantom{m[i,i]+m[i+1,i+3]+p_{i-1}p_ip_{i+3}}\right.$ m[i, i] + m[i + 1, i + 3] + p_{i - 1}p_ip_{i + 3} $\displaystyle \left.\vphantom{m[i,i]+m[i+1,i+3]+p_{i-1}p_ip_{i+3}}\right)$ $\displaystyle \perp$
		$\displaystyle \left(\vphantom{m[i,i+1]+m[i+2,i+3]+p_{i-1}p_{i+1}p_{i+3}}\right.$ m[i, i + 1] + m[i + 2, i + 3] + p_{i - 1}p_{i + 1}p_{i + 3} $\displaystyle \left.\vphantom{m[i,i+1]+m[i+2,i+3]+p_{i-1}p_{i+1}p_{i+3}}\right)$ $\displaystyle \perp$
		$\displaystyle \left(\vphantom{m[i,i+2]+m[i+3,i+3]+p_{i-1}p_{i+2}p_{i+3}}\right.$ m[i, i + 2] + m[i + 3, i + 3] + p_{i - 1}p_{i + 2}p_{i + 3} $\displaystyle \left.\vphantom{m[i,i+2]+m[i+3,i+3]+p_{i-1}p_{i+2}p_{i+3}}\right)$ ; 1 $\displaystyle \le$ i $\displaystyle \le$ n - 3

aus den darunterliegenden Teillösungen m[i, i], m[i + 1, i + 3], m[i, i + 1], m[i + 2, i + 3] m[i, i + 2] und m[i + 3, i + 3].

$\vdots$

$\mbox{$\bullet$}$

Berechnung der Lösung
m[1, n] = $\min\limits_{k=1}^{n-1}$ $\left(\vphantom{m[1,k]+m[k+1,n]+p_0p_kp_n}\right.$ m[1, k] + m[k + 1, n] + p₀p_kp_n $\left.\vphantom{m[1,k]+m[k+1,n]+p_0p_kp_n}\right)$
aus den darunterliegenden Teillösungen m[1, k] und m[k + 1, n] ; k = 1, 2,..., n - 1.

Die rekursive Berechnung von m[1, n] gemäß vorstehendem Algorithmus schließt die vorherige Berechnung aller Teillösungen m[i, j] aus den Initialisierungen m[i, i] und m[i, i + 1] ein. Sie erfolgt zweckmäßigerweise unter Benutzung der folgenden Arbeitstabelle (Tabelle 2, n = 6).

$\epsfbox{modul30_abschn8_17.ps}$

Tabelle 2: Arbeitstabelle zur Berechnung von m[1, n] für n = 6
Initialisierungen und Berechnungsreihenfolge (hauptdiagonalparallel aufsteigend) für die Teillösungen sind eingetragen

Für das in [3] untersuchte Beispiel p[0..6] = (30, 35, 15, 5, 10, 20, 25)hat man dann die Arbeitstabelle m[i, j]: Tabelle 3.

$\epsfbox{modul30_abschn8_7.ps}$
Berechnung von m[2, 5]:

m[2, 5] = $\min\limits_{k=2}^{4}$ $\left\{\vphantom{ \begin{array}{l} m[2,2]+m[3,5]+p_1p_2p_5=13000\\ [0.2cm] m[... ...,5]+p_1p_3p_5=7125\\ [0.2cm] m[2,4]+m[5,5]+p_1p_4p_5=11375 \end{array}}\right.$ $\begin{array}{l} m[2,2]+m[3,5]+p_1p_2p_5=13000\\ [0.2cm] m[2,3]+m[4,5]+p_1p_3p_5=7125\\ [0.2cm] m[2,4]+m[5,5]+p_1p_4p_5=11375 \end{array}$ $\left.\vphantom{ \begin{array}{l} m[2,2]+m[3,5]+p_1p_2p_5=13000\\ [0.2cm] m[2... ...5]+p_1p_3p_5=7125\\ [0.2cm] m[2,4]+m[5,5]+p_1p_4p_5=11375 \end{array}}\right\}$ = 7125
$\longrightarrow$ k_min[2, 5] = l[2, 5] = 3 .

Zur Berechnung von $\underline{\underline{m[1,6]=15125}}$ müssen alle anderen m[i, j] vorliegen.
Tabelle 3: Arbeitstabelle m[i, j] für p[0..6] = (30, 35, 15, 5, 10, 20, 25)

Aus der parallel mit der Arbeitstabelle m[i, j] aufzubauenden Arbeitstabelle l[i, j] kann dann die gesuchte Klammerung bestimmt werden. Für das betrachtete Beispiel aus [3] erhält man die Arbeitstabelle l[i, j]: Tabelle 4.
$\epsfbox{modul30_abschn8_8.ps}$
Tabelle 4: Zugehörige Arbeitstabelle l[i, j]

Daraus ergibt sich die gesuchte Klammerung:

$\left.\vphantom{\begin{array}{lll} l[1,6]=3&\longrightarrow&(\underline{M}_1\l... ...grightarrow&(\underline{M}_4\underline{M}_5)\underline{M}_6 \end{array}}\right.$ $\begin{array}{lll} l[1,6]=3&\longrightarrow&(\underline{M}_1\ldots \underline{... ...]=5&\longrightarrow&(\underline{M}_4\underline{M}_5)\underline{M}_6 \end{array}$ $\left.\vphantom{\begin{array}{lll} l[1,6]=3&\longrightarrow&(\underline{M}_1\l... ...rightarrow&(\underline{M}_4\underline{M}_5)\underline{M}_6 \end{array}}\right\}$ $\longrightarrow$ $\epsfbox{modul30_abschn8_29.ps}$

Aufgabe 1:

Notieren Sie die hier verbal vorgestellten Algorithmen zur Berechnung von m[1, n] und zur Bestimmung der optimalen Klammerung jeweils als Struktogramm.

Aufgabe 2:

Ist die in Tabelle 1 benutzte Berechnungsreihenfolge die einzig mögliche?

Aufgabe 3:

Transformieren Sie das vorliegende Problem in das Problem ,, Optimale Binärkodierung`` (Abschn. 5.5 bzw. DACModul 30) und lösen Sie es damit via Huffman-Algorithmus.

Aufgabe 4:

Die Zeitkomplexität des vorliegenden Algorithmus zur Berechnung von m[1, n] ist O(n³). Suchen Sie nach Möglichkeiten zur Effizienzverbesserung mit dem Ziel O(n²) bzw. O(nlog n).

Lesen Sie zur Bearbeitung der Aufgaben

[ 9] S. Godboke. On efficient computation of matrix chain products. IEEE Transactions on Computers C22(1973)9, 864-866
[10] T.C. Hu, M.R. Shing. Computations of matrix chain products.
Part I. SIAM Journal on Computing 11(1982)2, 362-373
Part II. SIAM Journal on Computing 13(1984)2, 228-251
[11] I. Wegener. Effiziente Algorithmen für grundlegende Funktionen. Stuttgart 1989
[12] A. Czumaj. Very Fast Approximation of the Matrix Chain Product Problem. Journal of Algorithms 21(1996)1, 71-79
sowie [2], Abschn. 5.3 und [3], Abschn. 16.1.

1 | 2 | 3
Die Module

[ 9]	S. Godboke. On efficient computation of matrix chain products. IEEE Transactions on Computers C22(1973)9, 864-866
[10]	T.C. Hu, M.R. Shing. Computations of matrix chain products. Part I. SIAM Journal on Computing 11(1982)2, 362-373 Part II. SIAM Journal on Computing 13(1984)2, 228-251
[11]	I. Wegener. Effiziente Algorithmen für grundlegende Funktionen. Stuttgart 1989
[12]	A. Czumaj. Very Fast Approximation of the Matrix Chain Product Problem. Journal of Algorithms 21(1996)1, 71-79