Not logged in. · Lost password · Register

Page:  1  2  next 
Shadow992
Member since Jan 2014
290 posts
Subject: Code-Gerüst für Blatt 3 Aufgabe 3.4
+1 nakami
Hallo zusammen,

ich möchte es nur kurz in den Raum werfen, um eventuellem "Jammern" vorzubeugen.
Da ich leider das aktuelle Blatt erst viel zu spät gesehen habe (sprich ich hab nicht gecheckt, dass es schon hochgeladen ist, ich aber halt "danach suchen" muss), wurde das jetzt auch etwas chaotisch. So wie es aussieht wird es für Aufgabe 3.4 ein Code-Gerüst geben. Bevor ich jedoch das Gerüst hochlade, möchte ich meinen Kollegen noch etwas Zeit geben, um eventuelle Probleme/Verbesserungsvorschläge/u.ä. zu machen.

Dieser Post dient also lediglich dazu diejenige unter euch, die nicht unter Prokastination leiden, früh genug "zu warnen", dass sie sich eventuell mehr Arbeit als nötig machen.
Das Code-Skelett ist momentan ausschließlich in C++11 vorhanden, bietet dafür aber ganz nette Debugging und Visualisierungs-Methoden (zumindest der aktuelle Stand, vielleicht müssen wir das noch etwas kürzen/anpassen). Eigentlich wollte ich noch einen äquivalenten Java-Code dafür schreiben, aber die Zeit hat da etwas gegen mich gespielt...

Sofern aber niemand der Tutoren etwas dagegen hat und es sich gewünscht wird, werde ich auch Java-Skelette in Zukunft versuchen mit rauszuhauen.
Eventuell sind wir uns nach dem Blatt auch einig, dass Code-Skelette doof sind und lassen das wieder.

Genaueres zwecks Code-Skelette zum jetzigen Blatt gibt es morgen Nachmittag und wie das in Zukunft laufen wird, werden wir wohl spätestens nach der dazugehörigen Übung (das heißt in zwei Wochen) entscheiden, nämlich dann, wenn wir auch etwas Rückmeldung bekommen haben. Eventuell macht das Skelett-Zeugs ja genau das Gegenteil und verwirrt euch nur unnötig.

P.S.
Bitte nehmt die Aussage: "Implement this problem in a programming language of your choice" nicht zu wörtlich. Auf esoterische Sprachen (z.b. Brainfuck und Co.) hab ich wirklich keine Lust. Das heißt geht von sehr strenger Korrektur aus (zumindest von meiner Seite aus), sollte jemand wirklich auf diese Idee kommen esoterische Sprache zu verwenden (Nur als Randanmerkung, weil ich mindestens eine Person kenne, die wirklich mit einem derartigen Gedanken spielte ;) ).

So und jetzt "Happy Solving" oder so :D
BTL
Member since Oct 2012
310 posts
+1 nakami
Gleich mal eine Frage zu dieser Aufgabe: Wenn das Feld 50x50 groß ist und man die linke obere Ecke als (0, 0) bezeichnet, ist dann rechts unten nicht (49, 49)? Wenn man bei 0 das Zählen beginnt, ist das grüne Feld auf (8, 8) statt auf (9, 9).
Shadow992
Member since Jan 2014
290 posts
+1 nakami
Quote by BTL:
Gleich mal eine Frage zu dieser Aufgabe: Wenn das Feld 50x50 groß ist und man die linke obere Ecke als (0, 0) bezeichnet, ist dann rechts unten nicht (49, 49)? Wenn man bei 0 das Zählen beginnt, ist das grüne Feld auf (8, 8) statt auf (9, 9).

Ich denke auch, dass das ein Fehler ist. (8,8) sollte die tatsächlich gemeinte Koordinate sein. Genau so wie das Feld natürlich nur bis (einschließlich) 49x49 geht.
Jazzpirate
Member since Oct 2016
803 posts
In reply to post #2
und man die linke obere Ecke als (0, 0) bezeichnet
...hab ich (0,0) geschrieben? Ich meinte (1,1)... (in Analogie zur Indizierung von Einträgen in Matritzen)
wird korrigiert ^^
MrDeathly
Member since Nov 2012
101 posts
Hätte man das Feld nicht kleiner machen können? Bei den endlos vielen Zyklen brauch ich für BFS ja fast nen HPC-Cluster um den Pfad zu finden.
Shadow992
Member since Jan 2014
290 posts
Quote by MrDeathly:
Hätte man das Feld nicht kleiner machen können? Bei den endlos vielen Zyklen brauch ich für BFS ja fast nen HPC-Cluster um den Pfad zu finden.

Das Geheimnis liegt in dem Satz "Also, all algorithms should remember visited states, as to not run into cycles." ;)
Und 50x50 ist selbst für BFS wirklich ein Klacks.
Jazzpirate
Member since Oct 2016
803 posts
In reply to post #5
Hätte man das Feld nicht kleiner machen können?
Naja, es musste groß genug sein, dass den algorithmus per Hand durchzunudeln nicht feasible ist...
Bei den endlos vielen Zyklen brauch ich für BFS ja fast nen HPC-Cluster um den Pfad zu finden.
hmm, ich würde fast behaupten, dann machst du was falsch... oder überseh ich was, was den search space zum explodieren bringt?
Shadow992
Member since Jan 2014
290 posts
+1 nakami
So das C++11 Code-Gerüst ist ausreichend getestet und steht ab sofort in StudOn unter "KI_Uebung_3_4_src.zip" zur Verfügung. Eine MakeFile liegt bei, ebenso wie kleine Anmerkungen/Kommentare.

Die Image.h bzw. Image.cpp könnt ihr getrost ignorieren, ihr müsst (hoffentlich) nie in dieser Datei rumpfuschen (dient lediglich zur Visualisierung). Der Rest ist alles Code, der euch helfen soll/kann.

Bei Fragen, Bugs u.ä. am besten das Forum benutzen, damit die Antwort auf die Frage jeder einsehen kann.
This post was edited on 2016-11-08, 17:01 by Shadow992.
Haddi
Member since Mar 2013
12 posts
Ich hab noch eine Frage zu dem iterative Deepening:
Wenn mein Algorithmus einen Punkt erreicht, welcher aber durch einen früheren Knoten bereits sichtbar ist(aber noch nicht besucht), soll er dann trotzdem stupide weiter laufen oder soll ich ihn stoppen, da er ja durch den früheren Knoten den gleichen Zustand schneller erreichen würde?
Würde den Algorithmus eben verbessern, die Frage ist nur ob das dann noch im Sinne eines DFS ist.
Shadow992
Member since Jan 2014
290 posts
Quote by Haddi:
Ich hab noch eine Frage zu dem iterative Deepening:
Wenn mein Algorithmus einen Punkt erreicht, welcher aber durch einen früheren Knoten bereits sichtbar ist(aber noch nicht besucht), soll er dann trotzdem stupide weiter laufen oder soll ich ihn stoppen, da er ja durch den früheren Knoten den gleichen Zustand schneller erreichen würde?
Würde den Algorithmus eben verbessern, die Frage ist nur ob das dann noch im Sinne eines DFS ist.

Auf den Blatt steht ja "Also, all algorithms should remember visited states, as to not run into cycles.", das würde ich also schon interpretieren als "nicht noch einmal besuchen" (ein vergleichbares Problem ergibt sich ja auch bei A*, wobei das per Definition ja klar geregelt ist... Naja ihr wisst was ich meine :D).
Solltest du das C++ Code-Skelett benutzen und keine eigenen Methoden hinzufügen, ist die einfachste Variante sogar, das ohne nochmaliges Besuchen zu implementieren.
Im Endeffekt bleibt es aber dir überlassen: Es ist beides genau gleich richtig und ändert nichts am Prinzip.
MiriTheRing
Member since Oct 2011
38 posts
Würde den Algorithmus eben verbessern, die Frage ist nur ob das dann noch im Sinne eines DFS ist.
Darueber kann man sich streiten, wenn du bei DFS mit iterative deepening schon (mit der selben maximalen tiefe) erreichte zustaende nicht mehr besuchst wird der algorithmus "unoptimaler" (optimal wars ja vorher auch nicht), weil der wieder gefundene zustand eventuell beim zweiten mal mit gerinerer Tiefe erreicht wird, und man sich durch nicht erneutes besuchen das Weiterkommen blockiert. Was moechtet ihr, einen schlechten algorithmus oder seeeeeehr lange laufzeit?

Nachtrag: Bei meiner frage gehts um den unterschied zwischen backtracking oder jeden zustand in jedem "Tiefenschritt" genau ein mal besuchen, was bauen was sich in loops verirrt ist ja per blatt ausgeschlossen.
This post was edited on 2016-11-09, 22:07 by MiriTheRing.
Jazzpirate
Member since Oct 2016
803 posts
Was moechtet ihr, einen schlechten algorithmus oder seeeeeehr lange laufzeit?
Das darfst du dir aussuchen :D Solang's irgendwie DFS mit iterative deepening und endlicher laufzeit ist bin ich happy ;)
pawe
Member since Oct 2014
11 posts
Habe ich das jetzt richtig verstanden, dass man das Codegeruest nicht zwingend verwenden muss, sondern auch was eigenes abgeben darf?
Jazzpirate
Member since Oct 2016
803 posts
Habe ich das jetzt richtig verstanden, dass man das Codegeruest nicht zwingend verwenden muss, sondern auch was eigenes abgeben darf?
Hast du ;) Sonst müsste man euch ja zu C++ zwingen... 0o
Shadow992
Member since Jan 2014
290 posts
Ich habe einmal das bestehende Code-Gerüst ein klein wenig überarbeitet und das alte auf StudOn gegen das Neue ausgetauscht. Im Grunde hat sich nicht viel verändert im Vergleich zu vorher. Ich habe lediglich noch zwei Methoden "resetAllVisitFlags" und "getVisitedNodesCount" hinzugefügt und in der main.cpp einen Bug entfernt, dass das Programm einen SEGMENTATIONFAULT geworfen hat, wenn die Parameterzahl kleiner war als benötigt (return vergessen... Anfängerfehler halt...). Und ein paar Rechtschreibfehler in den Kommentaren entfernt.

Wer schon seinen Code (fast) fertig hat braucht sich keine Sorgen machen. Es wurde nichts an der Struktur, an Aufrufren o.ä. geändert. Das heißt ihr könnt genau so gut mit der alten Version korrekt arbeiten und diese auch abgeben.
This post was edited on 2016-11-10, 17:20 by Shadow992.
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Page:  1  2  next 
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen