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/pic...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.

Hi,

schau dir das mal an: http://www.matheprisma.uni-wuppertal...ckTr/index.htm

Gruß
Erik

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.

Zitat von Vereth

Für die Suche nach dem kürzesten Pfad verwendet man normalerweise den Dijkstra-Algorithmus.

Genau!

Ich erinnere mich noch daran wie ich in der Schule mit damit manuell den kürzesten Weg von Router zu Router berechnen musste.
Ich hab's gehasst...

Zitat von RoCMe

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...

Zitat von Erik

Hi,

schau dir das mal an: http://www.matheprisma.uni-wuppertal...ckTr/index.htm

Gruß
Erik

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

Zitat von mccae

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

Zitat von iAZ

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...

Nein, dadurch entstehen Syncronisationsprobleme erst. Wenn jeder Thread seine eigene Instanz hätte, könnte er die Variablen darin nach belieben verändern.
Probleme gibt es grundsätzlich nur, wenn ein 2. Thread dem ersteren "dreinpfuscht". Threads werden gemäß dem Zeitscheibenmodell abgearbeitet, das heißt jeder Prozessorkern hat seine Threads die er abarbeitet (ist aber natürlich theoretisch auch auf einen anderen Kern übertragbar). Jeder Kern kann nur einen Thread gleichzeitig abarbeiten, und wechselt sich ab. Das Problem kann erst entstehen, wenn ein Thread wärend dem abarbeiten einer unsyncronisierten Thread von der CPU interrupted wird.
Der zweite Thread könnte so eine Änderung, die der erste gerade gemacht hat überschreiben.

Ich bin endlich fertig geworden... ich versuch mal in den nächsten tagen eine kurze Doku zu schreiben und den Code zu veröffentlichen

Hallo ihr,
Ich möchte euch mein Wissen natürlich nicht vorenthalten. Also wer sich das Labyrinth mal angucken will:
Labyrinth in meinem Blog
Dort könnt ihr euch auch das ganze Programm herunterladen.
Ich hab den Lösungsalgorithmus nicht mit Multithreading sondern mt Rekursion gemacht (erschien mir einfacher ).
Danke nochmals für eure Hilfe.

Schon ganz gut, aber du solltest besser das Labyrinth in ein Array der Größe (w+2,h+2) einlesen, damit du automatisch eine Umrandung hinzufügen kannst.
Möglich wäre auch, die Daten nicht in einem Array zu speichern, sondern in mit verzeigerten Objekten, wo jedes Feld einen Link zu seinen 4 Nachbarn hat, wie es bei einer schwach besetzten Matrix üblich ist. Auf diese Weise kannst du dann auch leicht z.B. 'Torus-Welten' oder andere Geometrienimplementieren, wo der obere und untere Rand bzw. der linke und der rechte Rand miteinander verbunden sind. Außerdem können dann alle Felder auf dasselbe Wand-Objekt verweisen; oder du verzichtest ganz auf die Wände und stellst sie als stattdessen null-Referenzen dar.

PS: Man schreibt Sackgasse

Danke,
ich werde es versuchen in den nächsten tagen zu verbessern
Sackgasse: peinlich, peinlich berichtigt
[EDIT:] Alles aktualisiert, man muss jetzt keinen Rand mehr ziehen adresse: http://blog.azapps.de/de/article/77/projekt-labyrinth/?