Not logged in. · Lost password · Register

 Member since Apr 2018 28 posts 2018-11-11, 01:43   #1   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, 02:02 by Stella.
 LasagneAlForno Member since Dec 2017 75 posts 2018-11-11, 06:59   #2   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, 10:20 by LasagneAlForno.
 ModKrypt Tutor WS19/20 Member since Oct 2014 106 posts 2018-11-11, 10:24   #3   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, 10:29 by tyr.
 Member since Apr 2018 28 posts 2018-11-11, 11:06   #4   +1 tyr Thanks a lot for the quick help!
 Member since Apr 2018 28 posts 2018-11-11, 22:59   #5   +3 LasagneAlForno, tyr, Nash 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 Member since Dec 2017 75 posts 2018-11-12, 16:17   #6   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
 Member since May 2014 48 posts 2018-11-13, 10:49   #7   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?
 Member since Oct 2016 806 posts 2018-11-13, 11:32   #8   +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?
 Member since May 2014 48 posts 2018-11-13, 11:40   #9   Quote by Jazzpirate:I assume you mean the former? Yes and thanks for the quick response
 Member since Mar 2016 41 posts 2018-11-13, 12:45   #10   @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 Member since Dec 2017 75 posts 2018-11-13, 16:52   #11   +2 slukas, Jazzpirate 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: Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys:
Special characters:
Go to forum
Datenschutz | Kontakt