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 :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138

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[left], sortedPoints[right]);         double minRightBorderDistance = distance(sortedPoints[left], sortedPoints[right]);         double leftBorderDistance = 0.0, rightBorderDistance = 0.0;         int center = (left + right) / 2;                 if( left == right ) {             // return distance(sortedPoints[left], sortedPoints[right]) > 0 ? distance(sortedPoints[left], 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[left]);             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 + ")");         }     } }

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ß

Hallo und vielen Dank für deine Hilfe.

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

Code :

1 2 3 4 5 6 7 8 9 10 11 12

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.