Not logged in. · Lost password · Register

Stella
Member since Apr 2018
28 posts
Subject: Tree assignments
For the first exercice I am a bit confused as to what " Stop when you expand G" should mean. If I do have a "tree" A-B-C starting with A and I am supposed to stop when expanding B, am I to output only A, as I would print B after expanding, A,B as I print while expanding and do NOT expand C, or A,B,C as C has already been added to the list when expanding B.

For the second exercice: Does the alphabetic order apply here too? Can you give more specific details on what you want of the implementation behaviour? I've done (dfs(Tree),X), which would output a full search on the Tree in the variable X. But in the lecture there has been the notion of goal states, should we implement that too? A description of the expected interfaces would be most useful.

If goal states are given: In which format? Can we assume unique values?

Also for iterative deepening: Should we start with depth 0 or 1 before adding the step size?
This post was edited 2 times, last on 2018-11-11, 01:02 by Stella.
LasagneAlForno
LasagneAlForno
Member since Dec 2017
75 posts
Quote by Stella:
For the second exercice: Does the alphabetic order apply here too? Can you give more specific details on what you want of the implementation behaviour? I've done (dfs(Tree),X), which would output a full search on the Tree in the variable X. But in the lecture there has been the notion of goal states, should we implement that too? A description of the expected interfaces would be most useful.
The output must have a total cost too. I am pretty sure it has to look like this: dfs(Goal, Tree, Result, Cost)

If goal states are given: In which format? Can we assume unique values?
Goals last year were given as a a String Value.
For example in your tree if you search for "B" you should have "AB" as a solution.
Is it important to have unique values? It's not a search tree, so I think we cant assume anything. My implementation doesnt care either
This post was edited on 2018-11-11, 09:20 by LasagneAlForno.
tyr
Avatar
Member since Oct 2014
93 posts
In reply to post #1
+2 Jazzpirate, Stella
Quote by Stella:
For the first exercice I am a bit confused as to what " Stop when you expand G" should mean. If I do have a "tree" A-B-C starting with A and I am supposed to stop when expanding B, am I to output only A, as I would print B after expanding, A,B as I print while expanding and do NOT expand C, or A,B,C as C has already been added to the list when expanding B.
Sorry for the bad phrasing in the assignment, but what you should do here is rather obvious:

For your example [A,B] should be printed. => print every expanded node up to the goal; and then also print the goal

Or as you put it "I print while expanding"

Quote by Stella:
For the second exercice: Does the alphabetic order apply here too? Can you give more specific details on what you want of the implementation behaviour? I've done (dfs(Tree),X), which would output a full search on the Tree in the variable X. But in the lecture there has been the notion of goal states, should we implement that too? A description of the expected interfaces would be most useful.

If goal states are given: In which format? Can we assume unique values?

Also for iterative deepening: Should we start with depth 0 or 1 before adding the step size?

Ok, I ca not answer all of that, wait for Dennis' answer for the rest...

The interface we more or less want is this:

% dfs(GoalValue, Tree, PathString, Cost)
%
% GoalValue is a String e.g. "G"
% Tree is a tree e.g. tree("A",[(1,tree("B",[]))])
% PathString shall contain the correct Path to the goal in the end
%          if you do not like strings, you may implement Path as List
% Cost is a Number that shall contain the summed up cost in the end

Only the iterative deepening differs from that interface, as we have to give a Stepsize

% idfs(GoalValue,Tree,PathString,Cost,StepSize)

BUT you can use something different, as long as it is able to do roughly the same!

(also producing the correct path may be somewhat hard, so if your implementation actually does a BFS for example, but cannot produce the correct path, that is still worth many points)

Can you assume unique values?
> That does not matter, the search does stop, when the first occurrence of a goal (state) is found.

And in the lecture, iterative deepening starts at depth 0 (slide 117).
"Debugging is like doing surgery by randomly squeezing stuff in a patient's body and going like 'lmao tell me when this guy stops breathing'." -- Orteil, Creator of Cookie-Clicker
This post was edited on 2018-11-11, 09:29 by tyr.
Stella
Member since Apr 2018
28 posts
+1 tyr
Thanks a lot for the quick help!
Stella
Member since Apr 2018
28 posts
+3 Nash, tyr, LasagneAlForno
For your service: dfs("G",tree("A",[(1,tree("B",[(1,tree("D",[(1,tree("F",[(2,tree("K",[])),(2,tree("L",[]))]))])),(1,tree("E",[]))])),(3,tree("C",[(1,tree("G",[])),(2,tree("H",[(1,tree("I",[])),(1,tree("J",[]))]))]))]),Path,Cost).
should implement the 3.1 Problem graph :) Nice for testing.
LasagneAlForno
LasagneAlForno
Member since Dec 2017
75 posts
I got one more question ffor the studon-upload:

Everything into one file or one file for each program?
First one is probably easier for the tutor, second one has a better running time
Nash
Member since May 2014
48 posts
What exactly is an expanded node? Is it a node that is visited and compared to the goal (success does not matter), or are they only nodes that lead us to the goal node?

And the cost is probably the cost from the second case, right?

So for the example of tree("A",[(2,tree("B",[])),(3,tree("C",[]))]) with Goal C, would the bfs path be ABC? Because B gets visited before C, or only AC?
And the cost 3?
Jazzpirate
Member since Oct 2016
803 posts
+1 Nash
What exactly is an expanded node?
the "expansion" step in the algorithm is the one where the node under consideration is compared to the goal state and its children are added to the fringe.

or are they only nodes that lead us to the goal node?
No - Whether a node actually leads to the goal state is unknown right until the algorithm terminates.

And the cost is probably the cost from the second case, right?
Exactly :)

So for the example of tree("A",[(2,tree("B",[])),(3,tree("C",[]))]) with Goal C, would the bfs path be ABC? Because B gets visited before C, or only AC?
And the cost 3?
It depends on what you mean by "the bfs path". The path to the goal state is simply AC and the cost of that path is 3. If we ask you for the *order* in which the BFS algorithm visits nodes, what we want to hear is "ABC", because that's the order in which the algorithm visits the nodes :) I assume you mean the former?
Nash
Member since May 2014
48 posts
Quote by Jazzpirate:
I assume you mean the former?

Yes and thanks for the quick response :)
slukas
Member since Mar 2016
41 posts
@tyr
PathString shall contain the correct Path to the goal in the end

Do you mean the path that goes straight to the goal-node or the "searchpath" as in problem 3.1?
LasagneAlForno
LasagneAlForno
Member since Dec 2017
75 posts
+2 Jazzpirate, slukas
Quote by slukas:
@tyr
PathString shall contain the correct Path to the goal in the end

Do you mean the path that goes straight to the goal-node or the "searchpath" as in problem 3.1?

The path that goes straight to the goal node should be your solution, BUT everytime you look at a node (like in 3.1.) you should write this node into the console (for example with "write(Value)").
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