Nicht angemeldet. · Kennwort vergessen · Registrieren

Stella
Mitglied seit 04/2018
28 Beiträge
Betreff: 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
Mitglied seit 10/2016
743 Beiträge
+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
Mitglied seit 04/2018
28 Beiträge
.... Okay, so I've kind of forgotten about the DIRECTED in DAG. Nevermind the question, the slides looked just much like a tree :'D
Schließen Kleiner – Größer + Auf diesen Beitrag antworten:
Prüfcode: VeriCode Gib bitte das Wort aus dem Bild ins folgende Textfeld ein. (Nur die Buchstaben eingeben, Kleinschreibung ist in Ordnung.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Weitere Zeichen:
Gehe zu Forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen