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.

**Question about mock exam**

For 1.3 why is it that a circle-free graph never creates an infinite search tree.

E.g. with greedy search and a bad heuristic like in the romania example, we’ve seen that we can get stuck in between two nodes. Like 5-6-8-0 if thius is a line with the heuristics and we start at 5 we never actually reach the goal (0).

…demonstrating that the graph isn’t circle-free. In particular it’s not a tree. If you can go from A to B, and from B to A, you immediately get an „infinite branch“ A->B->A->B->A->B->…

The terminology is important here. If your *state space* is already a tree, and it is finite, then such an infinite branch can not exist. If your state space is finite but not circle-free, then the search-tree on it isn’t necessarily finite, because of those infinite branches.

Does that make sense?

… Okay, so I’ve kind of forgotten about the DIRECTED in DAG. Nevermind the question, the slides looked just much like a tree :'D