Finden des nächstliegenden Punktepaares mithilfe des Divide-and-Conquer-Prinzips

In diesem Abschnitt werden effiziente Algorithmen zum Finden des nächstgelegenen Punktpaars mithilfe der Divide-and-Conquer-Methode vorgestellt. Bei einer gegebenen Menge von Punkten besteht das Problem des engsten Paares darin, die beiden Punkte zu finden, die einander am nächsten liegen. Wie in der Abbildung unten gezeigt, wird eine Linie gezeichnet, um die beiden nächstgelegenen Punkte in der Animation des engsten Paares zu verbinden.

Fallstudie: „Finding the Closest Pair“, präsentierte einen Brute-Force-Algorithmus zum Finden des nächstgelegenen Punktepaars. Der Algorithmus berechnet die Abstände zwischen allen Punktpaaren und findet dasjenige mit dem minimalen Abstand. Offensichtlich benötigt der Algorithmus O(n^2) Zeit. Können wir einen effizienteren Algorithmus entwerfen?

Wir werden einen Ansatz namens Teile und herrsche verwenden, um dieses Problem zu lösen. Der Ansatz unterteilt das Problem in Teilprobleme, löst die Teilprobleme und kombiniert dann die Lösungen der Teilprobleme, um die Lösung für das gesamte Problem zu erhalten. Im Gegensatz zum dynamischen Programmieransatz überschneiden sich die Teilprobleme beim Divide-and-Conquer-Ansatz nicht. Ein Teilproblem ähnelt dem ursprünglichen Problem, hat jedoch eine kleinere Größe, sodass Sie zur Lösung des Problems eine Rekursion anwenden können. Tatsächlich folgen alle Lösungen für rekursive Probleme dem Divide-and-Conquer-Ansatz.

Die folgenden Schritte beschreiben, wie Sie das Problem des engsten Paars mithilfe des Divide-and-Conquer-Ansatzes lösen.

• Schritt 1: Sortieren Sie die Punkte in aufsteigender Reihenfolge der x-Koordinaten. Sortieren Sie die Punkte mit denselben X-Koordinaten nach Y-Koordinaten. Dies führt zu einer sortierten Liste S von Punkten.
• Schritt 2: Teilen Sie S in zwei Teilmengen, S1 und S2, gleicher Größe auf, indem Sie den Mittelpunkt in der sortierten Liste verwenden. Der Mittelpunkt sei in S1. Finden Sie rekursiv das nächste Paar in S1 und S2. d1 und d2 bezeichnen jeweils den Abstand der nächsten Paare in den beiden Teilmengen.
• Schritt 3: Finden Sie das nächstgelegene Paar zwischen einem Punkt in S1 und einem Punkt in S2 und bezeichnen Sie deren Abstand als d3. Das nächstgelegene Paar ist das mit dem Abstand min(d1, d2, d3).

Die Auswahlsortierung benötigt O(n^2) Zeit. Schritt 1 kann in O(n log n) Zeit durchgeführt werden. Schritt 3 kann in O(n)-Zeit durchgeführt werden. Sei d = min(d1, d2). Wir wissen bereits, dass der Abstand des nächsten Paars nicht größer als d sein kann. Damit ein Punkt in S1 und ein Punkt in S2 das engste Paar in S bilden, muss der linke Punkt in stripL und der rechte Punkt in stripR liegen, wie in der Abbildung unten dargestellt ( a).

Für einen Punkt p in stripL müssen Sie nur einen rechten Punkt innerhalb des d X 2d-Rechtecks ​​berücksichtigen, wie unten (b) gezeigt. Jeder rechte Punkt außerhalb des Rechtecks ​​kann nicht das nächstliegende Paar mit p bilden. Da der Abstand des nächsten Paares in S2 größer oder gleich d ist, können es höchstens sechs sein
Punkte im Rechteck. Somit müssen für jeden Punkt in stripL höchstens sechs Punkte in stripR berücksichtigt werden.

Wie finden Sie für jeden Punkt p in stripL die Punkte im entsprechenden d X 2d-Rechteckbereich in stripR? Dies kann effizient durchgeführt werden, wenn die Punkte in stripL und stripR in aufsteigender Reihenfolge ihrer y-Koordinaten sortiert werden. Sei pointsOrderedOnY die Liste der Punkte, sortiert in aufsteigender Reihenfolge der y-Koordinaten. pointsOrderedOnY können vorher im Algorithmus ermittelt werden. stripL und stripR können von pointsOrderedOnY in Schritt 3 abgerufen werden, wie im Code unten gezeigt.

für jeden Punkt p in pointsOrderedOnY
if (p ist in S1 und mid.x – p.x <= d)
hänge p an stripL;
an sonst wenn (p ist in S2 und p.x - mid.x <= d)
hänge p an stripR;

Die Punkte in stripL und stripR seien {p0, p1, ... , pk} und {q0, q1, ... , qt}, wie in gezeigt Abbildung oben (c). Das nächstgelegene Paar zwischen einem Punkt in stripL und einem Punkt in stripR kann mithilfe des im folgenden Code beschriebenen Algorithmus gefunden werden.

d = min(d1, d2);
 r = 0; // r is the index of a point in stripR
 for (each point p in stripL) {
 // Skip the points in stripR below p.y - d
  while (r < stripR.length && q[r].y <= p.y - d)
  r++;

  let r1 = r;
  while (r1 < stripR.length && |q[r1].y – p.y| <= d) {
 // Check if (p, q[r1]) is a possible closest pair
 if (distance(p, q[r1]) < d) {
 d = distance(p, q[r1]);
 (p, q[r1]) is now the current closest pair;
 }

 r1 = r1 + 1;
 }
}

Die Punkte in stripL werden ab p0, p1, ..., pk in dieser Reihenfolge berücksichtigt. Überspringen Sie für einen Punkt p in stripL die Punkte in stripR, die unter p.y – d liegen (Zeilen 5–6). Sobald ein Punkt übersprungen wird, wird er nicht mehr berücksichtigt. Die while-Schleife (Zeilen 9–17) prüft, ob (p, q[r1]) ein mögliches nächstliegendes Paar ist. Es gibt höchstens sechs solcher q[r1]-Paare, da der Abstand zwischen zwei Punkten in stripR nicht kleiner als d sein kann. Die Komplexität zum Finden des nächsten Paares in Schritt 3 beträgt also O(n).

Beachten Sie, dass Schritt 1 in den obigen Schritten nur einmal ausgeführt wird, um die Punkte vorzusortieren. Gehen Sie davon aus, dass alle Punkte vorsortiert sind. T(n) bezeichne die Zeitkomplexität für diesen Algorithmus. Also

Daher kann das nächstgelegene Punktpaar in O(n log n) Zeit gefunden werden.

Das obige ist der detaillierte Inhalt vonFinden des nächstliegenden Punktepaares mithilfe des Divide-and-Conquer-Prinzips. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!