Universitat Bielefeld

AngewandteInformatik

“Komplizierte Probleme” der Informatik

Marc Hanheide

Juli 2003

KomplexitätsklassenLösungstrategien

TSPZusammenfassung

Randomisierte Algorithmen

Universitat Bielefeld

AngewandteInformatik Problemklassen

• EXPTIME: exponentiell• NP: nichtdeterministisch polynomial

(Rucksackproblem, Traveling Salesman Problem,Erfüllbarkeit)

• P: determinitisch polynomial ( Sortieren, usw. )

• Für Probleme in EXPTIME besteht keine Hoffnung auf effiziente Algorithmen

• Probleme aus NP können in polynomialer Zeit mit einem nichtdeterministischenAlgorithmus gelöst werden.

• Für kein NP-hartes Problem konnte bisher ein deterministischer polynomialerAlgorithmus gefunden werden

• Große Frage der theoretischen Informatik: NP = P ? (1 Mio $ von ClayMathematics Institute)

“Komplizierte Probleme” ∧ ∨ > � � 1

Universitat Bielefeld

AngewandteInformatik Ein Beispiel: Weltreiseproblem (TSP)

Aufgabe: Plündere alle 193 Staatender Erde auf der kürzesten Strecke!

kürzester Weg über alle Knoten eines Graphen mit gewichteten Kanten

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 2

Universitat Bielefeld

AngewandteInformatik Ein Beispiel: Weltreiseproblem (TSP)

Aufgabe: Plündere alle 193 Staatender Erde auf der kürzesten Strecke!

kürzester Weg über alle Knoten eines Graphen mit gewichteten Kanten

• Weltreise durch alle 193 Länder⇒ 192!= 3.549967931·10356 mögliche Routen

• Universum hat 6·1077 Atome und ist erst 12,5·109 Jahre alt

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 2

Universitat Bielefeld

AngewandteInformatik Ein Beispiel: Weltreiseproblem (TSP)

Aufgabe: Plündere alle 193 Staatender Erde auf der kürzesten Strecke!

kürzester Weg über alle Knoten eines Graphen mit gewichteten Kanten

• Weltreise durch alle 193 Länder⇒ 192!= 3.549967931·10356 mögliche Routen

• Universum hat 6·1077 Atome und ist erst 12,5·109 Jahre alt

• exakte Lösung so nicht berechenbar ( O((n−1)!/2))

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 2

Universitat Bielefeld

AngewandteInformatik Ein Beispiel: Weltreiseproblem (TSP)

Aufgabe: Plündere alle 193 Staatender Erde auf der kürzesten Strecke!

kürzester Weg über alle Knoten eines Graphen mit gewichteten Kanten

• Weltreise durch alle 193 Länder⇒ 192!= 3.549967931·10356 mögliche Routen

• Universum hat 6·1077 Atome und ist erst 12,5·109 Jahre alt

• exakte Lösung so nicht berechenbar ( O((n−1)!/2)) Was tun?

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 2

Universitat Bielefeld

AngewandteInformatik Lösungsansätze NP-harter Probleme

Subklassenidentifikation Viele auftretende Probleme sind in der realen Anwendungan Vorbedingungen geknüpft, die das Problem zum Teil erheblich vereinfachen.

Randomisierung Vermeidung „ungeschickter” Ausgangskonfigurationen durchZufallsverteilung, verbessert nicht die worst-case-Komplexität, aber den average-case. → Mathias Katzer

Approximation Durch effizientere Verfahren eine Lösung ermitteln, die nur um einenbestimmten Fehler von der optimalen Lösung abweicht

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 3

Universitat Bielefeld

AngewandteInformatik Lösungsansätze NP-harter Probleme

Subklassenidentifikation Viele auftretende Probleme sind in der realen Anwendungan Vorbedingungen geknüpft, die das Problem zum Teil erheblich vereinfachen.

Randomisierung Vermeidung „ungeschickter” Ausgangskonfigurationen durchZufallsverteilung, verbessert nicht die worst-case-Komplexität, aber den average-case. → Mathias Katzer

Approximation Durch effizientere Verfahren eine Lösung ermitteln, die nur um einenbestimmten Fehler von der optimalen Lösung abweicht

Ein Standardapproximationsverfahren ist die Klasse der „greedy” (gierigen)Algorithmen:

• ermittelt immer die lokale beste Lösung, u. U. auf Kosten eines schlechterenGesamtergebnisses (daher gierig)

• vorwiegend für Optimierungsaufgaben (Minimum, Maximum eingesetzt)• lokale Optimierung führt (hoffentlich) zu guter globaler Approximation

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 3

Universitat Bielefeld

AngewandteInformatik Approximation des TSP-Problems I

Berechne Minimal-spanning-Tree [Prim, 1957]. . .

• Wähle eine Startknoten

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 4

Universitat Bielefeld

AngewandteInformatik Approximation des TSP-Problems I

Berechne Minimal-spanning-Tree [Prim, 1957]. . .

• Wähle eine Startknoten

• Wähle kürzeste verfügbare Kante, dienicht behandelte, erreichbare Knotenmit bereits verarbeiteten verbindet

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 4

Universitat Bielefeld

AngewandteInformatik Approximation des TSP-Problems I

Berechne Minimal-spanning-Tree [Prim, 1957]. . .

• Wähle eine Startknoten

• Wähle kürzeste verfügbare Kante, dienicht behandelte, erreichbare Knotenmit bereits verarbeiteten verbindet

• Füge nächsten Knoten demLösungsgraphen hinzu

• Ende, wenn alle Knoten bearbeitet

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 4

Universitat Bielefeld

AngewandteInformatik Approximation des TSP-Problems I

Berechne Minimal-spanning-Tree [Prim, 1957]. . .

• Wähle eine Startknoten

• Wähle kürzeste verfügbare Kante, dienicht behandelte, erreichbare Knotenmit bereits verarbeiteten verbindet

• Füge nächsten Knoten demLösungsgraphen hinzu

• Ende, wenn alle Knoten bearbeitet

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 4

Universitat Bielefeld

AngewandteInformatik Approximation des TSP-Problems I

Berechne Minimal-spanning-Tree [Prim, 1957]. . .

• Wähle eine Startknoten

• Wähle kürzeste verfügbare Kante, dienicht behandelte, erreichbare Knotenmit bereits verarbeiteten verbindet

• Füge nächsten Knoten demLösungsgraphen hinzu

• Ende, wenn alle Knoten bearbeitet

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 4

Universitat Bielefeld

AngewandteInformatik Approximation des TSP-Problems I

Berechne Minimal-spanning-Tree [Prim, 1957]. . .

• Wähle eine Startknoten

• Wähle kürzeste verfügbare Kante, dienicht behandelte, erreichbare Knotenmit bereits verarbeiteten verbindet

• Füge nächsten Knoten demLösungsgraphen hinzu

• Ende, wenn alle Knoten bearbeitet

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 4

Universitat Bielefeld

AngewandteInformatik Approximation des TSP-Problems I

Berechne Minimal-spanning-Tree [Prim, 1957]. . .

• Wähle eine Startknoten

• Wähle kürzeste verfügbare Kante, dienicht behandelte, erreichbare Knotenmit bereits verarbeiteten verbindet

• Füge nächsten Knoten demLösungsgraphen hinzu

• Ende, wenn alle Knoten bearbeitet

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 4

Universitat Bielefeld

AngewandteInformatik Approximation des TSP-Problems I

Berechne Minimal-spanning-Tree [Prim, 1957]. . .

• Wähle eine Startknoten

• Wähle kürzeste verfügbare Kante, dienicht behandelte, erreichbare Knotenmit bereits verarbeiteten verbindet

• Füge nächsten Knoten demLösungsgraphen hinzu

• Ende, wenn alle Knoten bearbeitet

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 4

Universitat Bielefeld

AngewandteInformatik Approximation des TSP-Problems I

Berechne Minimal-spanning-Tree [Prim, 1957]. . .

• Wähle eine Startknoten

• Wähle kürzeste verfügbare Kante, dienicht behandelte, erreichbare Knotenmit bereits verarbeiteten verbindet

• Füge nächsten Knoten demLösungsgraphen hinzu

• Ende, wenn alle Knoten bearbeitet

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 4

Universitat Bielefeld

AngewandteInformatik Approximation des TSP-Problems I

Berechne Minimal-spanning-Tree [Prim, 1957]. . .

• Wähle eine Startknoten

• Wähle kürzeste verfügbare Kante, dienicht behandelte, erreichbare Knotenmit bereits verarbeiteten verbindet

• Füge nächsten Knoten demLösungsgraphen hinzu

• Ende, wenn alle Knoten bearbeitet

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 4

Universitat Bielefeld

AngewandteInformatik Approximation des TSP-Problems I

Berechne Minimal-spanning-Tree [Prim, 1957]. . .

• Wähle eine Startknoten

• Wähle kürzeste verfügbare Kante, dienicht behandelte, erreichbare Knotenmit bereits verarbeiteten verbindet

• Füge nächsten Knoten demLösungsgraphen hinzu

• Ende, wenn alle Knoten bearbeitet

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 4

Universitat Bielefeld

AngewandteInformatik Approximation des TSP-Problems I

Berechne Minimal-spanning-Tree [Prim, 1957]. . .

• Wähle eine Startknoten

• Wähle kürzeste verfügbare Kante, dienicht behandelte, erreichbare Knotenmit bereits verarbeiteten verbindet

• Füge nächsten Knoten demLösungsgraphen hinzu

• Ende, wenn alle Knoten bearbeitet

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 4

Universitat Bielefeld

AngewandteInformatik Approximation des TSP-Problems I

Berechne Minimal-spanning-Tree [Prim, 1957]. . .

• Wähle eine Startknoten

• Wähle kürzeste verfügbare Kante, dienicht behandelte, erreichbare Knotenmit bereits verarbeiteten verbindet

• Füge nächsten Knoten demLösungsgraphen hinzu

• Ende, wenn alle Knoten bearbeitet

• Laufzeit: O(n2)

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 4

Universitat Bielefeld

AngewandteInformatik Approximation des TSP-Problems II

. . . und traversiere den Baum

d

c

a

f

eb

a• Traversiere depth-first ausgehend

vom Startpunkt

• Überspringe bereits besuchte Knoten

• Lösung: Rmst = (a

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 5

Universitat Bielefeld

AngewandteInformatik Approximation des TSP-Problems II

. . . und traversiere den Baum

d

c

a

f

eb

a

d

c

a

f

eb

a

c

• Traversiere depth-first ausgehendvom Startpunkt

• Überspringe bereits besuchte Knoten

• Lösung: Rmst = (a,c

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 5

Universitat Bielefeld

AngewandteInformatik Approximation des TSP-Problems II

. . . und traversiere den Baum

d

c

a

f

eb

a

d

c

a

f

eb

a

c

d

c

a

f

eb

a

c

d

• Traversiere depth-first ausgehendvom Startpunkt

• Überspringe bereits besuchte Knoten

• Lösung: Rmst = (a,c,d

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 5

Universitat Bielefeld

AngewandteInformatik Approximation des TSP-Problems II

. . . und traversiere den Baum

d

c

a

f

eb

a

d

c

a

f

eb

a

c

d

c

a

f

eb

a

c

dd

c

a

f

eb

a

c

d

f

• Traversiere depth-first ausgehendvom Startpunkt

• Überspringe bereits besuchte Knoten

• Lösung: Rmst = (a,c,d, f

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 5

Universitat Bielefeld

AngewandteInformatik Approximation des TSP-Problems II

. . . und traversiere den Baum

d

c

a

f

eb

a

d

c

a

f

eb

a

c

d

c

a

f

eb

a

c

dd

c

a

f

eb

a

c

d

f

d

c

a

f

eb

a

c

d

f

b

• Traversiere depth-first ausgehendvom Startpunkt

• Überspringe bereits besuchte Knoten

• Lösung: Rmst = (a,c,d, f ,b

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 5

Universitat Bielefeld

AngewandteInformatik Approximation des TSP-Problems II

. . . und traversiere den Baum

d

c

a

f

eb

a

d

c

a

f

eb

a

c

d

c

a

f

eb

a

c

dd

c

a

f

eb

a

c

d

f

d

c

a

f

eb

a

c

d

f

bd

c

a

f

eb

a

c

d

f

b e

• Traversiere depth-first ausgehendvom Startpunkt

• Überspringe bereits besuchte Knoten

• Lösung: Rmst = (a,c,d, f ,b,e

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 5

Universitat Bielefeld

AngewandteInformatik Approximation des TSP-Problems II

. . . und traversiere den Baum

d

c

a

f

eb

a

d

c

a

f

eb

a

c

d

c

a

f

eb

a

c

dd

c

a

f

eb

a

c

d

f

d

c

a

f

eb

a

c

d

f

bd

c

a

f

eb

a

c

d

f

b ed

c

a

f

eb

a

c

d

f

b e

• Traversiere depth-first ausgehendvom Startpunkt

• Überspringe bereits besuchte Knoten

• Lösung: Rmst = (a,c,d, f ,b,e,a)

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 5

Universitat Bielefeld

AngewandteInformatik Approximation des TSP-Problems II

. . . und traversiere den Baum

d

c

a

f

eb

a

d

c

a

f

eb

a

c

d

c

a

f

eb

a

c

dd

c

a

f

eb

a

c

d

f

d

c

a

f

eb

a

c

d

f

bd

c

a

f

eb

a

c

d

f

b ed

c

a

f

eb

a

c

d

f

b e

• Traversiere depth-first ausgehendvom Startpunkt

• Überspringe bereits besuchte Knoten

• Lösung: Rmst = (a,c,d, f ,b,e,a)

• Laufzeit: O(n)

• Qualität der Approximation:

l(Rmst)≤ 2l(Ropt)

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 5

Universitat Bielefeld

AngewandteInformatik Approximation des TSP-Problems II

. . . und traversiere den Baum

d

c

a

f

eb

a

d

c

a

f

eb

a

c

d

c

a

f

eb

a

c

dd

c

a

f

eb

a

c

d

f

d

c

a

f

eb

a

c

d

f

bd

c

a

f

eb

a

c

d

f

b ed

c

a

f

eb

a

c

d

f

b e

DEMO

• Traversiere depth-first ausgehendvom Startpunkt

• Überspringe bereits besuchte Knoten

• Lösung: Rmst = (a,c,d, f ,b,e,a)

• Laufzeit: O(n)

• Qualität der Approximation:

l(Rmst)≤ 2l(Ropt)

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 5

Universitat Bielefeld

AngewandteInformatik Approximation des TSP-Problems II

. . . und traversiere den Baum

d

c

a

f

eb

a

d

c

a

f

eb

a

c

d

c

a

f

eb

a

c

dd

c

a

f

eb

a

c

d

f

d

c

a

f

eb

a

c

d

f

bd

c

a

f

eb

a

c

d

f

b ed

c

a

f

eb

a

c

d

f

b e

DEMO

• Traversiere depth-first ausgehendvom Startpunkt

• Überspringe bereits besuchte Knoten

• Lösung: Rmst = (a,c,d, f ,b,e,a)

• Laufzeit: O(n)

• Qualität der Approximation:

l(Rmst)≤ 2l(Ropt)

• Jan Schäfer: genetischer Algorithmus

& DEMO

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 5

Universitat Bielefeld

AngewandteInformatik TSP-Anwendungen

• Schweißroboter: Trajektorienplanung

• Process-Scheduling

• Platinenlayout

• Flugrouten

• Navigationssysteme

• Basis für viele andere geometrische Algorithmen

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 6

Universitat Bielefeld

AngewandteInformatik TSP-Anwendungen

• Schweißroboter: Trajektorienplanung

• Process-Scheduling

• Platinenlayout

• Flugrouten

• Navigationssysteme

• Basis für viele andere geometrische Algorithmen

• und natürlich: Raubzüge

“Komplizierte Probleme” � ≺ < ∧ ∨ > � � 6

Universitat Bielefeld

AngewandteInformatik Take-Home-Messages

• Beweist NP= P oder NP 6= P und Ihr seid reich

• Findet gute Approximationsalgorithmen für NP-harte Probleme

• Vermeidet NP-harte Probleme

“Komplizierte Probleme” � ≺ < ∧ ∨ 7

Universitat Bielefeld

AngewandteInformatik Take-Home-Messages

• Beweist NP= P oder NP 6= P und Ihr seid reich

• Findet gute Approximationsalgorithmen für NP-harte Probleme

• Vermeidet NP-harte Probleme

und nun Mathias Katzer: Randomisierte Algorithmen

“Komplizierte Probleme” � ≺ < ∧ ∨ 7