Not logged in. · Lost password · Register

nenas
Avatar
Member since May 2012
229 posts
Subject: Problem 2.6 Reihenfolge: CheckGoal <-> Expand
Hi,

ich habe eine Frage zur 2.6. Wird hier vom Aufgabensteller angenommen, das DFS zuerst den aktuellen Knoten erweitert und dann überprüft ob er einen Zielzustand repräsentiert, oder anders rum, wie in den Folien. Wenns so wie in den Folien sein soll, dann gibt es imo. keinen Pfad zum Ziel, in dem genau 6 Knoten erweitert werden.
Oder verstehe ich hier etwas komplett falsch?

Gruß
nenas
Sometimes, I guess there just aren't enough rocks.
Jazzpirate
Member since Oct 2016
803 posts
but its sensors only allow it to detect the source once it is in the same cell with it.
Ich interpretiere das als "Ein Knoten muss expandiert werden um als Zielknoten erkannt zu werden" (Stell dir vor, dass dei Zielfelder als einzige den Zustand "Laden" zulassen; dann muss das Feld natürlich expandiert werden, damit dieser Zustand als erreichbar erkannt wird)
nenas
Avatar
Member since May 2012
229 posts
Danke für die schnelle Antwort!

Quote by Jazzpirate:
but its sensors only allow it to detect the source once it is in the same cell with it.
Ich interpretiere das als "Ein Knoten muss expandiert werden um als Zielknoten erkannt zu werden" (Stell dir vor, dass dei Zielfelder als einzige den Zustand "Laden" zulassen; dann muss das Feld natürlich expandiert werden, damit dieser Zustand als erreichbar erkannt wird)

Aber das muss ich doch nur machen, wenn ich "Laden" zu den Zuständen hinzufüg. Wenn meine Zustände nur die Tiles sind, und ich als goal-test den Sensor verwende, dann muss ich den aktuellen Knoten nicht expandieren? Schließlich wird ja z.b. beim Saugerproblem das Überprüfen, ob auf der aktuellen Position Schmutz liegt, auch nicht als Zustand modeliert.
Sometimes, I guess there just aren't enough rocks.
Jazzpirate
Member since Oct 2016
803 posts
Wenn meine Zustände nur die Tiles sind, und ich als goal-test den Sensor verwende, dann muss ich den aktuellen Knoten nicht expandieren?
Wenn du den aktuellen Knoten nicht expandieren müsstest für einen goal-test, wüsstest du ja ob der nachfolgende Knoten ein goal ist bevor du ihn betrittst, also widerspräche das der Aufgabenstellung ;)
Schließlich wird ja z.b. beim Saugerproblem das Überprüfen, ob auf der aktuellen Position Schmutz liegt, auch nicht als Zustand modeliert.
Das ist richtig; "aufladen" ist aber eher eine Aktion; kein Zustand, oder? ;)
So oder so - ich hab ja nur versucht dem ganzen eine Art "Semantik" verpasst die den Zustandsbaum selbst etwas sinniger macht (zugegebenermaßen war das keine gute Semantik :D ); aber eigentlich kannst du dir auch vorstellen, dass die Räume halt undurchsichtige Türen haben und du eben den Knoten expandieren (=den Raum betreten) musst um zu wissen ob er eine Batterie enthält ;)
nenas
Avatar
Member since May 2012
229 posts
Quote by Jazzpirate:
Das ist richtig; "aufladen" ist aber eher eine Aktion; kein Zustand, oder? ;)

Ja, das macht Sinn.

Quote by Jazzpirate:
aber eigentlich kannst du dir auch vorstellen, dass die Räume halt undurchsichtige Türen haben und du eben den Knoten expandieren (=den Raum betreten) musst um zu wissen ob er eine Batterie enthält ;)

Achso, ich dachte einen Knoten expandieren bedeutet alle möglichen Nachfolger Knoten berechnen und zum Suchbaum hinzufügen.
Jedenfalls habe ich jetzt eine Idee das besser zu modelieren, vielen Dank. :)
Sometimes, I guess there just aren't enough rocks.
Jazzpirate
Member since Oct 2016
803 posts
Achso, ich dachte einen Knoten expandieren bedeutet alle möglichen Nachfolger Knoten berechnen und zum Suchbaum hinzufügen.
Genau das bedeutet auch; die Nachfolgerknoten entsprechen aber natürlich den von-diesem-Zustand-aus-durch-Aktionen-erreichbare-Zustände; i.e. expandieren entspricht gewissermaßen "den Zustand annehmen und gucken, was ich damit tun kann" ;)
10pointsforgryffindor
Member since Oct 2016
7 posts
Subject: BFS
hi,
ich beziehe mich auf die BFS-Teilaufgabe:

in der Lösung steht:
"BFS would find the solution at depth 3, so for this it will make all the expansions until depth
2, so 1 + 4 + 16, then on the last level, the solution would be the second node expanded because
the correct path is down down right. The first node will correspond to down down down, but the
next will be the right solution. So 1 + 4 + 16 + 2 = 23."

Das leuchtet mir in der Theorie ein, aber in depth 2 des BFS-Suchbaums werden Zellen mitgezählt, die außerhalb des erlaubten Bereichs liegen, oder? zB das Feld, das "rechts" des Feldes 10 liegt. Warum zählen wir diese mit? Sie können ja nicht expandiert werden, es wird nur "versucht", sie zu erreichen.

Danke schon mal!
LG
Jazzpirate
Member since Oct 2016
803 posts
Ja, das ist richtig, das hängt davon ab, wie man nachfolger zählt. Zwei mögliche Modelle:
1. Expandieren eines Knotens liefert mir ausschließlich die Felder, die tatsächlich existieren, dann wäre 16 falsch
2. Expandieren eines Knotens liefert "nonexistent" falls das Feld gar nicht existiert, und 4 nachfolger (l,r,u,d) andernfalls, dann wäre 16 richtig und ich merke erst beim "versuch, durch die wand zu laufen", dass die richtung unzulässig ist.

die lösung geht wohl (implizit) von 2. aus, du gehst scheinbar von 1. aus. 1. scheint mir das intuitiv sinnigere modell, erfordert aber "existenz-checks" bereits beim expandieren des vorgängers, 2. ist insofern einfacher, als dass die nachfolgerfunktion uniform ist und ein "existenz-check" erst beim expandieren durchgeführt wird.

Sprich: Ist ein trade-off zwischen Knotenzahl und "Komplexität" der Nachfolgerfunktion. (1 liefert weniger knoten, muss aber mehr beim nachfolger berechnen tun, 2 liefert mehr knoten, aber die nachfolgerfunktion ist trivial)
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:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen