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?
1 „Gefällt mir“
… Okay, so I’ve kind of forgotten about the DIRECTED in DAG. Nevermind the question, the slides looked just much like a tree :'D