Not logged in. · Lost password · Register

Stella
Member since Apr 2018
28 posts
Subject: 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).
Jazzpirate
Member since Oct 2016
803 posts
+1 Stella
we've seen that we can get stuck in between two nodes.
...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?
Stella
Member since Apr 2018
28 posts
.... Okay, so I've kind of forgotten about the DIRECTED in DAG. Nevermind the question, the slides looked just much like a tree :'D
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen