Algorithmen in einer Kurzfassung, 2.

Kapitel 1. Denken in Algorithmen

Diese Arbeit wurde mithilfe von KI übersetzt. Wir freuen uns über dein Feedback und deine Kommentare: [e-mail]

Algorithmen sind wichtig! Zu wissen, welcher Algorithmus unter welchen Umständen anzuwenden ist, kann einen großen Unterschied in der Software machen, die du produzierst. In diesem Buch lernst du eine Reihe wichtiger Algorithmen kennen, z. B. das Sortieren und Suchen. Wir stellen dir eine Reihe allgemeiner Ansätze vor, die von Algorithmen zur Problemlösung verwendet werden, wie z.B. die Divide and Conquer- oder Greedy-Strategie. Du wirst in der Lage sein, dieses Wissen anzuwenden, um die Effizienz deiner eigenen Software zu verbessern.

Datenstrukturen sind seit den Anfängen der Computertechnik eng mit Algorithmen verbunden. In diesem Buch lernst du die grundlegenden Datenstrukturen kennen, die verwendet werden, um Informationen für eine effiziente Verarbeitung richtig darzustellen.

Was musst du bei der Auswahl eines Algorithmus beachten? Das werden wir in den folgenden Abschnitten untersuchen.

Verstehe das Problem

Der erste Schritt beim Entwurf eines Algorithmus besteht darin, das Problem zu verstehen, das du lösen willst. Beginnen wir mit einem Beispielproblem aus dem Bereich der Computergeometrie. Stell dir eine Menge von Punkten P in einer zweidimensionalen Ebene vor, wie in Abbildung 1-1 gezeigt, und ziehe ein Gummiband um die Punkte, das du dann loslässt. Die resultierende Form wird als konvexe Hülle bezeichnet (d. h. die kleinste konvexe Form, die alle Punkte in P vollständig umschließt). Deine Aufgabe ist es, einen Algorithmus zu schreiben, der die konvexe Hülle aus einer Menge von zweidimensionalen Punkten berechnet.

Bei einer konvexen Hülle für P liegt jedes Liniensegment, das zwischen zwei beliebigen Punkten in P gezogen wird, vollständig innerhalb der Hülle. Nehmen wir an, wir ordnen die Punkte in der Hülle im Uhrzeigersinn an. Die Hülle wird also durch eine Anordnung von h Punkten _L0, _L1, ...,_Lh-1 im Uhrzeigersinn gebildet, wie in Abbildung 1-2 dargestellt. Jede Folge von drei Rumpfpunkten _Li, _Li+1, _Li+2 bildet eine Rechtskurve.

Abbildung 1-1. Beispielsatz von 15 Punkten in der Ebene

Abbildung 1-2. Berechnete konvexe Hülle für Punkte

Mit diesen Informationen kannst du wahrscheinlich die konvexe Hülle für jede beliebige Punktmenge zeichnen, aber könntest du einen Algorithmus entwickeln (d.h. eine schrittweise Abfolge von Anweisungen, mit der die konvexe Hülle für jede beliebige Punktmenge effizient berechnet werden kann)?

Das Interessante an dem Problem der konvexen Hülle ist, dass es sich nicht ohne Weiteres in bestehende algorithmische Bereiche einordnen lässt. Es scheint keine lineare Sortierung der Punkte von links nach rechts zu geben, obwohl die Punkte im Uhrzeigersinn um die Hülle herum angeordnet sind. Es wird auch keine offensichtliche Suche durchgeführt, obwohl du ein Liniensegment auf der Hülle identifizieren kannst, weil die verbleibenden n - 2 Punkte "rechts" von diesem Liniensegment in der Ebene liegen.

Naive Lösung

Natürlich gibt es für jede Sammlung von drei oder mehr Punkten eine konvexe Hülle. Aber wie konstruiert man sie? Überlege dir die folgende Idee. Wähle drei beliebige Punkte aus der ursprünglichen Sammlung aus und bilde ein Dreieck. Wenn einer der verbleibenden n - 3 Punkte in diesem Dreieck enthalten ist, kann er nicht Teil der konvexen Hülle sein. Wir beschreiben den allgemeinen Prozess mithilfe von Pseudocode, und du wirst ähnliche Beschreibungen für jeden der Algorithmen im Buch finden.

Langsamer Rumpf Zusammenfassung

Am besten, durchschnittlich, am schlechtesten: O(ⁿ⁴)

slowHull (P)
  foreach p0 in P do
    foreach p1 in {P-p0} do
      foreach p2 in {P-p0-p1} do 
        foreach p3 in {P-p0-p1-p2} do
          if p3 is contained within Triangle(p0,p1,p2) then
            mark p3 as internal 

  create array A with all non-internal points in P
  determine leftmost point, left, in A
  sort A by angle formed with vertical line through left 
  return A

Die Punkte p0, p1, p2 bilden ein Dreieck.

Punkte , die nicht als intern markiert sind, liegen auf der konvexen Hülle.

Diese Winkel (in Grad) reichen von -90 bis 90.

Im nächsten Kapitel werden wir die mathematische Analyse erläutern, die zeigt, warum dieser Ansatz als ineffizient angesehen wird. Diese Pseudocode-Zusammenfassung erklärt die Schritte, die eine konvexe Hülle für jede Eingabemenge erzeugen; insbesondere wurde damit die konvexe Hülle in Abbildung 1-2 erstellt. Ist das das Beste, was wir tun können?

Intelligente Ansätze

Die zahlreichen Algorithmen in diesem Buch sind das Ergebnis des Strebens nach effizienteren Lösungen für bestehenden Code. Wir identifizieren in diesem Buch gemeinsame Themen, um dir bei der Lösung deiner Probleme zu helfen. Es gibt viele verschiedene Möglichkeiten, eine konvexe Hülle zu berechnen. Indem wir diese Ansätze skizzieren, geben wir dir einen Vorgeschmack auf das Material in den folgenden Kapiteln.

Gierig

Hier ist eine Möglichkeit, die konvexe Hülle Punkt für Punkt zu konstruieren:

1. Entferne von P seinen tiefsten Punkt, der Teil des Rumpfes sein muss.

2. Sortiere die verbleibenden n - 1 Punkte in absteigender Reihenfolge nach dem Winkel, den sie in Bezug auf eine senkrechte Linie durch low bilden. Diese Winkel reichen von 90 Grad für Punkte links der Linie bis zu -90 Grad für Punkte rechts davon. _pn-2 ist der Punkt ganz rechts und _p0 ist der Punkt ganz links. Abbildung 1-3 zeigt die vertikale Linie und die Winkel zu ihr von jedem Punkt aus als helle Linien.

3. Beginne mit einer partiellen konvexen Hülle, die aus drei Punkten in dieser Reihenfolge gebildet wird _{pn-2, low, _p0}. Versuche, die Hülle zu erweitern, indem du der Reihe nach jeden der Punkte _p1 bis _pn-2 betrachtest. Wenn die letzten drei Punkte der Teilhülle jemals nach links zeigen, enthält die Hülle einen falschen Punkt, der entfernt werden muss.

4. Wenn alle Punkte berücksichtigt wurden, ist die Teilhülle fertig. Siehe Abbildung 1-3.

Abbildung 1-3. Mit einem Greedy-Ansatz gebildeter Rumpf

Teilen und Erobern

Wir können das Problem in zwei Hälften teilen, wenn wir zunächst alle Punkte P von links nach rechts nach der x-Koordinate sortieren (wobei wir Gleichstände durch Berücksichtigung der y-Koordinate auflösen). Aus dieser sortierten Sammlung berechnen wir zunächst die obere konvexe Teilhülle, indem wir die Punkte in der Reihenfolge von links nach rechts von _p0 bis _pn-1 im Uhrzeigersinn betrachten. Dann wird die untere konvexe Teilhülle konstruiert, indem dieselben Punkte in der Reihenfolge von rechts nach links von _pn-1 bis _p0 wieder im Uhrzeigersinn bearbeitet werden. Convex Hull Scan (beschrieben in Kapitel 9) berechnet diese Teilhüllen (siehe Abbildung 1-4) und fügt sie zusammen, um die endgültige konvexe Hülle zu erhalten.

Abbildung 1-4. Rumpf, der durch das Zusammenführen der oberen und unteren Teilhüllen entsteht

Parallel

Wenn du mehrere Prozessoren hast, teile die Anfangspunkte nach x-Koordinaten auf und lasse jeden Prozessor die konvexe Hülle für seine Teilmenge von Punkten berechnen. Sobald diese Berechnungen abgeschlossen sind, wird die endgültige Hülle durch das wiederholte Zusammenführen benachbarter Teillösungen zusammengefügt. Bei einem parallelen Ansatz werden die Teilprobleme auf mehrere Prozessoren aufgeteilt, um die Gesamtlösung zu beschleunigen.

Abbildung 1-5 zeigt diesen Ansatz auf drei Prozessoren. Zwei benachbarte Rümpfe werden zusammengefügt, indem zwei Tangenten hinzugefügt werden - eine oben und eine unten - und dann die Liniensegmente innerhalb des Vierecks, das durch diese beiden Linien gebildet wird, eliminiert werden.

Angleichung

Trotz dieser Verbesserungen gibt es immer noch eine feste untere Grenze für die Berechnung der konvexen Hülle, die nicht zu schlagen ist. Anstatt die exakte Antwort zu berechnen, bist du aber vielleicht mit einer ungefähren Antwort zufrieden, die schnell berechnet werden kann und deren Fehler genau bestimmt werden kann.

Der Bentley-Faust-Preparata-Algorithmus konstruiert eine ungefähre konvexe Hülle, indem er die Punkte in vertikale Streifen unterteilt (Bentley et al., 1982). Innerhalb jedes Streifens werden der maximale und der minimale Punkt (basierend auf der y-Koordinate ) identifiziert (sie sind in Abbildung 1-6 mit Quadraten um die Punkte herum eingezeichnet). Zusammen mit dem äußersten linken und dem äußersten rechten Punkt in P werden diese Extrempunkte zusammengefügt, um die ungefähre konvexe Hülle zu bilden. Dabei kann es vorkommen, dass ein Punkt außerhalb der tatsächlichen konvexen Hülle liegt, wie der Punkt _p1 in Abbildung 1-6 zeigt.

Abbildung 1-5. Rumpf durch Parallelkonstruktionen und Nähte gebildet

Abbildung 1-6. Durch Näherungsberechnungen gebildete Hülle

Verallgemeinerung

Oft ist es möglich, ein allgemeineres Problem zu lösen, dessen Lösung sich leicht in die Lösung deines spezifischen Problems umwandeln lässt. Das Voronoi-Diagramm (Preparata und Shamos, 1993) ist eine geometrische Struktur, die eine Menge von Punkten in einer Ebene in Regionen unterteilt, von denen jede durch einen der ursprünglichen Punkte in der Eingabemenge P verankert ist. Jede Region _Ri ist die Menge der Punkte(x, y) in der Ebene, die näher am Ankerpunkt _pi liegen als jeder andere Punkt in P. Sobald das Voronoi-Diagramm berechnet ist, können diese Regionen wie in Abbildung 1-7 dargestellt werden. Die grauen Regionen sind halb-unendlich und du kannst sehen, dass sie direkt mit den Punkten auf der konvexen Hülle übereinstimmen. Diese Beobachtung führt zu folgendem Algorithmus:

1. Berechne das Voronoi-Diagramm für P.

2. Initialisiere die Hülle mit dem niedrigsten Punkt, low, in P und beginne in der zugehörigen Region.

3. Besuche im Uhrzeigersinn die benachbarte Region, die eine unendlich lange Seite hat, und füge den Ankerpunkt dieser Region zum Rumpf hinzu.

4. Füge so lange Punkte hinzu, bis du auf die ursprüngliche Region triffst.

Abbildung 1-7. Aus dem Voronoi-Diagramm berechneter Rumpf

Zusammenfassung

Ein effizienter Algorithmus ist oft gar nicht so einfach zu entdecken, und für unterschiedliche Datensätze, unterschiedliche Verarbeitungsumgebungen (z. B. wo du die Parallelität ausnutzen kannst) und unterschiedliche Ziele können ganz unterschiedliche Algorithmen die beste Wahl sein. Diese kurze Einführung hat nur an der Oberfläche der Algorithmen gekratzt. Wir hoffen, dass du jetzt Lust bekommen hast, mehr über die verschiedenen Ansätze und die Vielfalt der Algorithmen zu erfahren, die wir in diesem Buch gesammelt haben. Wir haben alle Algorithmen implementiert und mit entsprechender Dokumentation und Erklärungen versehen, damit du verstehst, wie du diese Algorithmen nutzen und sogar selbst implementieren kannst.

Referenzen

Bentley, J. L., F. Preparata, and M. Faust, "Approximation algorithms for convex hulls," Communications of the ACM, 25(1): 64-68, 1982, http://doi.acm.org/10.1145/358315.358392.

Preparata, F. und M. Shamos, Computational Geometry: Eine Einführung, Springer, 1993.