Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


24. Elementare geometrische Methoden



Einfacher geschlossener Pfad

Um ein Gefühl für die Probleme zu bekommen, die mit Punktmengen zusammenhängen, betrachten wir das Problem einen Pfad durch eine Menge von N gegebenen Punkten zu finden, der sich nicht selbst überschneidet, alle Punkte berührt und zum Anfangspunkt zurückführt. Ein solcher Pfad wird einfacher geschlossener Pfad genannt. Man kann sich viele Anwendungen hierfür vorstellen: Die Punkte könnten Häuser darstellen und der Pfad die Route, die ein Postbote wählen könnte, um jedes der Häuser aufzusuchen, ohne daß sich sein Pfad überkreuzt. Oder es könnte sein, daß wir nach einem einfachen Verfahren suchen, wie die Punkte unter Verwendung eines Plotters gezeichnet werden könnten. Dieses Problem ist elementar, da lediglich nach irgendeinem geschlossenen Pfad gefragt wird, der die Punkte verbindet. Das Problem der Bestimmung des besten derartigen Pfades, das das Problem des Handelsreisenden (traveling salesman problem) genannt wird, ist viel, viel komplizierter, und wir betrachten es in den letzten Kapiteln dieses Buches etwas ausführlicher. Im folgenden Kapitel betrachten wir ein ähnlich gelagertes, doch wesentlich einfacheres Problem: die Bestimmung des kürzesten Pfades, der eine Menge von N gegebenen Punkten umschließt. In Kapitel 31 werden wir sehen, wie man den besten Pfad finden kann, um eine Menge von Punkten zu »verbinden«.

Abbildung 24.4
Abbildung 24.4 Einfache geschlossene Pfade.

Ein sich anbietender einfacher Weg zur Lösung des elementaren Problems ist folgender. Wähle einen der Punkte aus, der als »Anker« dienen soll. Berechne dann den Winkel von jedem der Punkte aus der Menge über den Anker und zur Waagerechten (dies ist ein Bestandteil der Polarkoordinaten des jeweiligen Punktes mit dem als Anker dienenden Punkt als Ursprung). Sortiere dann die Punkte entsprechend diesem Winkel. Verbinde schließlich benachbarte Punkte. Das Ergebnis ist ein einfacher geschlossener Pfad, der die Punkte verbindet, wie es in Abbildung 24.4 für die Punkte aus Abbildung 24.1 dargestellt ist. Für die kleine Punktmenge wird B als Anker benutzt; wenn die Punkte in der Reihenfolge

B M J L N P K F I E C O A H G D B

besucht werden, wird ein einfaches geschlossenes Polygon gezeichnet.

Falls dx und dy die Abstände von dem als Anker verwendeten Punkt zu einem anderen Punkt längs der x-Achse bzw. y-Achse bezeichnen, so ist der in diesem Algorithmus benötigte Winkel tan-1 dy/dx. Obwohl der Arkustangens in Pascal (und einigen anderen Programmierumgebungen) eine Standardfunktion ist, ist er gewöhnlich langsam und führt zu wenigstens zwei lästigen zusätzlichen Bedingungen, die überprüft werden müssen: ob dx gleich 0 ist und in welchem Quadrant der Punkt liegt. Da der Winkel in diesem Algorithmus nur für das Sortieren benutzt wird, ist es sinnvoll, eine Funktion zu benutzen, die sich wesentlich leichter berechnen läßt, jedoch die gleichen ordnenden Eigenschaften hat wie der Arkustangens (so daß wir beim Sortieren das gleiche Ergebnis erhalten). Ein guter Kandidat für eine solche Funktion ist einfach dy/(dy + dx). Ein Test für Ausnahmebedingungen ist trotzdem noch notwendig, doch einfacher. Das folgende Programmsegment gibt eine Zahl zwischen 0 und 360 zurück, die nicht gleich dem Winkel ist, den p1 und p2 mit der Waagerechten bilden, die jedoch die gleichen Ordnungseigenschaften wie dieser Winkel besitzt.

    function theta(p1,p2: point): real;
      var dx,dy,ax,ay: integer;
          t: real;
      begin
      dx:=p2.x-p1.x; ax:=abs(dx);
      dy:=p2.y-p1.y; ay:=abs(dy);
      if (dx=0) and (dy=0) then t:=0
        else t:=dy/(ax+ay);
      if dx<0 then t:=2-t
        else if dy<0 then t:=4+t;
      theta:=t*90.0;
      end;

In manchen Programmierumgebungen lohnt es sich möglicherweise nicht, solche Funktionen anstelle der standardmäßigen trigonometrischen Funktionen zu verwenden; in anderen können sie zu beträchtlichen Einsparungen führen. (In manchen Fällen kann es sich lohnen, theta so zu ändern, daß ein ganzzahliger Wert vorliegt, um die Benutzung von Zahlen vom Typ real vollständig zu vermeiden.)


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]