Reduktion eines leichten auf ein schweres Problem

 aufwärts

Ein schweres Problem lässt sich nicht auf ein leichtes Problem reduzieren – es sei denn, dass die Schwierig­keit in der Trans­formation versteckt ist. Denn das schwere Problem ist nicht schwer, wenn es sich auf dem Umweg über das leichte Problem leicht lösen lässt. Dagegen lässt sich ein leichtes Problem ohne weiteres auf ein schweres Problem "reduzieren". Wir zeigen dies, indem wir das Sortier­problem auf das Travelling Salesman Problem (TSP) reduzieren (Bild 1). Die hier gewählte Trans­formation ist dieselbe, die auch beim Beweis der unteren Schranke für die Berechnung der konvexen Hülle vorkommt.

Bild 1: Reduktion des Sortierproblems auf das Travelling-Salesman-Problem (TSP)
Bild 1: Reduktion des Sortierproblems auf das Travelling-Salesman-Problem (TSP)

Reduktion

 

Eingabe:Folge von Zahlen x0, ..., xn-1
Ausgabe:Die sortierte Folge
Methode:
  1. Transformation in einen Fall des Travelling-Salesman-Problems:
    1. Bilde Menge von Punkten pi = (xi, xi2) in der Ebene (Bild 2)
    2. Berechne xj = min(xi)   (in Bild 2 ist j = 4)
  2. Löse das Travelling-Salesman-Problem:
    1. Berechne die kürzeste Rundreise mit pj als Startknoten; offensichtlich verläuft die kürzeste Rundreise entlang den Eckpunkten der konvexen Hülle der Punktmenge (rot dargestellt in Bild 2)
  3. Rücktransformation:
    1. Bilde die Folge der x-Koordinaten der Knoten der Rundreise; dies ist die sortierte Folge (x4, x3, x1, x0, x5, x2 in Bild 2)

    Bild 2:
    Bild 2:

 

Durch diese Reduktion ist gleichzeitig bewiesen, dass sich das Travelling-Salesman-Problem nicht schneller als in Ω(n · log(n)) Schritten lösen lässt  ;-)   Denn ginge es schneller, dann könnte man schneller als in Ω(n · log(n)) Schritten sortieren – dies ist aber nicht möglich, denn Ω(n · log(n)) ist eine untere Schranke für das Sortier­problem.

 

Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 15.01.2003   Updated: 05.06.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik