Member since Apr 2018
28 posts

20190205, 15:07 #1
Subject: Question about mock exam
For 1.3 why is it that a circlefree 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 5680 if thius is a line with the heuristics and we start at 5 we never actually reach the goal (0). 
Member since Oct 2016
758 posts

20190205, 15:12 #2
+1 Stella
...demonstrating that the graph isn't circlefree. 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 circlefree, then the searchtree on it isn't necessarily finite, because of those infinite branches. Does that make sense? 
Member since Apr 2018
28 posts

20190205, 18:39 #3
.... Okay, so I've kind of forgotten about the DIRECTED in DAG. Nevermind the question, the slides looked just much like a tree :'D

Datenschutz 
Kontakt
Powered by the Unclassified NewsBoard software, 20150713dev,
© 20032011 by Yves Goergen