Bekomme Algorithmus nicht in Code umgesetzt

draig

Mitglied
Hallo. Ich ahbe mir einen Algorythmus überlegt, nur leider bekomme ich ihn nicht in Code umgesetzt.

Ich beschreibe mal wie er funktionieren soll.

ich habe einen Startpunkt und einne Zielpunkt, diese sind jeweils x und y Koordinaten.

sY und sX sind die Koordinaten zum start und zX und zY für Ziel.
Nun gibt es dort auf den weg Hinernisse, so das man diese umgehen muss.

Mein Gedanke ist nun, das vom Startfeld geguckt wird, ob das Feld "Oben" (vom Startfeld) schon einmal besucht wurde und das Gleiche für das Feld "Unten", sowie "Rechts" und "Links". Wenn nein und Ist begebar(also kein Hindernis) dann Setzte sie auf besucht (wird im einen Array gesetzt).
Das Gleiche soll er nun für die Felder machen, die er gerade Besucht hat, also wieder Oben und Unten gucken (nicht links Rechts). Sind alle Felder auf der Y Axe abgelaufen, so gehe wieder zum Startfeld und gucke nun ein Feld Links und Rechts weiter, welche Felder von Dort aus besucht werden können. Dies soll solange durchgehen, bis alle Felder die Begehbar sind dann einmal besucht wurden.

Hier ein Beispiel, wie ich mir das Vor stelle:
#=Mauer/Hindernis
_=Begehbar
o=besucht gerade
n=wurde schon besucht

Koordinaten: sY=1 und sX=9 , zY=1 und zX=1 Y= 5 X=10
Hier ist o die Stratposition und z die Zeilposition. Jetzt die ausbreitung im nächsten Schritt:
############
#___z####o_#
#___######_#
#________#_#
#__________#
#__________#
############

Versucht oben unten zu gehen, geht aber nicht. Danach rechts und links. Geht nur links, daher o auf links
############
#___z####no#
#___######_#
#________#_#
#__________#
#__________#
############

Versucht oben unten zu gehen, geht nur unten, da oben wieder nicht begehbar
############
#___z####nn#
#___######o#
#________#_#
#__________#
#__________#
############

Versucht wieder vom letzten o oben unten zu gehen, geht nur unten, da schon oben besucht wurde.
############
#___z####nn#
#___######n#
#________#o#
#__________#
#__________#
############

Siehe einen Schritter drüber.
############
#___z####nn#
#___######n#
#________#n#
#_________o#
#__________#
############

Guckt wieder und kann nun links und rechts gehen.
############
#___z####nn#
#___######n#
#________#n#
#________on#
#_________o#
############

Nun soll er ein Feld runter gehen und von dort aus gucken welche begehbar sind.
############
#___z####nn#
#___######n#
#________#n#
#________on#
#________on#
############

Nun soll er bei beiden o gucken, wo er hin kann. In diesen Fall können nur beide nach links, da alle anderne nicht begehbar oder schon gegangen wurden. Bignnen soll das o, was nähr an der Startposition liegt.
############
#___z####nn#
#___######n#
#________#n#
#________on#
#________on#
############

nun wird wieder geguckt
############
#___z####nn#
#___######n#
#________#n#
#_______onn#
#_______onn#
############

diesemal war oben frei, also geht dort ein neues o hin, da nun wieder nach oben gagen werden konnte, muss ers das neue was nach ob ge
gangen ist gucken was von ihm aus frei ist.
############
#___z####nn#
#___######n#
#_______o#n#
#______onnn#
#______onnn#
############

das sieht dann so aus
############
#___z####nn#
#___######n#
#______on#n#
#______onnn#
#______onnn#
############

überspirnge paar schritte, da wieder nun das Gleiche kommt
############
#___z####nn#
#___######n#
#__onnnnn#n#
#__onnnnnnn#
#__onnnnnnn#
############

Dann nun wieder einer nach oben gegangen ist, muss der nun wieder gucken, bevor die Anderne weiter machen
############
#___z####nn#
#__o######n#
#_onnnnnn#n#
#_onnnnnnnn#
#_onnnnnnnn#
############

sieht dann so aus
############
#__oz####nn#
#_on######n#
#_onnnnnn#n#
#_onnnnnnnn#
#_onnnnnnnn#
############

Oben wieder ein neuer, also wieder erst der gucken
############
#__oz####nn#
#_on######n#
#_onnnnnn#n#
#_onnnnnnnn#
#_onnnnnnnn#
############

Da nun ein o auf z, Algorythmus zu Ende
############
#_ono####nn#
#_on######n#
#_onnnnnn#n#
#_onnnnnnnn#
#_onnnnnnnn#
############

So würde dnan nun der gegangene weg aussehen. Durch ein "g" gekennzeichnet
############
#_ogg####gg#
#_og######g#
#_ogggggg#g#
#_onnnnnggg#
#_onnnnnnnn#
############



Ich habe leider keine andere Idee gehabt, es besser erklären zu können, als so.
 
Zuletzt bearbeitet:
Klingt wie Roboralley...

Aber wo ist nun dein Problem das so umzusetzen?

Ich würde übrigens in den Algorithmus einbauen nach möglichkeit den kürzesten Weg zum Ziel zu gehen und nicht alles zu durchsuchen.
 
Am ende ist es der Kürzeste Weg. Mein Problem ist, dass ich diesen Algorythmus nicht in Java Code um gesetzt bekomme, ob Schleife oder Rekusion.
 
Du mußt schon konkret sagen womit du nicht weiterkommst, ne Lösung wirst du hier nicht gepostet bekommen.

Zeig doch mal was du schon gemacht hast.
 
Hallo,

das klingt mir sehr nach einer einfachen Breitensuche. Mit diesem Stichwort sollten sich auch konkrete Implementierungen finden lassen.

Grüße,
Matthias
 
Nur habe ich keinen Graphen, sonst hätte ich schon einen fertigen Algorythmus genommen.

Ich komme einfach nicht auf die Idee, wie ich es hintereinander aufrufen soll. Einne kompletten quellode möchte ich gar nicht mir reicht shcon sowas wie

methode gehen

wenn yPositon>25
mach rekusion

ehr sowas.

ersten schritt den ich gemacht habe ist

Code:
static boolean gegangen[] = new boolean[24][25];
public void geheObenUnten(int yPosition, int xPosition){

geheRechts(int yPosition, int xPosition);
geheLinks(int yPosition, int xPosition);

gegangen[xPosition][yPosition]=true;
if(yPosition<2 5&& gegangen[xPosition][yPosition+1] == false){
geheObenUnten(yPosition+1);
}

if(yPosition>-1 && gegangen[xPosition][yPosition-1] == false){
geheObenUnten(yPosition-1);
}
}


hiermit sollten erstmal alle Felder auf der y Achse von der Start Position abgedeckt sein.Es werden alle Felder rauf und runter gegangen und von jedem feld rauf und runter Rechts und Links.
 
Zuletzt bearbeitet:
Ich habe glaube ich nun eine Idee wie ich es mache, werde dann Bericht erstatten ob es dnan so geklappt hat.
 
Nur habe ich keinen Graphen, sonst hätte ich schon einen fertigen Algorythmus genommen.
Du hast einen Graphen, auch wenn dir das vielleicht nicht ganz bewusst ist :) Die Knoten des Graphen sind die begehbaren Felder, eine Kante zwischen zwei Knoten existiert genau dann wenn die beiden entsprechenden Felder aneinandergrenzen.

Grüße,
Matthias
 
Hallo,

die klassische Lösung (immer wieder gern genommen), ist glaube ich die, die anzahl
Schritte mit dem ein Feld erreicht werden kann in einem "Lösungs-Array"zu vermerken !

Nach neun durchläufen sieht das z.B.das aus !

"Aufgaben-Array" "Lösungs-Array"
############ ############
#___z####s_# #___z####01#
#___######_# #___######2#
#________#_# #_____987#3#
#__________# #____987654#
#__________# #_____98765#
############ ############

Das Lösungs-Array braucht natürlich die Struktur des Labyrinths nicht enthalten
sondern nur die Schrittzahlen als int-Werte ! ( int[][] )

Hat man das Ziel erreicht ist es einfach den (einen) kürzesten Weg zu ermitteln !
Rückwärts vom Ziel folgt man den Schrittzahlen bis zur 0, dem Startfeld !

Gruß Jadix !
 
Zurück