Datenstrukturen und Algorithmen - Fragestunde

Aus Infostudium Wiki

Wechseln zu: Navigation, Suche

Optimale Suchbäume

$w_{ij} = \sum_{k=i}^j p_k$

1	2	3	4
$p_1 \ge$	$p_2 \ge$	$p_3 \ge$	$p 4$

$e_{ij} = \begin{cases} 0 & \mbox{if }i > j \\ w_{ij} + min^{(i \le r \le j)} \{e_{i,r-1}+e_{r+1,j}\} & \mbox{if }i \le j \end{cases}$

$w i j$	1	2	3	4
1	$p 1$	$p 1 + p 2$	$p 1 + p 2 + p 3$	$1$
2		$p 2$
3			$p 3$
4	0			$p 4$

$e i j$	1	2	3	4
1	$p 1$	$e 1,2$ $(p 1 + 2 p 2)$	..	..
2		$p 2$
3			$p 3$
4	0			$p 4$

$e 1,2 = w 1,2 + m i n {e 1,2 + e 2,2, e 1,1 + e 3,2}$

$= \ \ \ p_1+p_2 +\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p_2 \ \ \ p_1 \ \ \ \ \ \ \ \ \ \ \ = p_1+2p_2$

$r i j$	1	2	3	4
1	1	1
2		2
3			3
4				4

Von „http://wiki.infostudium.de/wiki/Datenstrukturen_und_Algorithmen_-_Fragestunde“

Kategorie: Datenstrukturen und Algorithmen

Ansichten

Meine Werkzeuge

Anmelden / Benutzerkonto erstellen

Suche

Werkzeuge