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 ?
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 + ")");
}
}
}