Labyrinth-Problem

iAZ

Mitglied
Hallo ihr,
Ich arbeite gerade an einem kleinen Problem in Java: finde den kürzesten Weg in einem Labirinth.
Ich hab schon ein bisschen geplant, wie ich das mache:
  1. Lese aus einer Datei Die Zahlen in ein 2-dimensionales Array: 0=>Wand; 1=>Weg; 2=>Start; 3=>Ziel
  2. Suche den Start Starte in jede Richtung einen Thread
  3. Thread: gehe solange in eine Richtung, bis eine Kreuzung oder Saggasse kommt; Schreibe die Anzahl der Züge in das Feld.
  4. Wenn Kreuzung: starte in jede Richtung (außer in die, woher du gekommen bist) einen eigenen Thread und beende den aktuellen.
  5. Wenn Saggasse: starte thread, der zurück bis zu einer Kreuzung geht und den Weg überschreibt.
  6. Wenn Ziel: warte bis alle threads beendet sind und gehe den kürzesten Weg (d.h. der wo die kleinste Zahl steht) zurück und kennzeichne ihn entsprechend
Am Ende sollte es ungefähr so aussehen: http://rost.azapps.de/info/lex12/pics/maze_running/maze_running004.gif

Jetzt zu meinem Problem:
Das Array aus der Datei zu lesen, habe ich schon geschafft. Aber ich hab nicht wirklich Ahnung, wie ich das Speichere. Meiner Meinung nach, wäre eine Globale Variable, auf die jeder Thread zugreifen kann das beste. Aber da Java eine OO-Sprache ist, wäre die Lösung nicht so schön. Wenn ich das Objekt mit dem Array an jeden Thread übergebe, wie Garantiere ich dann, dass jeder Thread die aktuelle Version hat?

Danke,
AZ
 
Bau dir für den Typ doch eine Containerklasse (z. B. Field(byte typ)), und speichers einfach in ne HashMap, indem du die Instanzen mit den Points der Koordinaten verknüpfst.
 
Wenn ich das Objekt mit dem Array an jeden Thread übergebe, wie Garantiere ich dann, dass jeder Thread die aktuelle Version hat

In Java gibst du nicht ein Objekt, sondern immer nur einen Zeiger auf ein Objekt weiter. Das mag auf den ersten Blick kein großer Unterschied sein, ist aber enorm wichtig: Auch wenn sich das Objekt ändert, bleibt ein Zeiger darauf gültig.

Mein erster Gedanke wäre wohl ein einfaches zweidimensionales Array, dass jeder Thread kennt. Ich denke mal, deine Koordinaten sind irgendwas von (0,0) bis, (m,n) oder so? Mir erscheint eine HashMap mit "Points der Koordinaten", was auch immer damit gemeint war, gerade etwas overhead :)

Allerdings musst du dir Gedanken machen, wie du verhinderst, dass 2 Threads gleichzeitig auf ein Feld schreiben...
 
Allerdings musst du dir Gedanken machen, wie du verhinderst, dass 2 Threads gleichzeitig auf ein Feld schreiben...
Das ist keine große Sache, Stichwort Monitoring sollte da weiterhelfen. Allerdings würde ich mir da überlegen, ob ich nicht vielleicht darauf verzichten würde und stattdessen entsprechende Alternativen wie Collections, die das Prinzip bereits implementiert haben (z.B. Vector, HashTable), verwenden würde.
 
Das Labyrinth auf der Seite sollte er sich eher nicht so zu Herzen nehmen, der ist bei mir gerade gut 10 mal die selben 2 Sackgassen abgelaufen, bevor er mal nen Ausgang genommen hat. Den rekursiven Aufruf jedes Feldes finde ich da wesendlich besser, jeder Thread der das Ziel erreicht muss nur in eine globale Variabel schreiben, wie lange er gebraucht hat, bei jedem Threaddurchlauf muss dieser nur checken, ob die Variable schon auf einem Wert, der größer/gleich 1 ist gesetzt wurde, und ob die aktuellen Schritte kleiner sind, sonst hört er auf. Am Ende muss er nur warten, bis alle Threads aufhören.
Bei dem Backtracking müsste z. B. noch speichern, wo er schon war, damit er dem selben "Fehler" nicht 2 mal macht.

btw^1: Monitoring? Einfach einen ReentrantLock locken, oder? Wobei ich mal etwas davon gelesen habe, dass ein Thread beim syncronisieren nicht umbedingt ein "ungecachede" Instanz, also eine geänderte Version sieht. Habe es aber nicht richtig verstanden. Stand hauptsächlich im Zusammenhang mit dem Variablen-Keyword um zu syncronisieren.
btw²: Klar kann man einfach ein Array verwenden, aber ich finde HashMap's eine coole Erfindung. ^_^
 
Hallo!

Wenn du den schnellsten Weg von mehreren verschiedenen suchst (setzt voraus, dass die Wege auch zum Ziel führen und du die Wege kennst), könntest du dich in den Ameisenalgorithmus einarbeiten.

Wenn du also mehrere Wege ermittelt hast, kannst du damit die optimalste Route finden.

Siehe: http://de.wikipedia.org/wiki/Ameisenalgorithmus

mfg
Martin
 
Für die Suche nach dem kürzesten Pfad verwendet man normalerweise den Dijkstra-Algorithmus.
Für die Suche würde ich keine Threads verwenden. Wenn du aber doch welche verwenden willst, musst du bei gemeinsam genutzten Ressourcen darauf achten, dass der Zugriff mit Lockingmechanismden gesichert wird.
 
In Java gibst du nicht ein Objekt, sondern immer nur einen Zeiger auf ein Objekt weiter. Das mag auf den ersten Blick kein großer Unterschied sein, ist aber enorm wichtig: Auch wenn sich das Objekt ändert, bleibt ein Zeiger darauf gültig.

Mein erster Gedanke wäre wohl ein einfaches zweidimensionales Array, dass jeder Thread kennt. Ich denke mal, deine Koordinaten sind irgendwas von (0,0) bis, (m,n) oder so? Mir erscheint eine HashMap mit "Points der Koordinaten", was auch immer damit gemeint war, gerade etwas overhead :)

Allerdings musst du dir Gedanken machen, wie du verhinderst, dass 2 Threads gleichzeitig auf ein Feld schreiben...

Ahhhh....
Das dürfte also heißen, dass alle Threads immer die gleiche instanz des Objekts benutzen, und es somit überhaupt keine Probleme mit der Synchronisation geben ... (Wenn ich es richtig verstanden habe)
Ich habs mir dann irgendwie falsch Vorgestellt...


Komische Seite ;) kriegs nicht hin den "Held" zu bewegen, aber egal.

Hallo!

Wenn du den schnellsten Weg von mehreren verschiedenen suchst (setzt voraus, dass die Wege auch zum Ziel führen und du die Wege kennst), könntest du dich in den Ameisenalgorithmus einarbeiten.

Wenn du also mehrere Wege ermittelt hast, kannst du damit die optimalste Route finden.

Siehe: http://de.wikipedia.org/wiki/Ameisenalgorithmus

mfg
Martin

Wenn ich in jedes Feld reinschreibe, wie viele züge man vom Start aus braucht, kann man doch gleich vom Ziel immer -1 gehen... dürfte doch effizienter sein. Und wenn man eine Stelle kommt wo schon was im Feld steht, überprüft man, ob seine eigene Zahl größer ist, wenn ja, überschreibt man einfach, wenn nicht beendet man den Thread.

Ich werd mich mal am WE dran setzen, mal schauen was rauskommt;)

AZ
 
Zurück