[Java-Hilfe] Ist das Straight-Radixsort? und noch ne Frage zu Dijkstra

[Senior Sanchez]

Hoi,

Meiner einer lernt ja gerade fleißig und da bin ich im Sedgewick übern Straight-Radixsort Algorithmus gestolpert, nur war der wie schon manch andere Algos im Buch fehlerhaft. Jetzt meine ich den korrigiert zu haben, aber er unterscheidet sich in bestimmten Punkten doch sehr vom Sedgewick (bsp. die Größe vom Array count). Kann mir jemand sagen, ob das wirklich Straight-Radixsort ist oder bloß Distribution-Counting?


public class StraightRadixSort {

public static int[] array = new int[5];

public static void main(String[] args) {

for(int i=0; i < array.length; i++) {
array[i] =(int)(Math.random() * Integer.MAX_VALUE);
System.out.print(array[i] + " ");
}

long time = System.currentTimeMillis();
radixSort();
long time2 = System.currentTimeMillis();
System.out.println(time2 - time);

System.out.println("Ergebnis");
for(int i: array) {
System.out.print(i + " ");
}

}


public static void radixSort() {
int m = 32;
int[] count = new int[32];
for(int i=0; i < 32; i++) {
for(int a = 0; a < count.length; a++) {
count[a] = 0;
}

for(int a =0; a < array.length; a++) {
count[bits(array[a], i,1)]++;
}

for(int a =1; a < array.length; a++) {
count[a] += count[a -1];
}

int[] b = new int[array.length];
for(int a =array.length-1; a >=0; a--) {
b[count[bits(array[a], i,1)]-1] = array[a];
count[bits(array[a], i,1)]--;
}

System.arraycopy(b,0,array,0,array.length);
}

}

public static int bits(int x,int k,int j) {
return (x >> k )% (1 << j);

}
}




---------------------------------------------

Ne andere Frage die ich noch habe: Ihr kennt ja sicherlich den Dijkstra-Algorithmus der ja negative Kantengewichte ausschließt.

Die Frage ist nun folgende: Angenommen man hätte negative Kantengewichte, wäre dann bloß die Berechnung falsch oder (wie von manchen behauptet) terminiert der Algorithmus dann nicht mal?

[Trap]

Du brauchst nur count[2], ansonsten sieht es richtig aus (habs nicht getestet).

Dijkstra mit negativen Kantengewichten kann das richtige Ergebnis liefern, ein falsches Ergebnis liefern oder nicht terminieren, kommt auf den Graph an.

[Senior Sanchez]

Trap[/POST]']Du brauchst nur count[2], ansonsten sieht es richtig aus (habs nicht getestet).

Dijkstra mit negativen Kantengewichten kann das richtige Ergebnis liefern, ein falsches Ergebnis liefern oder nicht terminieren, kommt auf den Graph an.

Das ist mir auch vorhin aufgefallen, zumal die eine schleife noch falsch ist.

es muss da heißen

for(int a=1; a < count.length; a++) {
count[a] += count[a-1];
}



Aber wann terminiert denn der Dijkstra da nicht?

[Trap]

Wenn die Suche einen negativen Zyklus im Graph erreicht, dann terminiert es nicht. Ah, da fällt mir ein, dass man Dijstra ja auch mit expliziter Closed-List implementieren kann, dann terminiert es natürlich.

[Senior Sanchez]

Trap[/POST]']Wenn die Suche einen negativen Zyklus im Graph erreicht, dann terminiert es nicht. Ah, da fällt mir ein, dass man Dijstra ja auch mit expliziter Closed-List implementieren kann, dann terminiert es natürlich.

Eben, das meine ich nämlich.

Ich tagge die kanten quasi, welche schon besucht worden. Somit sind negative Kantengewichte zwar scheiße aber er terminiert.

mache ich das nicht und suche immer nach dem kleinsten kann natürlich nen negativer zyklus entstehen. Aber nicht bei meiner Variante, bei der eben bereits besuchte Kanten rausfliegen.

[Trap]

Senior Sanchez[/POST]']
Ich tagge die kanten quasi, welche schon besucht worden. Somit sind negative Kantengewichte zwar scheiße aber er terminiert.
Kanten markieren ist nicht so geschickt, davon gibt es normalerweise mehr als Knoten, es reicht wenn man den Knoten, den man grade aus der PQ entnimmt als bearbeitet markiert und nichtmehr in die PQ einfügt.

[Senior Sanchez]

Trap[/POST]']Kanten markieren ist nicht so geschickt, davon gibt es normalerweise mehr als Knoten, es reicht wenn man den Knoten, den man grade aus der PQ entnimmt als bearbeitet markiert und nichtmehr in die PQ einfügt.

- Blödsinn geschrieben -

Ich habe gerade nochmal geguggt in meinem Source und ich habe die Knoten markiert, nicht die Kanten, also deine Variante genutzt.

[Sewing]

Wenn die Suche einen negativen Zyklus im Graph erreicht, dann terminiert es nicht. Ah, da fällt mir ein, dass man Dijstra ja auch mit expliziter Closed-List implementieren kann, dann terminiert es natürlich.


aber handelt es sich dann nicht automatisch um den A* Algorithmus?

[robobimbo]

IMHO nicht, weil der A* ja noch eine Heuristik zusätzlich hat.

[Trap]

Der Unterschied zwischen Dijkstra und A* ist, dass man bei A* den nächsten zu bearbeitenden Knoten mit einer Heuristik wählt. Die Heuristik sorgt also nur für eine andere Reihenfolge, verhindert aber doppeltes Bearbeiten nicht.

Eine explizite Closed-List ist da etwas anderes, die verhindert, dass man den gleichen Knoten 2 mal bearbeitet, ändert aber nichts an der Reihenfolge der bearbeiteten Knoten.

[Senior Sanchez]

Wow! Ein fast 5 Jahre alter Thread von mir. Ich war beim Titel ganz interessiert und hab mich schon gewundert, wer so etwas fragt - dabei war ich das. :biggrin:

Zur A*-Frage: robobimbo und Trap haben es genau richtig erklärt. In der Regel nutzt man dort eine Heuristik die nicht überschätzend ist, dass heißt, sie liefert keinen Schätzwert der größer als die reale Entfernung ist. Im Geoinformationsbereich (da habe ich gerade mit zu tun) wird dabei zum Beispiel die Luftlinie genommen, aber meist nicht mittels Euklid bestimmt. A* kann man natürlich auch mit anderen Heuristiken nutzen und ist gerade im Navigationsbereich einer der Standardalgorithmen, wenn nicht sogar DER Standard schlechthin.