Closest Pair - Divide and Conquer

tobbimann

Mitglied
Hallo liebe Java-Freunde,

ich habe eine Klasse geschrieben, die mir n zweidimensionale Punkte in einem Array speichert und diese dann nach der x-Koordinate aufsteigend sortiert.

Anschließend wird der kleinste Abstand zwischen 2 Punkten bestimmt.
- einmal auf die triviale Weise "vergleiche alle Punkte mieinander"
- einmal per Divide-and-Conquer, also Teile das Problem in gleichgroße Teilprobleme und löse rekursiv

Der D-and-C Algorithmus macht mir leider noch Probleme. Obwohl zwischenzeitlich der korrekte Wert im Speicher liegt, wird dieser im weiteren Verlauf des rekursiven Aufrufs wieder überschrieben und die beiden Methoden liefern unterschiedliche Ergebnisse.

Auch nach einigen Runden im Debug-Modus finde ich den Fehler nicht.

Kann mir jemand helfen ?

Code:
import java.awt.*;
import java.util.*;

class Aufgabe16 {
	static Point tempPoints[];
	static Point sortedPoints[];
	
	// berechnet die euklidische Distanz zweier Punkte
	public static double distance(Point punkt1, Point punkt2) {
		double xdiff = punkt1.x - punkt2.x;
		double ydiff = punkt1.y - punkt2.y;
		return Math.sqrt(xdiff * xdiff + ydiff * ydiff); 
	}
	
	// a) Erzeugt mit Hilfe von gleichverteilten Zufallszahlen n Punkte
	public static Point[] createPoints(int n) {
		int zufallX, zufallY;
		tempPoints = new Point[n];
		Random rand = new Random();
		
		for (int i = 0; i < n; i++) {
			zufallX = rand.nextInt(100);
			zufallY = rand.nextInt(100);
			tempPoints[i] = new Point(zufallX, zufallY);
			/* tempPoints[0] = new Point(38, 59);
			tempPoints[1] = new Point(92, 64);
			tempPoints[2] = new Point(76, 90);
			tempPoints[3] = new Point(39, 17);
			tempPoints[4] = new Point(10, 47);
			tempPoints[5] = new Point(6, 44); */
		}
		return tempPoints;
	}
	
	// b) sortiert die erzeugten Punkte nach der x-Koordinate
	public static Point[] sortPoints(Point[] tempPoints) {
		sortedPoints = tempPoints;
		int tauschX;
		int tauschY;
		int max;
		
		for (int i = tempPoints.length-1; i >= 0; i--) {
			max=i;
			for (int j = 0; j < i; j++) {
				if (tempPoints[j].x > tempPoints[max].x) { 
					max=j; 
				} 
			}
			tauschX = tempPoints[max].x;
			tauschY = tempPoints[max].y;
			tempPoints[max].x = sortedPoints[i].x;
			tempPoints[max].y = sortedPoints[i].y;
			sortedPoints[i].x = tauschX;
			sortedPoints[i].y = tauschY;
		}
		return sortedPoints;
	}
	
	// c) Teil-und-Herrsche-Algorithmus
	public static double dANDcPoints(Point[] sortedPoints, int left, int right) {
		double minEuklDistance = 0.0;
		
		double minLeftBorderDistance = distance(sortedPoints, sortedPoints[right]);
		double minRightBorderDistance = distance(sortedPoints, sortedPoints[right]);
		double leftBorderDistance = 0.0, rightBorderDistance = 0.0;
		int center = (left + right) / 2;
		
		if( left == right ) {
			// return distance(sortedPoints, sortedPoints[right]) > 0 ? distance(sortedPoints, sortedPoints[right]) : 0;
			return 0.0;
		}
		
		double maxLeftDistance = dANDcPoints(sortedPoints, left, center);
		double maxRightDistance = dANDcPoints(sortedPoints, center+1, right);
		
		for (int i = center; i >= left; i--) {
			leftBorderDistance = distance(sortedPoints[i], sortedPoints);
			if (leftBorderDistance < minLeftBorderDistance) {
				minLeftBorderDistance = leftBorderDistance;
			}
		}
		
		for (int i = center; i >= right; i++) {
			rightBorderDistance = distance(sortedPoints[i], sortedPoints[right]);
			if (rightBorderDistance < minRightBorderDistance) {
				minRightBorderDistance = rightBorderDistance;
			}
		}
		
		minEuklDistance = maxLeftDistance > maxRightDistance ? maxLeftDistance > (minLeftBorderDistance + minRightBorderDistance) ? maxLeftDistance : (minLeftBorderDistance + minRightBorderDistance) : maxRightDistance > (minLeftBorderDistance + minRightBorderDistance) ? maxRightDistance : (minLeftBorderDistance + minRightBorderDistance);
				
		return  minEuklDistance;
	}
	
	// d) Algorithmus, der alle Punkte überprüft
	public static double trivialPoints(Point[] sortedPoints) {
		double minEuklDistance = 0.0;
		
		for (int i = sortedPoints.length-1; i >= 0; i--) {
			for (int j = 0; j < i; j++) {
				minEuklDistance = distance(sortedPoints[i], sortedPoints[j]);
				if (distance(sortedPoints[i], sortedPoints[j]) < minEuklDistance ) {
					minEuklDistance = distance(sortedPoints[i], sortedPoints[j]);
				}
			}
		}
		return minEuklDistance;
	}
	
	// e) Mainklasse zum testen der Methoden
	public static void main( String args[] ) {
		int Punkte = 10;
		
		System.out.println("Erzeuge " + Punkte + " zufällige Punkte...");
		createPoints(Punkte);
		System.out.println("Folgende Punkte wurden erzeugt: ");
		ausgeben(tempPoints);
		sortPoints(tempPoints);
		System.out.println("Die Punkte wurden wie folgt nach der X-Koordinate sortiert: ");
		ausgeben(sortedPoints);
		long time1 = -System.currentTimeMillis(); // TEST
		System.out.println("Teile-und-Herrsche Algorithmus liefert: " + dANDcPoints(sortedPoints, 0, sortedPoints.length-1));
		System.out.print("Laufzeit: ");
		System.out.println(time1+System.currentTimeMillis() + "ms"); // TEST
		System.out.println();
		long time2 = -System.currentTimeMillis(); // TEST
		System.out.println("Trivialer Algorithmus liefert: " + trivialPoints(sortedPoints));
		System.out.print("Laufzeit: ");
		System.out.println(time2+System.currentTimeMillis() + "ms"); // TEST
	}
	
	// Hilfsmethode um die Punkte in einem Point-Array auszugeben
	public static void ausgeben(Point[] points) {
		for (int i = 0; i < points.length; i++) {
			System.out.println("(" + points[i].x + ", " + points[i].y + ")");
		}
	}
}
 

deepthroat

Erfahrenes Mitglied
Hi.

Beide deiner Algorithmen sind nicht korrekt.

In dem trivialen Algorithmus darfst du doch die Variable minEuklDistance nur verändern falls du ein neues Minimum gefunden hast. Du aber veränderst die Variable in jedem Schleifendurchlauf...

In der dANDcPoints Methode gehst du nicht wirklich nach dem Divide-and-Conquer Algorithmus vor. Das Ziel wäre ein Problem solange zu zerlegen bis man es auf ein trivial zu lösendes anderes Problem zerlegt hat.

Das heißt du bestimmst einfach die min. eukl. Distanz der rechten und der linken Hälfte. Das Gesamtminimum läßt sich dann trivialerweise ganz einfach berechnen. Schleifen sind in diesem Algorithmus fehl am Platz. Als Richtwert wäre zu sagen, das der Algorithmus ca. 10 Zeilen (maximal) umfasst.

Außerdem wäre es vermutlich besser, wenn du den Code übersichtlicher schreiben würdest. Eine Zeile die deutlich länger als 100 Zeichen ist, kannst du definitiv nicht wirklich überblicken.

Gruß
 

tobbimann

Mitglied
Hallo und vielen Dank für deine Hilfe.

Ich habe den Code für die triviale Version nun wie folgt abgeändert.

Code:
	public static double trivialPoints(Point[] sortedPoints) {
		double minEuklDistance = distance(sortedPoints[0], sortedPoints[sortedPoints.length-1]);
		
		for (int i = sortedPoints.length-1; i >= 0; i--) {
			for (int j = 0; j < i; j++) {
				if (distance(sortedPoints[i], sortedPoints[j]) < minEuklDistance ) {
					minEuklDistance = distance(sortedPoints[i], sortedPoints[j]);
				}
			}
		}
		return minEuklDistance;
	}

Über den Divide-and-Conquer-Ansatz muss ich nochmal eine Nacht schlafen.