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.
[Official] Assignment 2
I’ve uploaded the second homework sheet at https://kwarc.info/teaching/AI/assignment.pdf
Mistake in Problem 2.2
There is a mistake in the last section of the Problem 2.2 code sample:
% bfs(T) visits every node in beadth-first order
dfs(T) :- ???The second line should be “bfs” instead of “dfs”.
Just a small thing. I think everyone understands it nevertheless. 
I have two questions about exercise 2.3:
-
In the lecture, when we talked about Greedy Search, we also said that we need some kind of heuristics. And in each step, we try to go the the node where the value of h() is the lowest. I don’t really see how we could come up with heuristics for such a general problem. So should we just look for the lowest total path cost then? Or try to follow the edge with the lowest cost first (ignoring the total cost)?
-
Could someone provide an example invocation of the program, so that we can see how edges and stuff like that look like? The current problem description is pretty short
As far as I have understood, the call is invoked by search(Es, F, T, P), where Es represents the edges (i.e. the graph), F and T the nodes of the graph to connect and P a list of the nodes that comprise the resulting path. E.g. search([edge(A, B, 1)], A, B, [A, B]) would be the most simple case (apart from an empty graph) with a graph of two nodes of which the connecting path is searched, that obviously consists of the nodes themselves.
For your first question, I have the same problem regarding the heuristic function
Thank you for the explanation! 
I am now simply using “always take the edge with the lowest cost first” as my heuristic. This is of course not optimal (it does not look at the whole path cost). But one could argue that this is at least some kind of heuristic I hope this is not completely wrong, because it took quite some time to implement this…
I kept this one short on purpose, as a contrast to the very strictly specified 2.2.
So here you have a bit more challenge/freedom how you interpret the assignment.
But the solution I had in mind uses the shortest outgoing edge as the heuristic for choosing the next edge to use.
Perfect, thanks for clarifying this!
so is it still possible to get some examples for the tasks 2.2 and 2.3?
I learn much better, if I have some kind of example query or input to check against or at least something like that.
e.g. "consider this tree t(…t(…t(…),t(…),t(t(t(…))) " or “consider this graph [edge(A,B,5), edge(C,D,7), edge(D,A,2), etc…]” really helps in my opinion
EDIT: btw NO i’m not good with taking a random tree from the tutorial
Regarding examples, it’s straightforward to make your examples. You can generate trees as described in the tutorial or use the tree from A2.1.
@2.1: Does returning to a node in DFS or ITD count as a visit? (so, are there 1 or 3 "A"s in the line for DFS?)
Question to 2.3
We had a question in the tutorial today, that we were not sure about the answer.
In Question 2.3 are the edges bidirectional?
So for edge(A,B,2) can I also travel from B to A for cost 2?
yes
Pretty unfortunate that this wasn’t specified in the assignment. If I see “edge(From, To)”, then I assume that this is a directed one…
But this makes the search more likely to run in circles. Or did I miss something?
In general, what is the position on using Built-In definitions that ISO/SWI-Prolog provides? Usually I can define them myself, but it’s easier to just use member/3, between/3, max_list/2, etc. Also, are exceptions allowed (I was specifically thinking of raising an exception when dfs/bfs/itd is invoked with a non-tree argument).
An specifically regarding 2.3: Are we supposed to generate all paths, all paths without cycles or just the first path we find and then terminate?
Yeah, I think so… Currently rewriting my entire program to do some kind of loop checking. Pretty unfortunate.
Then it’s no greedy search anymore.
Hm but is there another way to build greedy search with undirected edges, without running into infinite loops?
Why should that be the case? If greedy search could fall into loops that easily, regardless of whether the graph is directed or undirected, it wouldn’t make much sense.