Algorithmen und Datenstrukturen

vi
visual inference

[Link] Roth, SS 2025

07
Fortgeschrittene
Algorithmen-Entwurfsmethoden

Folien beruhen auf der Veranstaltung von Prof. Marc Fischlin und Christian Janson aus dem SS 2024

13. Oktober 2010 | [Link] Fischlin | Kryptosicherheit | 1

Auswahl Algorithmischer Entwurfsmethoden

Divide & Conquer Backtracking

Löse rekursiv durchsuche iterativ
(disjunkte) Teilprobleme Lösungsraum

(Quicksort, Mergesort)

Dynamisches Greedy
Programmieren
Löse rekursiv baue Lösung aus Folge
(überlappende) Teilprobleme lokal bester Auswahlen zusammen
durch Wiederverwenden
(Kruskal, Prim, Dijkstra)

+Metaheuristiken: übergeordnete Methoden für Optimierungsprobleme

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 2
vi
 Divide & Conquer

(Fast Fourier Transformation, FFT)

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 3
vi
Idee der Fourier-Transformation Beispiel:
Polynommultiplikation

Beispiel:
Beispiel: FFT und inverse FFT Beispiel:
𝑇 = Ω(𝑛! ) in Zeit 𝑂(𝑛 log 𝑛) in Zeit 𝑂(𝑛)
per Divide & Conquer

Problem in Transformiere in Zeit ≪ 𝑇 Problem in

Darstellung X Darstellung Y

Löse in Zeit T Gesamtzeit ≪ 𝑇 Löse in Zeit ≪ 𝑇

Transformiere
Lösung in in Zeit ≪ 𝑇 zurück Lösung in
Darstellung X Darstellung Y
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 4
vi
 Bilder erstellt mit [Link]

Polynom: Koeffizientendarstellung (I)

! ! ! " ' # !
"##$ %&"#$ %!($ %&$)'
𝑝 𝑥 = 𝑝! + 𝑝" 𝑥 + 𝑝# 𝑥# + ⋯ + 𝑝$%# 𝑥 $%# + 𝑝$%" 𝑥 $%"
mit 𝑝"#$ ≠ 0 und 𝑔𝑟𝑎𝑑 𝑝 𝑥 =𝑛−1

Gegeben beispielsweise als Array p[] der Koeffizienten p[i]

(Annahme im Folgenden: p[i]=0 für i>=n)

Schnelle Auswertung an Stelle w bei Koeffizientendarstellung (Horner-Methode):

𝑝 𝑥 = ( 𝑝$%" 𝑥 + 𝑝$%# 𝑥 + 𝑝$%& 𝑥 + ⋯ 𝑝" )𝑥 + 𝑝!

PolyEval(p,n,w) // p[] array of n entries

1 y=p[n-1];
2 FOR i=n-2 DOWNTO 0 DO y=y*w+p[i];
Laufzeit Θ(𝑛)
3 return y;

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 5
vi
 Bilder erstellt mit [Link]

Polynom: Koeffizientendarstellung (II)

! ! ! " ' # !
"##$ %&"#$ %!($ %&$)'

Multiplikation zweier Polynome 𝑝(𝑥), 𝑞(𝑥), beide vom Grad 𝑛 − 1

𝑝 𝑥 * 𝑞(𝑥) = ∑$%" ' $%"

'(! 𝑝' 𝑥 * ∑'(! 𝑞' 𝑥
' vom Grad 2𝑛 − 2
!"#! %
=9 9 𝑝( : 𝑞%#( 𝑥 % Faltung / „Konvolution“
%&' (&' der Koeffizienten

Geht das schneller?

PolyMult(p,q,n) // p,q arrays of n entries

1 r=ALLOC(2n-1); Laufzeit
#$%#
2 FOR k=0 TO 2n-2 DO Θ Σ)(! 𝑘 = Θ(𝑛# )
3 r[k]=0;
4 FOR j=0 TO k DO r[k]=r[k]+p[j]*q[k-j];
5 return r;

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 6
vi
 Bilder erstellt mit [Link]

Fourier-Transformation (I)DFT=(Inverse) Diskrete Fourier-Transformation

(I)FFT=(Inverse) Fast Fourier Transformation

„Transformiere in
geeignetere Darstellung,
! ! ! " ' # !
"##$ %&"#$ %!($ %&$)' rechne dort
und transformiere zurück“

Multiplikation von 𝑝 𝑥 , 𝑞(𝑥) DFT Darstellung von 𝑝 𝑥 , 𝑞(𝑥)

vom Grad 𝑛 − 1 vom Grad 𝑛 − 1
in Koeffizientendarstellung in Zeit Θ 𝑛 log 𝑛 in Punkt/Wert-Darstellung
per FFT
per Faltung
Gesamtzeit Θ(𝑛 log 𝑛) in Zeit Θ(𝑛)
in Zeit Θ(𝑛! )

in Zeit Θ 𝑛 log 𝑛
𝑟 𝑥 = 𝑝 𝑥 : 𝑞(𝑥) per IFFT 𝑟 𝑥 = 𝑝 𝑥 : 𝑞(𝑥)
vom Grad 2𝑛 − 2 vom Grad 2𝑛 − 2
in Koeffizientendarstellung IDFT in Punkt/Wert-Darstellung
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 7
vi
 Bilder erstellt mit [Link]

Polynome: Punkt/Wert-Darstellung (I)

𝑝 𝑥 = 𝑝! + 𝑝" 𝑥 + 𝑝# 𝑥 # + ⋯ + 𝑝$%# 𝑥 $%# + 𝑝$%" 𝑥 $%"
mit 𝑝"#$ ≠ 0 und 𝑔𝑟𝑎𝑑 𝑝 𝑥 =𝑛−1

Gegeben z.B. als Array p[] der Punkte/Werte p[i].x, p[i].y

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 8
vi
 Exkurs

Eindeutigkeit der Punkt/Wert-Darstellung (I)

Jedes Polynom 𝑝(𝑥) über Körper vom Grad ≤ 𝑛 − 1 lässt sich eindeutig
durch 𝑛 Punkt/Wert-Paare (𝑥* , 𝑦* )*(!,…,$%" für verschiedene 𝑥* durch
𝑦* = 𝑝 𝑥* beschreiben.

Zu (𝑥( , 𝑦( )(&',…,"#$ betrachte lineares Gleichungssystem in Variablen 𝑝' , 𝑝$ , … , 𝑝"#$ :

𝑝 𝑥' = 𝑝' + 𝑝$ 𝑥' + 𝑝! 𝑥'! + ⋯ + 𝑝"#$ 𝑥'"#$ = 𝑦'

𝑝 𝑥$ = 𝑝' + 𝑝$ 𝑥$ + 𝑝! 𝑥$! + ⋯ + 𝑝"#$ 𝑥$"#$ = 𝑦$
⋮
! "#$
𝑝 𝑥"#$ = 𝑝' + 𝑝$ 𝑥"#$ + 𝑝! 𝑥"#$ + ⋯ + 𝑝"#$ 𝑥"#$ = 𝑦"#$

In Matrixform:
⋯ 𝑥'"#$ 𝑝' 𝑦' Vandermonde-Matrix 𝑉 𝑥' , … , 𝑥"#$ mit
1 𝑥'
1 𝑥$ 𝑝$ 𝑦$ det 𝑉 𝑥' , … , 𝑥"#$ = ∏'+,-(+"#$(𝑥( − 𝑥, )
⋯ 𝑥$"#$
⋮ = ⋮
⋮ ⋱
1 𝑥"#$ "#$
⋯ 𝑥"#$ 𝑝"#$ 𝑦"#$ det 𝑉 𝑥' , … , 𝑥"#$ ≠ 0 für verschiedene 𝑥( ,
also eindeutige Lösung 𝑝' , 𝑝$ , … , 𝑝"#$
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 9
vi
 Bilder erstellt mit [Link]

Polynome: Punkt/Wert-Darstellung (II)

Ziel: berechne Produkt 𝑟 𝑥 = 𝒑(𝒙) : 𝒒(𝒙)

Polynom-Multiplikation in Punkt/Wert-Darstellung einfach

(sofern gleiche x-Koordinaten 𝑥' , 𝑥$ , 𝑥! , … für 𝑝 und 𝑞):

𝑟 𝑥( = 𝒑(𝒙𝒋 ) : 𝒒(𝒙𝒋 ) für alle 𝑗 = 0,1, … , 2𝑛 − 2

benötigen 2𝑛 − 1 Paare
(damit auch schon für 𝑝, 𝑞,
da 𝑟 vom Grad 2𝑛 − 2)

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 10
vi
 Bilder erstellt mit [Link]

Polynome: Punkt/Wert-Darstellung (III)

𝟏 𝟒 𝟏 𝟑 𝟓 𝟐 𝟏
𝒑 𝒙 = 𝟒𝟎𝟎 𝒙 #𝟐𝟒𝟎𝒙 #𝟏𝟔𝒙 #𝟐𝒙 + 𝟓 FFT
𝟏 𝟏 𝟐 𝟏 (2𝑛 − 1 Werte)
𝒒 𝒙 = 𝟏𝟎𝟎𝟎𝟎 𝒙𝟒 + 𝟏𝟎𝟎 𝒙 − 𝟏𝟎 𝒙 + 𝟎, 𝟓

PolyMult(p,q,n)
// p,q arrays of 2n-1 entries x,y
// p[i].x=q[i].x for all i
1 r=ALLOC(2n-1);
2 FOR i=0 TO 2n-2 DO
3 r[i].x = p[i].x;
4 r[i].y = p[i].y * q[i].y;
5 return r;
Laufzeit Θ(𝑛)

$
𝑟 𝑥 = %&&&&&&𝑥 6 +…
IFFT
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 11
vi
 Bilder erstellt mit [Link]

Diskrete Fourier-Transformation berechnen (I)

! ! ! " ' # !
"##$ %&"#$ %!($ %&$)'

𝑝 𝑥 = 𝑝' + 𝑝$ 𝑥 + ⋯ + 𝑝"#$ 𝑥 "#$ 𝐷𝐹𝑇" 𝑝 = (𝑥( , 𝑝(𝑥( ))(&',…,!"#!

Problem:
Wir benötigen 2𝑛 − 1 Punkt/Werte-Paare

Auswertung des Polynoms nach Horner-Methode

kostet jeweils Θ(𝑛) Schritte für jeden Punkt 𝑥(

Gesamtaufwand für alle 2𝑛 − 1 Punkte wäre Θ(𝑛! ) !

Lösung: Verwende spezielle Werte 𝒙𝒋 ,

so dass schneller per Divide & Conquer berechenbar
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 12
vi
 Bilder erstellt mit [Link]

Diskrete Fourier-Transformation berechnen (II)

! ! ! " ' # !
"##$ %&"#$ %!($ %&$)'

𝑝 𝑥 = 𝑝' + 𝑝$ 𝑥 + ⋯ + 𝑝"#$ 𝑥 "#$

Schreibe 𝑝(𝑥) in folgender Form (n gerade):

𝑝 𝑥 = 𝑝787" 𝑥 ! + 𝑥 : 𝑝9:: (𝑥 ! )

wobei noch nicht (ganz)

𝑝787" 𝑥 = 𝑝' + 𝑝! 𝑥 + ⋯ + 𝑝"#! 𝑥 ("#!)/! Problem halber Größe,
um Divide & Conquer
𝑝9:: 𝑥 = 𝑝$ + 𝑝> 𝑥 + ⋯ + 𝑝"#$ 𝑥 ("#!)/! anzuwenden

𝒑𝒆𝒗𝒆𝒏 , 𝒑𝒐𝒅𝒅 sind Polynome von ca. halbem Grad

– aber leider immer noch 𝟐𝒏 − 𝟏 Punkte 𝒙𝒋 nötig
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 13
vi
 Bilder erstellt mit [Link]

Diskrete Fourier-Transformation berechnen (III)

! ! ! " ' # !
"##$ %&"#$ %!($ %&$)'

𝑝 𝑥 = 𝑝' + 𝑝$ 𝑥 + ⋯ + 𝑝"#$ 𝑥 "#$

Schreibe 𝑝(𝑥) in folgender Form (n gerade): aber immer noch

𝑥! ≠ 𝑥!"#
𝑝 𝑥 = 𝑝787" 𝑥 ! + 𝑥 : 𝑝9:: (𝑥 ! )

Verwende Werte 𝑥( , so dass 𝑥(! = 𝑥(E"

!
für alle 𝑗 = 0,1, … , 𝑛 − 1
"#!
Dann müssen 𝑝787" , 𝑝9:: vom Grad = '( − 1 nur an
!
𝑛 Stellen 𝑥'! , 𝑥$! , … , 𝑥"#$
!
ausgewertet werden
Problemgröße halbiert Þ Divide & Conquer anwendbar
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 14
vi
 Exkurs

𝒎-te primitive Einheitswurzeln

Eine 𝑚-te primitive Einheitswurzel 𝜔- über einem Körper
- = 1 und 𝜔 * ≠ 1 für 𝑗 = 1,2, … , 𝑚 − 1.
erfüllt 𝜔- -

Beispiel für komplexe Zahlen: Für 𝑚-te primitive Einheitswurzel 𝜔F

gilt für gerades 𝑚:
!G,
𝜔F = 𝑒𝑥𝑝 F = cos !G !G
F + 𝑖 : sin F ( ! (EF/! ! F
𝜔F = 𝜔F für alle 𝑗 = 0,1, … ! − 1
denn:
!
𝜔F =𝑖 (EF/! ! !(EF !( F ( !
𝜔F = $
𝜔F 𝜔F = 𝜔F = 𝜔F : 𝜔
\F = 𝜔F
>
𝜔F
=1
6
𝜔F =1
H
𝜔F = −1 ! eine )-te primitive Einheitswurzel,
Ferner ist 𝜔F (
K
I
𝜔F 𝜔F !
da 𝜔F F/! F =1
= 𝜔F
J
𝜔F = −𝑖 ! ( !(
und 𝜔F = 𝜔F ≠ 1 für 𝑗 = 1,2, … , )( − 1
𝑚=8 (und somit 2𝑗 = 2,4, … , 𝑚 − 2)
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 15
vi
FFT - Algorithmen (I)
Wrapper, der für rekursive Aufrufe die aktuelle primitive Einheitswurzel hinzufügt:

FFTWrap(p,n) // n=2^k =#entries in p, k>=0

1 return FFT(p,n,w); //w 2n-th primitive root of unity

Zur Vereinfachung bestimmen wir 2𝑛 (statt 2𝑛 − 1) Punkt-Werte-Paare, so dass

jeweils 𝑛 Einträge im Array p[] und jeweils doppelt so viele Punkt-Werte-Paare
berechnet werden

Wir benötigen, dass 𝑛 Zweierpotenz ist; erreichen wir notfalls, indem wir
𝑛 maximal verdoppeln und die zusätzlichen Einträge im Array p[] auf 0 setzen

(Übergang 𝑛 → 2𝑛 wird später in der asymptotischen Laufzeit nicht ins Gewicht fallen)

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 16
vi
FFT - Algorithmen (II)
FFT(p,n,w) // n=2^k =#entries in p, k>=0
1 pEven=ALLOC(n/2); pOdd=ALLOC(n/2);
2 pVal=ALLOC(2n); pEvenVal=ALLOC(n); pOddVal=ALLOC(n);
3 x=ALLOC(2n); x[0]=1; //input values 𝒙𝒋
4 FOR j=1 TO 2n-1 DO x[j]=w*x[j-1]; //x[j]= w^j

5 IF n==1 THEN //constant polynom

6 pVal[0].x=x[0]; pVal[0].y=p[0].y;
7 pVal[1].x=x[1]; pVal[1].y=p[0].y;
8 ELSE
9 FOR j=0 TO (n-2)/2 DO //create 𝒑𝒆𝒗𝒆𝒏,𝒑𝒐𝒅𝒅
10 pEven[j]=p[2j]; pOdd[j]=p[2j+1];
11 pEvenVal=FFT(pEven,n/2,w*w); //evaluate at 𝒙𝟐𝒋
12 pOddVal =FFT(pOdd,n/2,w*w);
13 FOR j=0 TO 2n-1 DO //𝒑 𝒙𝒋 = 𝒑𝒆𝒗𝒆𝒏 𝒙𝟐𝒋 + 𝒙𝒋 + 𝒑𝒐𝒅𝒅(𝒙𝟐𝒋 )
14 pVal[j].x=x[j];
15 pVal[j].y=pEvenVal[j mod n].y + x[j]*pOddVal[j mod n].y;
16 return pVal;

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 17
vi
 𝑝 𝑥 = 5 + 𝑥 − 𝑥 ! + 2𝑥 >
FFT - Beispiel (I) p=[5,1,-1,2], n=4, w=𝝎𝟖

FFT([5,1,-1,2],4,𝝎𝟖 )
x[]=[𝟏, 𝝎𝟖 , 𝝎𝟐𝟖 , 𝝎𝟑𝟖 , 𝝎𝟒𝟖 , 𝝎𝟓𝟖 , 𝝎𝟔𝟖 , 𝝎𝟕𝟖 ]
Basisfall für
pEvenVal[] 𝑛=1
FFT([5,-1],2,𝝎𝟐𝟖 ) (konstantes
Polynom)
𝟐 𝟒 𝟔
x[]=[𝟏,
FFT(p,n,w) // n=2^k 𝝎 𝟖 , 𝝎𝟖 ,𝝎𝟖 ] in p, k>=0
=#entries
… pEvenVal[]
4 IF n==1 THEN //constant polynom
𝟒
5 FFT([5],1,𝝎
pVal[0].x=x[0]; 𝟖)
pVal[0].y=p[0].y;
6 pVal[1].x=x[1];return
pVal[1].y=p[0].y;
[(1,5),(𝝎𝟒𝟖 ,5)]
7 ELSE
8 FOR j=0 TO (n-2)/2 DO //create 𝒑𝒆𝒗𝒆𝒏,𝒑𝒐𝒅𝒅
9 pEven[j]=p[2j]; pOdd[j]=p[2j+1];
10 pEvenVal=FFT(pEven,n/2,w*w); //evaluate at 𝒙𝟐𝒋
11 pOddVal =FFT(pOdd,n/2,w*w);
12 FOR j=0 TO 2n-1 DO //𝒑 𝒙𝒋 = 𝒑𝒆𝒗𝒆𝒏 𝒙𝟐𝒋 + 𝒙𝒋 + 𝒑𝒐𝒅𝒅 𝒙𝟐𝒋
13 pVal[j].x=x[j];
14 pVal[j].y=pEvenVal[j mod n].y + x[j]*pOddVal[j mod n].y;

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 18
vi
 𝑝 𝑥 = 5 + 𝑥 − 𝑥 ! + 2𝑥 >
FFT - Beispiel (II) p=[5,1,-1,2], n=4, w=𝜔6

FFT([5,1,-1,2],4,𝝎𝟖 )
x[]=[𝟏, 𝝎𝟖 , 𝝎𝟐𝟖 , 𝝎𝟑𝟖 , 𝝎𝟒𝟖 , 𝝎𝟓𝟖 𝝎𝟔𝟖 , 𝝎𝟕𝟖 ]
pEvenVal[]
FFT([5,-1],2,𝝎𝟐𝟖 )
𝟐 𝟒 𝟔
x[]=[𝟏,
FFT(p,n,w) // n=2^k 𝝎 𝟖 , 𝝎𝟖 ,𝝎𝟖 ] in p, k>=0
=#entries
… pEvenVal[]=[(1,5),(𝝎𝟒𝟖 ,5)]
4 IF n==1 THEN //constant polynom
5 pOddVal[]pVal[0].y=p[0].y;
pVal[0].x=x[0];
6 pVal[1].x=x[1]; pVal[1].y=p[0].y;
𝟒
7 ELSE
FFT([-1],1,𝝎 𝟖)
8 return
FOR j=0 TO (n-2)/2 DO //create 𝒑𝒆𝒗𝒆𝒏𝟒𝟖,𝒑
[(1,-1),(𝝎 ,-1)]
𝒐𝒅𝒅
9 pEven[j]=p[2j]; pOdd[j]=p[2j+1];
10 pEvenVal=FFT(pEven,n/2,w*w); //evaluate at 𝒙𝟐𝒋
11 pOddVal =FFT(pOdd,n/2,w*w);
12 FOR j=0 TO 2n-1 DO //𝒑 𝒙𝒋 = 𝒑𝒆𝒗𝒆𝒏 𝒙𝟐𝒋 + 𝒙𝒋 + 𝒑𝒐𝒅𝒅 𝒙𝟐𝒋
13 pVal[j].x=x[j];
14 pVal[j].y=pEvenVal[j mod n].y + x[j]*pOddVal[j mod n].y;

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 19
vi
 𝑝 𝑥 = 5 + 𝑥 − 𝑥 ! + 2𝑥 >
FFT - Beispiel (III) p=[5,1,-1,2], n=4, w=𝜔6

FFT([5,1,-1,2],4,𝝎𝟖 )
x[]=[𝟏, 𝝎𝟖 , 𝝎𝟐𝟖 , 𝝎𝟑𝟖 , 𝝎𝟒𝟖 , 𝝎𝟓𝟖 𝝎𝟔𝟖 , 𝝎𝟕𝟖 ]
5 + 1 + (−1)
pEvenVal[]
FFT([5,-1],2,𝝎𝟐𝟖 ) 5 + 𝜔+, + (−1)
𝟐 𝟒 𝟔
x[]=[𝟏,
FFT(p,n,w) // n=2^k 𝝎𝟖 , 𝝎𝟖 ,𝝎𝟖 ] in p, k>=0
=#entries 5 + 𝜔+- + (−1)
… pEvenVal[]=[(1,5),(𝝎𝟒𝟖 ,5)]
4 IF n==1 THEN //constant polynom 5 + 𝜔+. + (−1)
𝟒
5 pOddVal[]=[(1,-1),(𝝎
pVal[0].x=x[0]; pVal[0].y=p[0].y; 𝟖 ,-1)]
6 pVal[1].x=x[1]; pVal[1].y=p[0].y;
pVal[]=[(1,4),(𝜔6! ,5-𝜔6! ),
7 ELSE H H J J
8 (𝜔 ,5-𝜔 ),(𝜔 ,5-𝜔
FOR j=0 TO (n-2)/2 DO //create 𝒑𝒆𝒗𝒆𝒏,𝒑𝒐𝒅𝒅
6 6 6 6 )]
9 pEven[j]=p[2j]; pOdd[j]=p[2j+1];
10 pEvenVal=FFT(pEven,n/2,w*w); //evaluate at 𝒙𝟐𝒋
11 pOddVal =FFT(pOdd,n/2,w*w);
12 FOR j=0 TO 2n-1 DO //𝒑 𝒙𝒋 = 𝒑𝒆𝒗𝒆𝒏 𝒙𝟐𝒋 + 𝒙𝒋 + 𝒑𝒐𝒅𝒅 𝒙𝟐𝒋
13 pVal[j].x=x[j];
14 pVal[j].y=pEvenVal[j mod n].y + x[j]*pOddVal[j mod n].y;

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 20
vi
 𝑝 𝑥 = 5 + 𝑥 − 𝑥 ! + 2𝑥 >
FFT - Beispiel (IV) p=[5,1,-1,2], n=4, w=𝜔6

FFT([5,1,-1,2],4,𝝎𝟖 )
x[]=[𝟏, 𝝎𝟖 , 𝝎𝟐𝟖 , 𝝎𝟑𝟖 , 𝝎𝟒𝟖 , 𝝎𝟓𝟖 𝝎𝟔𝟖 , 𝝎𝟕𝟖 ]
pEvenVal[]=[(1,4),(𝜔6! ,5-𝜔6! ),(𝜔6H ,5-𝜔6H ),(𝜔6J ,5-𝜔6J )]
pOddVal[]=[(1,3),(𝜔6! ,1+2𝜔6! ),(𝜔6H ,1+2𝜔6H ),(𝜔6J ,1+2𝜔6J )]
$ ! $ !
pVal=[(1,4+1:3),(𝜔
FFT(p,n,w) 6 ,(5-𝜔6in
// n=2^k =#entries )+𝜔p, k>=0 6 )),
6 :(1+2𝜔
… (𝜔6! ,(5-𝜔6H )+𝜔6! :(1+2𝜔6H ),…]
4 IF n==1 THEN //constant polynom
5 7 = 𝑝(1)
pVal[0].x=x[0]; + 𝜔6$ − 𝜔6! + 2𝜔6> = 𝑝(𝜔6$ )
5pVal[0].y=p[0].y;
6 pVal[1].x=x[1]; pVal[1].y=p[0].y;
7 ELSE 5 + 𝜔6! − 𝜔6H + 2𝜔6J = 𝑝(𝜔6! )
8 FOR j=0 TO (n-2)/2 DO //create 𝒑𝒆𝒗𝒆𝒏,𝒑𝒐𝒅𝒅
return pVal[]
9 pEven[j]=p[2j]; pOdd[j]=p[2j+1];
10 pEvenVal=FFT(pEven,n/2,w*w); //evaluate at 𝒙𝟐𝒋
11 pOddVal =FFT(pOdd,n/2,w*w);
12 FOR j=0 TO 2n-1 DO //𝒑 𝒙𝒋 = 𝒑𝒆𝒗𝒆𝒏 𝒙𝟐𝒋 + 𝒙𝒋 + 𝒑𝒐𝒅𝒅 𝒙𝟐𝒋
13 pVal[j].x=x[j];
14 pVal[j].y=pEvenVal[j mod n].y + x[j]*pOddVal[j mod n].y;

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 21
vi
FFT - Laufzeit Laufzeit Θ(𝑛 log 𝑛)

FFT(p,n,w) // n=2^k =#entries in p, k>=0

1 pEven=ALLOC(n/2); pOdd=ALLOC(n/2);
2 pVal=ALLOC(2n); pEvenVal=ALLOC(n); pOddVal=ALLOC(n);
3 x=ALLOC(2n); x[0]=1; //input values 𝒙𝒋
4 FOR j=1 TO 2n-1 DO x[j]=w*x[j-1]; //x[j]= w^j Θ(𝑛)

5 IF n==1 THEN //constant polynom

6 pVal[0].x=x[0]; pVal[0].y=p[0].y; also 𝑇 𝑛 = 2𝑇 𝑛/2 + Θ(𝑛)
7 pVal[1].x=x[1]; pVal[1].y=p[0].y;
8 ELSE
9 FOR j=0 TO (n-2)/2 DO //create 𝒑𝒆𝒗𝒆𝒏,𝒑𝒐𝒅𝒅 Θ(𝑛)
10 pEven[j]=p[2j]; pOdd[j]=p[2j+1];
11 pEvenVal=FFT(pEven,n/2,w*w); //evaluate at 𝒙𝟐𝒋
12 pOddVal =FFT(pOdd,n/2,w*w);
13 FOR j=0 TO 2n-1 DO //𝒑 𝒙𝒋 = 𝒑𝒆𝒗𝒆𝒏 𝒙𝟐𝒋 + 𝒙𝒋 + 𝒑𝒐𝒅𝒅(𝒙𝟐𝒋 ) Θ(𝑛)
14 pVal[j].x=x[j];
15 pVal[j].y=pEvenVal[j mod n].y + x[j]*pOddVal[j mod n].y;
16 return pVal;

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 22
vi
 Die Diskrete Fourier-Transformation wird abstrakt definiert durch:

𝑎! 𝑎@!
𝑎" DFT 𝑎@" $%"
*)
⋮ ⋮ mit 𝑎@* = D 𝑎) * 𝜔$
)(!
𝑎$%" 𝑎@$%"

Interpretieren Sie diese Formel bezüglich unserer Anwendung

zur Polynommultiplikation.

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 23
vi
Inverse DFT berechnen (I)

Zur Erinnerung:
𝑟 = 𝑝𝑞 Polynom vom Grad 𝑚 ≤ 2𝑛 − 1
1 𝑥' ⋯ 𝑥'F#$ 𝑟' 𝑦'
(
1 𝑥$ ⋯ 𝑥$F#$ 𝑟$ 𝑦$ 𝑥( = 𝜔F 𝑗-te Potenz der 𝑚-ten
⋮ = ⋮
⋮ ⋱ primitiven Einheitswurzel 𝜔F
1 𝑥F#$ F#$
⋯ 𝑥F#$ 𝑟F#$ 𝑦F#$
Vandermonde-Matrix 𝑉 = 𝑉 𝑥' , … , 𝑥F#$
(%
(𝑉)(% = 𝜔F

Bestimme Koeffizienten von 𝑟 durch inverse Matrix 𝑉:

#$
𝑟' 1 𝑥' ⋯ 𝑥'F#$ 𝑦'
𝑟$ 1 𝑥$ ⋯ 𝑥$F#$ 𝑦$
⋮ = : ⋮
⋮ ⋱
𝑟F#$ 1 𝑥F#$ F#$
⋯ 𝑥F#$ 𝑦F#$

= 𝑉 %!

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 24
vi
Inverse DFT berechnen (II)
.123
Es gilt: 𝑉 %" = - *)
, denn:

1
⋯ %
𝜔F
1 #( #!( # F#$ ( !%
𝑉 #$ : 𝑉 = : 1 𝜔F 𝜔F ⋯ 𝜔F : ⋮ 𝜔F ⋮
𝑚 ⋮
⋯
𝜔FF#$ %

F#$ F#$
1 '
1
: 9 𝜔F = : 9 1 = 1 für 𝑗 = 𝑘
F#$ 𝑚 𝑚
1 O #(E% O&' O&'
= : 9 𝜔F =
𝑚 F #(E%
O&' (% 1 𝜔F −1 1 1−1
: = : #(E% =0
𝑚 𝜔 #(E% − 1 𝑚 𝜔 −1
F F
für 𝑗 ≠ 𝑘,
" 8!": 0 ≤ 𝑗, 𝑘 < 𝑚
verwendet ∑789 4 ! #$
456 𝑞 = !#$ für 𝑞 ≠ 1, hier 𝑞 = 𝜔7 ≠ 1 für 𝑗 ≠ 𝑘

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 25
vi
Inverse DFT berechnen (III) rechne Faktor
IFFTWrap(rVal,n) // n=2^k =#entries in rVal, k>=0 1/n heraus
//w n-th primitive root of unity
1 r[]=IFFT(rVal,n,w);
2 FOR j=0 TO n-1 DO r[j]=r[j]/n;
3 return r; Laufzeit Θ(𝑛 log 𝑛)
IFFT(rVal,n,w) // n=2^k =#entries in rVal, k>=0
1 r=ALLOC(n); rEvenVal=ALLOC(n); rOddVal=ALLOC(n);
2 x=ALLOC(n); x[0]=1;
3 FOR j=1 TO n-1 DO x[j]=w*x[j-1]; //x[j]= w^j
4 IF n==1 THEN
5 r[0]=rVal[0].y;
6 ELSE Division, da wir inverses
8;!
7 rEven=ALLOC(n/2); rOdd=ALLOC(n/2); 𝜔# benötigen
8 FOR j=0 TO (n-2)/2 DO
9 rEvenVal[j]=rVal[2j]; rOddVal[j]=rVal[2j+1];
10 rEven=IFFT(rEvenVal,n/2,w*w);
11 rOdd =IFFT(rOddVal,n/2,w*w);
12 FOR j=0 TO n-1 DO
13 r[j]=rEven[j mod n/2] + rOdd[j mod n/2]/x[j];
14 return r;

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 26
vi
Inverse FFT: Beispiel (I) 𝑟 𝑥 = 5 + 𝑥 − 𝑥 ! + 2𝑥 >
𝜔H = 𝑖
IFFT([(1,7),(𝝎𝟒 ,6-i),(𝝎𝟐𝟒 ,1),(𝝎𝟑𝟒 ,6+i)],4,𝝎𝟒 )
𝒙 𝒓(𝒙)
x[]=[𝟏, 𝝎𝟒 , 𝝎𝟐𝟒 , 𝝎𝟑𝟒 ]
1 7
rEven[]
𝜔H = 𝑖 6−𝑖
IFFT([(1,7),(𝝎𝟐𝟒 ,1)],2,𝝎𝟐𝟒 )
𝜔H! = −1 1
𝟐
x[]=[𝟏,
IFFT(rVal,n,w) 𝟒]
//𝝎n=2^k =#entries in rVal, k>=0
𝜔H> = −𝑖 6+𝑖
1 r=ALLOC(n); rEvenVal=ALLOC(n); rOddVal=ALLOC(n);
2 rEven[]
x=ALLOC(n); x[0]=1;
3 FOR j=1 TO n-1 DO x[j]=w*x[j-1]; //x[j]= w^j
IFFT([(1,7)],1,𝟏)
4 IF n==1 THEN
5 return [7]
r[0]=rVal[0].y;
6 ELSE
7 rEven=ALLOC(n/2); rOdd=ALLOC(n/2);
8 FOR j=0 TO (n-2)/2 DO
9 rEvenVal[j]=rVal[2j]; rOddVal[j]=rVal[2j+1];
10 rEven=IFFT(rEvenVal,n/2,w*w);
11 rOdd =IFFT(rOddVal,n/2,w*w);
12 FOR j=0 TO n-1 DO
13 r[j]=rEven[j mod n/2] + rOdd[j mod n/2]/x[j];
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 27
vi
Inverse FFT: Beispiel (II) 𝑟 𝑥 = 5 + 𝑥 − 𝑥 ! + 2𝑥 >
𝜔H = 𝑖
IFFT([(1,7),(𝝎𝟒 ,6-i),(𝝎𝟐𝟒 ,1),(𝝎𝟑𝟒 ,6+i)],4,𝝎𝟒 )
𝒙 𝒓(𝒙)
x[]=[𝟏, 𝝎𝟒 , 𝝎𝟐𝟒 , 𝝎𝟑𝟒 ]
1 7
rEven[]
𝜔H = 𝑖 6−𝑖
IFFT([(1,7),(𝝎𝟐𝟒 ,1)],2,𝝎𝟐𝟒 )
𝜔H! = −1 1
𝟐
x[]=[𝟏,
IFFT(rVal,n,w) 𝟒]
//𝝎n=2^k =#entries in rVal, k>=0
𝜔H> = −𝑖 6+𝑖
1 r=ALLOC(n); rEvenVal=ALLOC(n); rOddVal=ALLOC(n);
2 rEven[]=[7]
x=ALLOC(n); x[0]=1;
3 FOR j=1rOdd[]
TO n-1 DO x[j]=w*x[j-1]; //x[j]= w^j
4 IF n==1 THEN
5 IFFT([𝝎𝟐𝟒 ,1)],1,𝟏)
r[0]=rVal[0].y;
6 ELSE return [1]
7 rEven=ALLOC(n/2); rOdd=ALLOC(n/2);
8 FOR j=0 TO (n-2)/2 DO
9 rEvenVal[j]=rVal[2j]; rOddVal[j]=rVal[2j+1];
10 rEven=IFFT(rEvenVal,n/2,w*w);
11 rOdd =IFFT(rOddVal,n/2,w*w);
12 FOR j=0 TO n-1 DO
13 r[j]=rEven[j mod n/2] + rOdd[j mod n/2]/x[j];
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 28
vi
Inverse FFT: Beispiel (III) 𝑟 𝑥 = 5 + 𝑥 − 𝑥 ! + 2𝑥 >
𝜔H = 𝑖
IFFT([(1,7),(𝝎𝟒 ,6-i),(𝝎𝟐𝟒 ,1),(𝝎𝟑𝟒 ,6+i)],4,𝝎𝟒 )
𝒙 𝒓(𝒙)
x[]=[𝟏, 𝝎𝟒 , 𝝎𝟐𝟒 , 𝝎𝟑𝟒 ]
1 7
rEven[]
𝜔H = 𝑖 6−𝑖
IFFT([(1,7),(𝝎𝟐𝟒 ,1)],2,𝝎𝟐𝟒 )
𝜔H! = −1 1
𝟐
x[]=[𝟏,
IFFT(rVal,n,w) 𝟒]
//𝝎n=2^k =#entries in rVal, k>=0
𝜔H> = −𝑖 6+𝑖
1 r=ALLOC(n); rEvenVal=ALLOC(n); rOddVal=ALLOC(n);
2 rEven[]=[7]
x=ALLOC(n); x[0]=1;
3 FOR j=1rOdd[]=[1]
TO n-1 DO x[j]=w*x[j-1]; //x[j]= w^j
4 IF n==1 THEN
r[]=[7+1/1,7+1/-1]=[8,6]
5 r[0]=rVal[0].y;
6 ELSE return r[]
7 rEven=ALLOC(n/2); rOdd=ALLOC(n/2);
8 FOR j=0 TO (n-2)/2 DO
9 rEvenVal[j]=rVal[2j]; rOddVal[j]=rVal[2j+1];
10 rEven=IFFT(rEvenVal,n/2,w*w);
11 rOdd =IFFT(rOddVal,n/2,w*w);
12 FOR j=0 TO n-1 DO
13 r[j]=rEven[j mod n/2] + rOdd[j mod n/2]/x[j];
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 29
vi
Inverse FFT: Beispiel (IV) 𝑟 𝑥 = 5 + 𝑥 − 𝑥 ! + 2𝑥 >
𝜔H = 𝑖
IFFT([(1,7),(𝝎𝟒 ,6-i),(𝝎𝟐𝟒 ,1),(𝝎𝟑𝟒 ,6+i)],4,𝝎𝟒 )
𝒙 𝒓(𝒙)
x[]=[𝟏, 𝝎𝟒 , 𝝎𝟐𝟒 , 𝝎𝟑𝟒 ]
1 7
rEven[]=[8,6]
𝜔H = 𝑖 6−𝑖
rOdd[]
𝜔H! = −1 1
𝟑 𝟐
IFFT([(𝝎//
IFFT(rVal,n,w) 𝟒 ,6-i),(𝝎 𝟒 ,6+i)],2,𝝎
n=2^k =#entries 𝟒)
in rVal, k>=0
𝜔H> = −𝑖 6+𝑖
1 r=ALLOC(n); rEvenVal=ALLOC(n); rOddVal=ALLOC(n);
x[]=[𝟏, 𝝎𝟐𝟒 ]
2 x=ALLOC(n); x[0]=1;
3 FOR j=1rEven[]
TO n-1 DO x[j]=w*x[j-1]; //x[j]= w^j
4 IF n==1 THEN
IFFT([(𝝎𝟒 ,6-i)],1,𝟏)
5 r[0]=rVal[0].y;
6 ELSE return [6-i]
7 rEven=ALLOC(n/2); rOdd=ALLOC(n/2);
8 FOR j=0 TO (n-2)/2 DO
9 rEvenVal[j]=rVal[2j]; rOddVal[j]=rVal[2j+1];
10 rEven=IFFT(rEvenVal,n/2,w*w);
11 rOdd =IFFT(rOddVal,n/2,w*w);
12 FOR j=0 TO n-1 DO
13 r[j]=rEven[j mod n/2] + rOdd[j mod n/2]/x[j];
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 30
vi
Inverse FFT: Beispiel (V) 𝑟 𝑥 = 5 + 𝑥 − 𝑥 ! + 2𝑥 >
𝜔H = 𝑖
IFFT([(1,7),(𝝎𝟒 ,6-i),(𝝎𝟐𝟒 ,1),(𝝎𝟑𝟒 ,6+i)],4,𝝎𝟒 )
𝒙 𝒓(𝒙)
x[]=[𝟏, 𝝎𝟒 , 𝝎𝟐𝟒 , 𝝎𝟑𝟒 ]
1 7
rEven[]=[8,6]
𝜔H = 𝑖 6−𝑖
rOdd[]
𝜔H! = −1 1
𝟑 𝟐
IFFT([(𝝎//
IFFT(rVal,n,w) 𝟒 ,6-i),(𝝎 𝟒 ,6+i)],2,𝝎
n=2^k =#entries 𝟒)
in rVal, k>=0
𝜔H> = −𝑖 6+𝑖
1 r=ALLOC(n); rEvenVal=ALLOC(n); rOddVal=ALLOC(n);
x[]=[𝟏, 𝝎𝟐𝟒 ]
2 x=ALLOC(n); x[0]=1;
3 FOR j=1rEven[]=[6-i]
TO n-1 DO x[j]=w*x[j-1]; //x[j]= w^j
4 IF n==1rOdd[]
THEN
5 r[0]=rVal[0].y;
6 ELSE IFFT([(𝝎𝟑𝟒 ,6+i)],1,𝟏)
7 rEven=ALLOC(n/2);
returnrOdd=ALLOC(n/2);
[6+i]
8 FOR j=0 TO (n-2)/2 DO
9 rEvenVal[j]=rVal[2j]; rOddVal[j]=rVal[2j+1];
10 rEven=IFFT(rEvenVal,n/2,w*w);
11 rOdd =IFFT(rOddVal,n/2,w*w);
12 FOR j=0 TO n-1 DO
13 r[j]=rEven[j mod n/2] + rOdd[j mod n/2]/x[j];
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 31
vi
Inverse FFT: Beispiel (VI) 𝑟 𝑥 = 5 + 𝑥 − 𝑥 ! + 2𝑥 >
𝜔H = 𝑖
IFFT([(1,7),(𝝎𝟒 ,6-i),(𝝎𝟐𝟒 ,1),(𝝎𝟑𝟒 ,6+i)],4,𝝎𝟒 )
𝒙 𝒓(𝒙)
x[]=[𝟏, 𝝎𝟒 , 𝝎𝟐𝟒 , 𝝎𝟑𝟒 ]
1 7
rEven[]=[8,6]
𝜔H = 𝑖 6−𝑖
rOdd[]
𝜔H! = −1 1
𝟑 𝟐
IFFT([(𝝎//
IFFT(rVal,n,w) 𝟒 ,6-i),(𝝎 𝟒 ,6+i)],2,𝝎
n=2^k =#entries 𝟒)
in rVal, k>=0
𝜔H> = −𝑖 6+𝑖
1 r=ALLOC(n); rEvenVal=ALLOC(n); rOddVal=ALLOC(n);
x[]=[𝟏, 𝝎𝟐𝟒 ]
2 x=ALLOC(n); x[0]=1;
3 FOR j=1rEven[]=[6-i]
TO n-1 DO x[j]=w*x[j-1]; //x[j]= w^j
4 IF n==1rOdd[]=[6+i]
THEN
5 r[0]=rVal[0].y;
6 ELSE r[]=[12,-2i]
7 rEven=ALLOC(n/2);
return r[] rOdd=ALLOC(n/2);
8 FOR j=0 TO (n-2)/2 DO
9 rEvenVal[j]=rVal[2j]; rOddVal[j]=rVal[2j+1];
10 rEven=IFFT(rEvenVal,n/2,w*w);
11 rOdd =IFFT(rOddVal,n/2,w*w);
12 FOR j=0 TO n-1 DO
13 r[j]=rEven[j mod n/2] + rOdd[j mod n/2]/x[j];
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 32
vi
Inverse FFT: Beispiel (VII) 𝑟 𝑥 = 5 + 𝑥 − 𝑥 ! + 2𝑥 >
𝜔H = 𝑖
IFFT([(1,7),(𝝎𝟒 ,6-i),(𝝎𝟐𝟒 ,1),(𝝎𝟑𝟒 ,6+i)],4,𝝎𝟒 )
𝒙 𝒓(𝒙)
x[]=[𝟏, 𝝎𝟒 , 𝝎𝟐𝟒 , 𝝎𝟑𝟒 ]
1 7
rEven[]=[8,6]
𝜔H = 𝑖 6−𝑖
rOdd[]=[12,-2i]
𝜔H! = −1 1
r[0]=8+12/1=20
IFFT(rVal,n,w) // n=2^k =#entries in rVal, k>=0
Alle Werte werden in 𝜔H> = −𝑖 6+𝑖
1 r=ALLOC(n); rEvenVal=ALLOC(n); rOddVal=ALLOC(n);
r[1]=6-2i/i=4 IFFTWrap noch durch
2 x=ALLOC(n); x[0]=1;
3r[2]=8+12/-1=-4 𝑛 = 4 dividiert und
FOR j=1 TO n-1 DO x[j]=w*x[j-1]; ergeben
//x[j]= w^j
4 IF n==1 THEN daher Koeffizienten von 𝑟(𝑥)
5r[3]=6-2i/-i=8
r[0]=rVal[0].y;
6return
ELSE r[]=[20,4,-4,8]
7 rEven=ALLOC(n/2); rOdd=ALLOC(n/2);
8 FOR j=0 TO (n-2)/2 DO
9 rEvenVal[j]=rVal[2j]; rOddVal[j]=rVal[2j+1];
10 rEven=IFFT(rEvenVal,n/2,w*w);
11 rOdd =IFFT(rOddVal,n/2,w*w);
12 FOR j=0 TO n-1 DO
13 r[j]=rEven[j mod n/2] + rOdd[j mod n/2]/x[j];
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 33
vi
 Bilder erstellt mit [Link]

Fourier-Transformation, woanders
Q
P& !"GR !"GR
𝑓: ℝ → ℝ mit Periode 𝑇 𝑓 𝑡 = !
+9 (𝑎" : cos S
+ 𝑏" : sin S
)
"&$

Darstellung durch Koeffizienten 𝑎' , 𝑎$ , 𝑏$ , …

Beispielanwendung: Frequenz-Filter
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 34
vi
 Backtracking

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 35
vi
Backtracking

Prinzip Backtracking:

Finde Lösungen 𝑥 = (𝑥" , 𝑥# , … , 𝑥$ ) per „Trial-and-Error“,

indem Teillösung 𝑥" , 𝑥# , … , 𝑥'%" durch Kandidaten 𝑥'

ergänzt wird, bis Gesamtlösung erhalten,

oder bis festgestellt, dass keine Gesamtlösung erreichbar,

und Kandidat 𝑥'%" revidiert wird

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 36
vi
Beispiel: 4x4-Sudoku (I)

4
in jeder Zeile die Ziffern 1,2,3,4
2
in jeder Spalte die Ziffern 1,2,3,4
4 3 1
in jedem Quadranten die Ziffern 1,2,3,4
3

SUDOKU-BACKTRACKING(B) // B[0…3][0…3] board

prüft, ob Board
komplett ausgefüllt 1 IF isFull(B) THEN
2 print „solution: “+B;
nächste freie Position 3 ELSE
(zeilenweise) 4 (i,j)=nextFreePos(B);
5 FOR v=1 TO 4 DO
prüft Kriterien oben 6 IF isAdmissible(B,i,j,v) THEN
7 B[i,j]=v;
löscht Feld vor Rückkehr
8 SUDOKU-BACKTRACKING(B);
9 B[i,j]=empty; vi
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 37
Beispiel: 4x4-Sudoku (II)

4 1

2
zwei Möglichkeiten: 1 und 2
4 3 1

SUDOKU-BACKTRACKING(B) // B[0…3][0…3] board

1 IF isFull(B) THEN
2 print „solution: “+B;
3 ELSE
4 (i,j)=nextFreePos(B);
5 FOR v=1 TO 4 DO
6 IF isAdmissible(B,i,j,v) THEN
7 B[i,j]=v;
8 SUDOKU-BACKTRACKING(B);
9 B[i,j]=empty; vi
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 38
Beispiel: 4x4-Sudoku (III)

4 1

4 3 1 keine zulässige Option ® Backtracking

SUDOKU-BACKTRACKING(B) // B[0…3][0…3] board

1 IF isFull(B) THEN
2 print „solution: “+B;
3 ELSE
4 (i,j)=nextFreePos(B);
5 FOR v=1 TO 4 DO
6 IF isAdmissible(B,i,j,v) THEN
7 B[i,j]=v;
8 SUDOKU-BACKTRACKING(B);
9 B[i,j]=empty; vi
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 39
Beispiel: 4x4-Sudoku (IV)

4 1 3

4 3 1 ® Backtracking

SUDOKU-BACKTRACKING(B) // B[0…3][0…3] board

1 IF isFull(B) THEN
2 print „solution: “+B;
3 ELSE
4 (i,j)=nextFreePos(B);
5 FOR v=1 TO 4 DO
6 IF isAdmissible(B,i,j,v) THEN
7 B[i,j]=v;
8 SUDOKU-BACKTRACKING(B);
9 B[i,j]=empty; vi
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 40
Beispiel: 4x4-Sudoku (III)

4 2 1 3
einzig zulässige Option
2

4 3 1

SUDOKU-BACKTRACKING(B) // B[0…3][0…3] board

1 IF isFull(B) THEN
2 print „solution: “+B;
3 ELSE
4 (i,j)=nextFreePos(B);
5 FOR v=1 TO 4 DO
6 IF isAdmissible(B,i,j,v) THEN
7 B[i,j]=v;
8 SUDOKU-BACKTRACKING(B);
9 B[i,j]=empty; vi
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 41
Beispiel: 4x4-Sudoku (VI)

4 2 1 3
zwei Möglichkeiten: 1 und 3
1 2

4 3 1 keine zulässige Option ® Backtracking

SUDOKU-BACKTRACKING(B) // B[0…3][0…3] board

1 IF isFull(B) THEN
2 print „solution: “+B;
3 ELSE
4 (i,j)=nextFreePos(B);
5 FOR v=1 TO 4 DO
6 IF isAdmissible(B,i,j,v) THEN
7 B[i,j]=v;
8 SUDOKU-BACKTRACKING(B);
9 B[i,j]=empty; vi
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 42
Beispiel: 4x4-Sudoku (VII)

4 2 1 3

3 1 4 2

2 4 3 1 einzig zulässige Option

1 3 2 4

SUDOKU-BACKTRACKING(B) // B[0…3][0…3] board

1 IF isFull(B) THEN
2 print „solution: “+B;
3 ELSE
4 (i,j)=nextFreePos(B);
5 FOR v=1 TO 4 DO
6 IF isAdmissible(B,i,j,v) THEN
7 B[i,j]=v;
8 SUDOKU-BACKTRACKING(B);
9 B[i,j]=empty; vi
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 43
Backtracking vs. DFS
4 2 1 3

3 1 4 2

2 4 3 1

1 3 2 4

4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3

3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2

2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1

1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4

4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3

3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2

2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1

1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4

4 2 1 3 4 2 1 3

3 1 4 2 3 1 4 2

2 4 3 1 2 4 3 1

1 3 2 4 1 3 2 4

Backtracking kann man als Tiefensuche auf Rekursionsbaum betrachten,

wobei aussichtslose Lösungen evtl. frühzeitig abgeschnitten werden

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 44
vi
Backtracking vs. Brute-Force Search
4 2 1 3

3 1 4 2

2 4 3 1

1 3 2 4

4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3

3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2

2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1

1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4

4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3

3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2

2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1

1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4

…
4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3

… 3

2
1

4
4

3
2

1
3

2
1

4
4

3
2

1
3

2
1

4
4

3
2

1
3

2
1

4
4

3
2

1
3

2
1

4
4

3
2

1
3

2
1

4
4

3
2

1
3

2
1

4
4

3
2

1
3

2
1

4
4

3
2

1
3

2
1

4
4

3
2

1
3

2
1

4
4

3
2

1
3

2
1

4
4

3
2

1
3

2
1

4
4

3
2

1
3

2
1

4
4

3
2

1
3

2
1

4
4

3
2

1
3

2
1

4
4

3
2

1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4

alle möglichen Belegungen

Backtracking kann man als „intelligentere“ erschöpfende Suche ansehen,

die aussichtslose Lösungen vorher aussortiert

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 45
vi
Backtracking: Lösungssuche

4 2 1 3 4 2 1 3 4 2 1 3

3 1 4 2 3 1 4 2 3 1 4 2

2 4 3 1 2 4 3 1 2 4 3 1

1 3 2 4 1 3 2 4 1 3 2 4

4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3

3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2

2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1

1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4

4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3

3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2

2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1

1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4

finde eine Lösung finde alle Lösungen finde beste Lösung

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 46
vi
Beispiel: Regulärer Ausdruck (I) Mustersuche in Strings

regulärer Ausdruck: a(b|c)+d

…dann ein oder mehrere

…der mit a beginnt Zeichen aus der Menge …und noch auf d endet
{b,c} enthält

durchsuche String abacd per Backtracking „gegen“ regulären Ausdruck

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 47
vi
Beispiel: Regulärer Ausdruck (II) a(b|c)+d

abacd

abacd abacd abacd

keine
a(b|c)+d weitere Back- keine Option a(b|c)+d
Option tracking
Back-
abacd tracking
abacd
keine Back-
weitere
a(b|c)+d Option tracking a(b|c)+d

abacd abacd
keine Option
a(b|c)+d
Back-
tracking Lösung!
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 48
vi
 Aufwand Backtracking
Evtl. exponentieller Aufwand kann exponentiell werden

Schlechte, verschachtelte
regulärer Ausdruck: ^(a+)+$ Formulierung für:
„Zeile enthält nur a‘s“

mindestens einmal a und

Zeilenbeginn mindestens einer dieser a-Folgen Zeilenende

aaaa…aaaab
expontielle Anzahl
von Möglichkeiten

(aaa…a) (aa…a)(a) (a…a)(aa) (a…a)(a)(a) …

Back- Back- Back- Back-
tracking tracking tracking tracking

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 49
vi
 Dynamische Programmierung

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 50
vi
Dynamisches Programmieren

Prinzip Dynamisches Programmieren:

Teile Problem in (überlappende) Teilprobleme

Löse rekursiv Teilprobleme,

verwende dabei Zwischenergebnisse wieder
(„Memoization“)

Rekonstruiere Gesamtlösung

Achtung: es geht primär um das Auffinden geeigneter Rekursionen!

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 51
vi
Beispiel: Fibonacci-Zahlen

𝐹m = 1, 𝐹n = 1, 𝐹o = 𝐹opm + 𝐹opn für 𝑛 ≥ 3

Fib-Rek(n) // n>=1
1 IF n<=2 THEN
2 return 1;
3 ELSE
4 return Fib-Rek(n-1)+Fib-Rek(n-2);

(vereinfachte) Laufzeitabschätzung mittels 𝑇(𝑛 − 1) ≈ 𝑇(𝑛 − 2):

𝑇 𝑛 =𝑇 𝑛−1 +𝑇 𝑛−2 +𝑐
≈2:𝑇 𝑛−1 +𝑐
=4:𝑇 𝑛−2 +2:𝑐+𝑐
= …
= Θ(2" )

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 52
vi
Fibonacci-Berechnungsbaum

𝐹s

viele Werte
𝐹t 𝐹u werden mehrfach
berechnet

𝐹u 𝐹v 𝐹v 𝐹n
Ansatz:
𝐹v 𝐹n 𝐹n 𝐹m 𝐹n 𝐹m speichere stattdessen
Werte zwischen
(„Memoization“)

𝐹n 𝐹m

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 53
vi
Fibonacci mit Memoization Laufzeit Θ(𝑛)
𝐹s
Wenn Basisfall erreicht,
nur noch Addieren und Auslesen

𝐹t aus Speicher 𝐹u
FibDyn(n) // n>=1
1 F[]=ALLOC(n); //F_i at F[i-1]
𝐹u 𝐹v 2 FOR i=0 TO n-1 DO F[i]=0;
aus Speicher 3 return FibDynRek(n-1,F);
FibDynRek(i,F) // i>=0
𝐹v 𝐹n 1 IF F[i]!=0 THEN return F[i];
aus Speicher 2 IF i<=1 THEN schon berechnet,
3 f=1 dann zurückgeben
𝐹n 𝐹m 4 ELSE
5 f=FibDynRek(i-1,F)+FibDynRek(i-2,F);
6 F[i]=f;
7 return f;
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 54
vi
Minimum Edit Distance (I) (Levenshtein-Distanz)

Misst Ähnlichkeit von Texten: Wie viele (Buchstaben-)Operationen

ins(S,i,b) – fügt an i-ter Position Buchstabe b in String S ein

del(S,i) – löscht an i-ter Position Buchstabe in String S
sub(S,i,b) – ersetzt an i-ter Position in String S den Buchstaben durch b

sind nötig, um Texte ineinander zu überführen?

Levenshtein-Distanz=5
e i n T e s t
(manchmal Kosten 2 für
Substitution, dann Distanz hier 6)
z w e i F e s t e
i i c c d c s c c c i c für copy(S,i)-ohne Kosten

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 55
vi
Minimum Edit Distance (II)
beginnen hier jeweils bei 1
Algorithmische Sichtweise:

Überführe schrittweise String X[1…m] von links nach rechts in String Y[1…n]

Jeweils Teil X[1…i] bereits in Teil Y[1…j] transformiert

X[1…4] X[5]

e i n T e s t Achtung:
Optimalität dieser
Herangehensweise
wäre zu zeigen
z w e i F e s t e

Y[1…5] Y[6]
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 56
vi
Minimum Edit Distance (III)
D[i][j] sei Distanz, um X[1…i] in Y[1…j] zu überführen (i,j>=1)

Betrachte nächstens Schritt, um X in Y zu überführen:

copy sub del ins
a a a

a b b

„vorher X[1…i-1] „vorher X[1…i-1] „vorher X[1…i-1] „vorher X[1…i]

in Y[1…j-1] in Y[1…j-1] in Y[1…j] in Y[1…j-1]
überführt, und jetzt überführt, und jetzt überführt, und jetzt überführt, und jetzt
(kostenfrei) kopieren“ ersetzen“ X[i] löschen“ Y[j] einfügen“

D[i][j] D[i][j] D[i][j] D[i][j]

= = = =
D[i-1][j-1] D[i-1][j-1]+1 D[i-1][j]+1 D[i][j-1]+1

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 57
vi
Minimum Edit Distance (IV)
D[i][j] sei Distanz, um X[1…i] in Y[1…j] zu überführen (i,j>=1)

Betrachte nächstens Schritt, um X in Y zu überführen:

copy sub del ins
a a a

a b b

„vorher X[1…i-1] „vorher X[1…i-1] „vorher X[1…i-1] „vorher X[1…i]

in Y[1…j-1] in Y[1…j-1] in Y[1…j] in Y[1…j-1]
überführt, und jetzt überführt, und jetzt überführt, und jetzt überführt, und jetzt
(kostenfrei) kopieren“ ersetzen“ X[i] löschen“ Y[j] einfügen“

D[i][j] D[i][j] D[i][j] D[i][j] D[i][j]

= = = = =
D[i-1][j-1]+(X[i]!=Y[j])
D[i-1][j-1] D[i-1][j-1]+1 D[i-1][j]+1 D[i][j-1]+1
1, wenn wahr, 0 sonst
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 58
vi
Minimum Edit Distance (IV)
D[i][j] sei Distanz, um X[1…i] in Y[1…j] zu überführen (i,j>=1)

Betrachte nächstens Schritt, um X in Y zu überführen:

copy sub del ins
a a a

a b b

Da wir beste Ersetzungsstrategie suchen:

D[i][j]
=
D[i][j] D[i][j] D[i][j] D[i][j] D[i][j]
min
= = = = =
{ D[i-1][j-1]+(X[i]!=Y[j])
D[i-1][j-1] ,
D[i-1][j-1]+1 D[i-1][j]+1, D[i][j-1]+1 }

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 59
vi
Minimum Edit Distance (V)
D[i][j] sei Distanz, um X[1…i] in Y[1…j] zu überführen (i,j>=1)

„Randbedingungen“:

D[0][j]=j – füge j Buchstaben Y[1…j] zu leerem String X[1…0] hinzu

D[i][0]=i – lösche i Buchstaben X[1…i], um leeren String Y[1…0]

zu erhalten

Da wir beste Ersetzungsstrategie suchen:

D[i][j]
=
D[i][j] D[i][j] D[i][j] D[i][j] D[i][j]
min
= = = = =
{ D[i-1][j-1]+(X[i]!=Y[j])
D[i-1][j-1] ,
D[i-1][j-1]+1 D[i-1][j]+1, D[i][j-1]+1 }

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 60
vi
Minimum Edit Distance: Algorithmus
mittels dynamischer Programmierung und Memoization

MinEditDist(X,Y,m,n) // X=X[1…m], Y=Y[1…n]

1 D[][]=ALLOC(m,n); Laufzeit und
2 FOR i=0 TO m DO D[i][0]=i; Speicher
3 FOR j=0 TO n DO D[0][j]=j; Θ(𝑚𝑛)
4 FOR i=1 TO m DO
5 FOR j=1 TO n DO
6 IF X[i]=Y[j] THEN s=0 ELSE s=1;
7 D[i][j]=min{D[i-1][j-1]+s,D[i-1][j]+1,D[i][j-1]+1};
8 return D[m][n];

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 61
vi
Minimum Edit Distance: Beispiel (I)
X[1…i]
D 0 1 2 3 4 5 6 7 8
X[1… 8] = ein Test 0 0 1 2 3 4 5 6 7 8
1
Y[1…10] = zwei Feste 1
2 2
3 3

Y[1…j]
Initialisierung (2 und 3) 4 4
5 5
6 6
7 7
MinEditDist(X,Y,m,n) // X=X[1…m], Y=Y[1…n]
8 8
1 D[][]=ALLOC(m,n);
9 9
2 FOR i=0 TO m DO D[i][0]=i;
10 10
3 FOR j=0 TO n DO D[0][j]=j;
4 FOR i=1 TO m DO
5 FOR j=1 TO n DO
6 IF X[i]=Y[j] THEN s=0 ELSE s=1;
7 D[i][j]=min{D[i-1][j-1]+s,D[i-1][j]+1,D[i][j-1]+1};
8 return D[m][n];

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 62
vi
Minimum Edit Distance: Beispiel (II)
X[1…i]
D 0 1 2 3 4 5 6 7 8
X[1… 8] = ein Test 0 0 1 2 3 4 5 6 7 8
1
Y[1…10] = zwei Feste 1 1
2 2
3 3
i=1: FOR-Schleife für j (5-7)

Y[1…j]
4 4
j=1: X[1]=e ≠ z=Y[1] ⟹ s=1 5 5
D[1][1]=min{0+1,1+1,1+1}=1 6 6
7 7
MinEditDist(X,Y,m,n) // X=X[1…m], Y=Y[1…n]
8 8
1 D[][]=ALLOC(m,n);
9 9
2 FOR i=0 TO m DO D[i][0]=i;
10 10
3 FOR j=0 TO n DO D[0][j]=j;
4 FOR i=1 TO m DO
5 FOR j=1 TO n DO
6 IF X[i]=Y[j] THEN s=0 ELSE s=1;
7 D[i][j]=min{D[i-1][j-1]+s,D[i-1][j]+1,D[i][j-1]+1};
8 return D[m][n];

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 63
vi
Minimum Edit Distance: Beispiel (III)
X[1…i]
D 0 1 2 3 4 5 6 7 8
X[1… 8] = ein Test 0 0 1 2 3 4 5 6 7 8
1 1
Y[1…10] = zwei Feste 1
2 2 2
3 3
i=1: FOR-Schleife für j (5-7)

Y[1…j]
4 4
j=2: X[1]=e ≠ w=Y[2] ⟹ s=1 5 5
D[1][2]=min{1+1,2+1,1+1}=2 6 6
7 7
MinEditDist(X,Y,m,n) // X=X[1…m], Y=Y[1…n]
8 8
1 D[][]=ALLOC(m,n);
9 9
2 FOR i=0 TO m DO D[i][0]=i;
10 10
3 FOR j=0 TO n DO D[0][j]=j;
4 FOR i=1 TO m DO
5 FOR j=1 TO n DO
6 IF X[i]=Y[j] THEN s=0 ELSE s=1;
7 D[i][j]=min{D[i-1][j-1]+s,D[i-1][j]+1,D[i][j-1]+1};
8 return D[m][n];

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 64
vi
Minimum Edit Distance: Beispiel (IV)
X[1…i]
D 0 1 2 3 4 5 6 7 8
X[1… 8] = ein Test 0 0 1 2 3 4 5 6 7 8
1 1
Y[1…10] = zwei Feste 1
2 2 2
3 3 2
i=1: FOR-Schleife für j (5-7)

Y[1…j]
4 4
j=3: X[1]=e = e=Y[3] ⟹ s=0 5 5
D[1][3]=min{2+0,3+1,2+1}=2 6 6
7 7
MinEditDist(X,Y,m,n) // X=X[1…m], Y=Y[1…n]
8 8
1 D[][]=ALLOC(m,n);
9 9
2 FOR i=0 TO m DO D[i][0]=i;
10 10
3 FOR j=0 TO n DO D[0][j]=j;
4 FOR i=1 TO m DO
5 FOR j=1 TO n DO
6 IF X[i]=Y[j] THEN s=0 ELSE s=1;
7 D[i][j]=min{D[i-1][j-1]+s,D[i-1][j]+1,D[i][j-1]+1};
8 return D[m][n];

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 65
vi
Minimum Edit Distance: Beispiel (V)
X[1…i]
D 0 1 2 3 4 5 6 7 8
X[1… 8] = ein Test 0 0 1 2 3 4 5 6 7 8
1 1 2
Y[1…10] = zwei Feste 1
2 2 2 2
3 3 2 3
i=2: FOR-Schleife für j (5-7)

Y[1…j]
4 4 3 2
j=4: X[2]=i = i=Y[4] ⟹ s=0 5 5 4
D[2][4]=min{2+0,3+1,3+1}=2 6 6 5
7 7 6
MinEditDist(X,Y,m,n) // X=X[1…m], Y=Y[1…n]
8 8 7
1 D[][]=ALLOC(m,n);
9 9 8
2 FOR i=0 TO m DO D[i][0]=i;
10 10 9
3 FOR j=0 TO n DO D[0][j]=j;
4 FOR i=1 TO m DO
5 FOR j=1 TO n DO
6 IF X[i]=Y[j] THEN s=0 ELSE s=1;
7 D[i][j]=min{D[i-1][j-1]+s,D[i-1][j]+1,D[i][j-1]+1};
8 return D[m][n];

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 66
vi
Minimum Edit Distance: Beispiel (VI)
X[1…i]
D 0 1 2 3 4 5 6 7 8
X[1… 8] = ein Test 0 0 1 2 3 4 5 6 7 8
1 1 2 3 4 5 6 7 8
Y[1…10] = zwei Feste 1
2 2 2 2 3 4 5 6 7 8
3 3 2 3 3 4 5 5 6 7

Y[1…j]
4 4 3 2 3 4 5 6 6 7
5 5 4 3 3 3 4 5 6 7
6 6 5 4 4 4 4 5 6 7
7 7 6 5 5 5 5 4 5 6
MinEditDist(X,Y,m,n) // X=X[1…m], Y=Y[1…n]
8 8 7 6 6 6 6 5 4 5
1 D[][]=ALLOC(m,n);
9 9 8 7 7 7 7 6 5 4
2 FOR i=0 TO m DO D[i][0]=i;
10 10 9 8 8 8 8 7 6 5
3 FOR j=0 TO n DO D[0][j]=j;
4 FOR i=1 TO m DO
5 FOR j=1 TO n DO
6 IF X[i]=Y[j] THEN s=0 ELSE s=1;
7 D[i][j]=min{D[i-1][j-1]+s,D[i-1][j]+1,D[i][j-1]+1};
8 return D[m][n];

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 67
vi
Minimum Edit Distance: Beispiel (VII)
X[1…i]
D 0 1 2 3 4 5 6 7 8
Rückwärtsschrittfolge 0 0 1 2 3 4 5 6 7 8
D[m][n] zu D[0][0] entlang 1 1 1 2 3 4 5 6 7 8
der ausgewählten Minima 2 2 2 2 3 4 5 6 7 8
(bzw. bis Rand erreicht) 3 3 2 3 3 4 5 5 6 7

Y[1…j]
gibt Operationen an: 4 4 3 2 3 4 5 6 6 7
5 5 4 3 3 3 4 5 6 7
6 6 5 4 4 4 4 5 6 7
(↘) : copy (±0) 7 7 6 5 5 5 5 4 5 6
↘ : sub (+1) 8 8 7 6 6 6 6 5 4 5
⟶ : del 9 9 8 7 7 7 7 6 5 4
↓ : ins 10 10 9 8 8 8 8 7 6 5

(Im Allgemeinen gibt es

mehrere mögliche Sequenzen!)

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 68
vi
Minimum Edit Distance: Beispiel (VIII)
(↘) c, ↘ s, ⟶ d, X[1…i]
↓i D 0 1 2 3 4 5 6 7 8

ein£Test 0 0 1 2 3 4 5 6 7 8
↓ zein£Test 1 1 1 2 3 4 5 6 7 8
↓ zwein£Test 2 2 2 2 3 4 5 6 7 8
(↘) zwein£Test 3 3 2 3 3 4 5 5 6 7

Y[1…j]
(↘) zwein£Test 4 4 3 2 3 4 5 6 6 7
⟶ zwei£Test 5 5 4 3 3 3 4 5 6 7
(↘) zwei£Test
6 6 5 4 4 4 4 5 6 7
↘ zwei£Fest
7 7 6 5 5 5 5 4 5 6
(↘) zwei£Fest
8 8 7 6 6 6 6 5 4 5
(↘) zwei£Fest
(↘) zwei£Fest 9 9 8 7 7 7 7 6 5 4
↓ zwei£Feste 10 10 9 8 8 8 8 7 6 5

nach Operation verbleibendes X[i+1…n]

⟶ zwei£Test
erstelltes Y[1…j]

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 69
vi
 Geben Sie zwei Strings an, die durch verschiedene Sequenzen
von Operationen mit gleicher Levenshtein-Distanz ineinander
übergeführt werden können

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 70
vi
 Greedy-Algorithmen

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 71
vi
Greedy-Algorithmen

Prinzip Greedy:

Finde Lösung 𝑥 = (𝑥" , 𝑥# , … , 𝑥$ )

indem Teillösung 𝑥" , 𝑥# , … , 𝑥'%" durch Kandidaten 𝑥'

ergänzt wird,

der lokal am günstigsten erscheint.

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 72
vi
„Unsere“ Greedy-Algorithmen…
(auch Prim)
Dijkstra-SSSP(G,s,w)

1 initSSSP(G,s,w);
2 Q=V; //let S=V-Q wähle jeweils Knoten,
3 WHILE !isEmpty(Q) DO der kürzeste Distanz hat
4 u=EXTRACT-MIN(Q); //wrt. dist
5 FOREACH v in adj(u) DO
6 relax(G,u,v,w);

MST-Kruskal(G,w) // G=(V,E) undirected, connected graph

w weight function
1 A=∅
2 FOREACH v in V DO set(v)={v};
3 Sort edges according to weight in nondecreasing order
4 FOREACH {u,v} in E according to order DO
5 IF set(u)!=set(v) THEN
6 A = A ∪{{u,v}} Wähle jeweils
7 UNION(G,u,v); leichteste Kante
8 return A

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 73
vi
…funktionieren oft, aber nicht immer
Dijkstra-SSSP(G,s,w)

1 initSSSP(G,s,w);
2 Q=V; //let S=V-Q
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //wrt. dist
5 FOREACH v in adj(u) DO
6 relax(G,u,v,w);
1
kürzester Weg 1®5 via 2 3
1® 2 ® 4 ® 3 ® 5 6
mit Gewicht 6+2-5+0=3 -5
2
1 4

0
Dijkstra-Algorithmus: 5
1®5 mit Gewicht 5 5

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 74
vi
Traveling Salesperson Problem (TSP)
Traveling Salesperson Problem:
Gegeben vollständiger (un-)gerichteter Graph 𝐺 = 𝑉, 𝐸 mit Kantenge-
wichten 𝑤: 𝐸 → ℝ, finde Tour 𝑝 mit minimalem Kantengewicht 𝑤(𝑝).
Eine Tour ist ein Weg 𝑝 = (𝑣! , 𝑣" , … , 𝑣$%" , 𝑣$ ) entlang der Kanten
(𝑣' , 𝑣'/" ) ∈ 𝐸 für 𝑖 = 0,1,2, … 𝑛 − 1, der bis auf Start- und Endknoten
𝑣! = 𝑣$ jeden Knoten genau einmal besucht.

Graph 𝐺 = 𝑉, 𝐸 ist vollständig, wenn 2

2 3
es für alle Knoten 𝑢, 𝑣 ∈ 𝑉 mit 𝑢 ≠ 𝑣 1 4
eine Kante (𝑢, 𝑣) ∈ 𝐸 gibt 6 4

Wenn Graph nicht vollständig, aber Tour hat, 1

1 4
kann man „verboten teure“ Kanten (𝑢, 𝑣) mit 2 8
𝑤 (𝑢, 𝑣) = 𝑉 : max |𝑤 𝑒 | + 1 hinzufügen
7∈U 5 7
5

Tour 1®5®2®3®4®1 mit Gewicht 14

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 75
vi
TSP vs. Dijkstra
löst anderes Problem

Allgemeiner TSP-Algorithmus: Dijsktra-Algorithmus:

finde optimale Route, finde optimalen Pfad vom

die durch jeden Ausgangspunkt aus
Knoten geht und zum
Ausgangspunkt zurückkehrt (besucht evtl. nicht alle Knoten
und betrachtet auch nicht Rückkehr)

Ansatz Greedy-Algorithmus für TSP:

Starte mit beliebigem oder gegebenem Knoten.
Nimm vom gegenwärtigen Knoten aus die Kante
zu noch nicht besuchtem Knoten, die kleinstes Gewicht hat.
Wenn kein Knoten mehr übrig, gehe zu Startpunkt zurück.
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 76
vi
Greedy-TSP
Greedy-TSP(G,s,w) // |V|=n, s starting node

1 FOREACH v in V DO [Link]=white;
2 tour[]=ALLOC(n); tour[0]=s; tour[0].color=gray;
3 FOR i=1 TO n-1 DO
4 tour[i]=EXTRACT-MIN(adj(tour[i-1]));
//get (white) neighbor with minimum edge weight
5 tour[i].color=gray;
6 return tour;

Ansatz Greedy-Algorithmus für TSP:

Starte mit beliebigem oder gegebenem Knoten.
Nimm vom gegenwärtigen Knoten aus die Kante
zu noch nicht besuchtem Knoten, die kleinstes Gewicht hat.
Wenn kein Knoten mehr übrig, gehe zu Startpunkt zurück.
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 77
vi
Greedy-TSP ist zu gierig (I)
Betrachte vollständigen Graphen mit Knoten 𝑉 = {1,2,3, … , 𝑛}, 𝑛 ≥ 3,
und folgenden Kantengewichten für beliebig große Konstante 𝑁:
1 1 ≤ 𝑖, 𝑗 ≤ 𝑛, 𝑗 = 𝑖 + 1
𝑤 {𝑖, 𝑗} = 𝑁 𝑖 = 1, 𝑗 = 𝑛 Startknoten 𝑠 = 1
2 𝑠𝑜𝑛𝑠𝑡

1
2 3
2 2
Optimale Tour mit Startknoten 𝑠 = 1 1 1

1®2®… ® 𝑛 − 2 ® 𝑛 ® 𝑛 − 1 ®1 2
1 4
2 2
hat Gewicht
𝑁 5 1
1 + 1 + ⋯+ 1 + 2 + 1 + 2 = 𝑛 + 2
Beispiel: 𝑛 = 5
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 78
vi
Greedy-TSP ist zu gierig (II)
Betrachte vollständigen Graphen mit Knoten 𝑉 = {1,2,3, … , 𝑛}, 𝑛 ≥ 3,
und folgenden Kantengewichten für beliebig große Konstante 𝑁:
1 1 ≤ 𝑖, 𝑗 ≤ 𝑛, 𝑗 = 𝑖 + 1
𝑤 {𝑖, 𝑗} = 𝑁 𝑖 = 1, 𝑗 = 𝑛 Startknoten 𝑠 = 1
2 𝑠𝑜𝑛𝑠𝑡

1
2 3
Greedy-Algorithmus läuft zunächst 2 2
1 1
1®2®… ® 𝑛 − 1 ® 𝑛,
2
1 4
muss dann die „teure“ Kante 𝑛 ® 1 2 2
nehmen, erreicht also nur Gewicht 𝑁 5 1

1 + 1 + ⋯+ 1 + 𝑁 = 𝑁 + 𝑛 − 1 Beispiel: 𝑛 = 5
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 79
vi
Effizienter Algorithmus für TSP?

TSP(G,w,s)

???

Vermutlich schwierig, effizienten Algorithmus zu finden

® siehe Kapitel 8 über NP

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 80
vi
 Metaheuristiken

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 81
vi
Heuristiken und Metaheuristiken

Heuristik: Metaheuristik:

dedizierter Suchalgorithmus
für Optimierungsproblem, allgemeine Vorgehensweise,
um Suche für beliebige
der gute (aber evtl. nicht optimale) Optimierungsprobleme
Lösung für spezielles Problem findet zu leiten

problem-abhängig, problem-unabhängig,
arbeitet direkt „am“ Problem arbeitet mit abstrakten Problemen

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 82
vi
Lokale Suche

Güte der Lösung

1. Finde erste Lösung

2. suche in Nähe bessere Lösungen,

bis keine Verbesserung mehr (oder Zeit um)
Lösungen

„Hill-Climbing-Strategie“
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 83
vi
Hill-Climbing-Algorithmus

HillClimbing(P) // maxTime constant wähle

initiale Lösung
1 sol=initialSol(P);
2 time=0;
3 WHILE time<maxTime DO ändere Lösung
4 new=perturb(P,sol); leicht ab
5 IF quality(P,new)>quality(P,sol) THEN
6 sol=new; ersetze aktuelle
7 time=time+1; Lösung durch neu,
8 return sol; falls diese besser ist

Beispiel TSP:
initSol: wähle beliebige Tour, z.B. per Greedy-Algorithmus
perturb: wähle zwei Knoten u,v zufällig und tausche sie in Tour
quality: (negatives) Gewicht der aktuellen Tour

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 84
vi
Hill-Climbing-Algorithmus für TSP

1 1
2 3 wenn 4,5 2 3
2 2 gewählt 2 2
1 1 1 1

2 2
1 4 1 4
2 2 2 2
𝑁 5 1 𝑁 5 1

Greedy-Lösung optimale Lösung

Beispiel TSP:
initSol: wähle beliebige Tour, z.B. per Greedy-Algorithmus
perturb: wähle zwei Knoten u,v zufällig und tausche sie in Tour
quality: (negatives) Gewicht der aktuellen Tour

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 85
vi
Lokale vs. globale Maxima

Güte der Lösung globales Maximum

lokales Maximum

Lösungen

Eventuell bleibt Hill-Climbing-Algorithmus in lokalem Maximum hängen,

da stets nur leichte Lösungsänderungen in aufsteigender Richtung!
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 86
vi
Lokale vs. globale Maxima beim TSP (I)
2
1 1 1 TSP auf gerichtetem Graphen
1 2 3 4 Alle anderen Kanten Gewicht 𝑁
Startknoten 1
2 2
5

optimale Lösung Greedy-Lösung

1®2®5®3®4®1 mit Gewicht 8 1®2®3®4®5®1 mit Gewicht 2N+3
2 2
1 1 1 1 1 1
1 2 3 4 1 2 3 4

2 2 2 2
N N
5 5

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 87
vi
Lokale vs. globale Maxima beim TSP (II)

Umgebung der Greedy-Lösung durch Vertauschen

zweier Knoten gegeben (Startknoten bleibt fix):

1®3®2®4®5®1 mit Gewicht 5N

1®4®3®2®5®1 mit Gewicht 4N+2 Greedy-Lösung
1®5®3®4®2®1 mit Gewicht 3N+3 1®2®3®4®5®1 mit Gewicht 2N+3
1®2®4®3®5®1 mit Gewicht 4N+1
2
1®2®5®4®3®1 mit Gewicht 3N+3
1 1 1
1®2®3®5®4®1 mit Gewicht 2N+4 1 2 3 4

Hill-Climbing findet 2 2
keine bessere Lösung in der Nähe N N
® Greedy-Lösung lokales Max (bzw. Min) 5

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 88
vi
Lokale vs. globale Maxima beim TSP (III)
optimale Lösung 2
1®2®5®3®4®1 mit Gewicht 8 1 1 1
1 2 3 4

2 2
2
5
1 1 1 Tausche
1 2 3 4 3 und 5
N Greedy-Lösung
2 2
N 1®2®3®4®5®1 mit Gewicht 2N+3
5
2
1 1 1
1®2®3®5®4®1 mit Gewicht 2N+4 1 2 3 4

2 2
N N
5
Tausche 4 und 5
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 89
vi
Lokale vs. globale Maxima beim TSP (IV)
Optimale Lösung
1®2®5®3®4®1
Greedy Lösung mit Gewicht 8
1®2®3®4®5®1
mit Gewicht 2N+3

lokaler
Suchbereich
Zwischenlösung
1®2®3®5®4®1
mit Gewicht 2N+4

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 90
vi
Iterative Lokale Suche Problem: „zufällige“ (?) Lösungen
könnten auch schlecht sein

1b. Finde erste Lösung

Güte der Lösung
1a. Finde erste Lösung

2b. suche in Nähe

2a. suche in Nähe bessere Lösungen,

bis keine Verbesserung mehr (oder Zeit um)
Lösungen

Beginne Suche nochmal von vorne, z.B. mit neuer zufälliger Lösung,
akzeptiere beste gefundene Lösung
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 91
vi
Simulated Annealing
„Annealing“ in Metallverarbeitung:
Härten von Metallen durch Erhitzen auf hohe Temperatur
und langsames Abkühlen

je nach Temperatur

1. Temperatur zu Beginn hoch, kühlt langsam ab

2. Je höher Temperatur, desto wahrscheinlicher „Sprung in schlechte Richtung“

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 92
vi
„In schlechte Richtung“ mit Wahrscheinlichkeit
Ansatz: akzeptiere auch schlechtere Lösung new mit
quality(new)<quality(sol) mit Wahrscheinlichkeit:

1 ƒ„…†‡ˆ‰ oŠ‹ pƒ„…†‡ˆ‰(Œ•†)

Wahrscheinlichkeit

𝑒 ˆŠŽ•Š•…ˆ„•Š

Exponent
heiße Temperatur (zu Beginn):
akzeptiere oft viel schlechtere Lösungen
kühlere Temperatur (am Ende):
akzeptiere selbst unwesentlich schlechtere Lösungen fast nie
(am Ende also quasi Hill-Climbing)
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 93
vi
Simulated Annealing

SimulatedAnnealing(P) // maxTime constant

// TempSched[] temparature annealing

1 sol=initialSol(P);
2 time=0; uniformer Wert
3 WHILE time<maxTime DO zwischen 0 und 1
4 new=perturb(P,sol);
5 temperature=TempSched[time];
6 d=quality(P,new)-quality(P,sol); r=random(0,1);
7 IF d>0 OR r<=exp(d/temperature) THEN
8 sol=new;
9 time=time+1;
10 return sol;

Bestimmung eines guten „Annealing schedule“ (Starttemperatur und Abnahme)

betrachten wir hier in der Vorlesung nicht weiter

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 94
vi
Simulated Annealing beim TSP
2
Starttemperatur 1 1 1
= max{𝑤 𝑒 } = 𝑁 = 1000 1 2 3 4
0∈2
2 2
lineare Temperaturabnahme = 𝑁/2𝑛 = 100 5

Aktuelle Lösung Gewicht Zuf. Gew. Temp Zuf. Exp Neue Löung
Tausch nach Wert r (-d/temp) akzeptiert?
Tausch
1 1®2®3®4®5®1 2N+3 2 und 3 5N 1000 0.37 0.0498 nein

2 1®2®3®4®5®1 2N+3 2 und 4 4N+2 900 0.60 0.1084 nein

3 1®2®3®4®5®1 2N+3 4 und 5 2N+4 800 0.17 0.9986 ja (Zufall)

4 1®2®3®5®4®1 2N+4 2 und 4 5N 700 0.34 0.0138 nein

5 1®2®3®5®4®1 2N+4 3 und 4 3N+3 600 0.45 0.1889 nein

6 1®2®3®5®4®1 2N+4 3 und 5 8 500 0.78 – ja (besser)

7 1®2®5®3®4®1 8 2 und 5 2N+4 400 0.51 0.0067

Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 95
vi nein
Weitere Metaheuristiken
Tabu Search Evolutionäre Algorithmen

Ausgehend von Beginne mit Lösungspopulation

aktueller Lösung, suche
bessere Lösung in der Nähe Wähle beste Lösungen zur
Reproduktion aus
Speichere eine Zeit lang
schon besuchte Lösungen, Bilde durch Überkreuzungen
und vermeide diese Lösungen und Mutationen der
besten Lösungen
Wenn keine bessere Lösung neue Lösungen
in der Nähe, akzeptiere auch
schlechtere Lösung Ersetze schlechteste Lösungen
durch diese neuen Lösungen

+Schwarmoptimierung, Ameisenkolonialisierung,…
Algorithmen und Datenstrukturen | Stefan Roth & Zsolt István | SS 25 | 07 Fortgeschrittene Algorithmen-Entwurfsmethoden | 96
vi