Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
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?
The output must have a total cost too. I am pretty sure it has to look like this: dfs(Goal, Tree, Result, Cost)
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
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“
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 endOnly 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).
2 „Gefällt mir“
Thanks a lot for the quick help!
1 „Gefällt mir“
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.
3 „Gefällt mir“
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
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?
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.
No - Whether a node actually leads to the goal state is unknown right until the algorithm terminates.
Exactly 
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?
1 „Gefällt mir“
Yes and thanks for the quick response
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)“).
2 „Gefällt mir“