Question 1:<\/p>\n
Options 1 and 4 are correct. The belief state transition function results in a change to B<\/p>\n
A x O x B \u2014> B is correct (the left hand side can be any order)<\/p>\n
B x A x O \u2014> B is correct<\/p>\n
B x O x A \u2014> A is incorrect<\/p>\n
A x B x O \u2014> O is incorrect
\nQuestion 2:<\/p>\n
Which of the following options are true.<\/p>\n
NO: Breadth-first search is an implementation of the generic, uninformed search algorithm that implements the frontier as a stack<\/p>\n
YES: Depth-first search is an implementation of the generic, uninformed search algorithm that implements the frontier as a stack<\/p>\n
YES: If the branching factor of a breadth-first search is B, and the next path to be selected on the frontier has N arcs, then the frontier has O(B^N) elements.<\/p>\n
From the text and the videos, it should be clear that breadth first search has an exponential space complexity in the depth of the search. With branching factor b, there are b^0 elements (1 element) at depth 0, with no arcs, just a path containing the start node); up to b^1 elements at depth 1 (each element of the frontier contains a path with one arc); up to b^2 elements at depth 2 (each path with two arcs; \u2026.; up to b^N elements at depth N (each element with N arcs), etc<\/p>\n
I found the paragraph in section 3.5.1 to be potentially confusing regarding specific numbers, with references to n-1, n, n+1 regards elements, paths, and arcs. Also, \u201cat least b^(n-1) elements\u201d stated as a lower bound, and then the potential for \u201cn+1 arcs\u201d as an upper bound stated in terms of \u2018arcs\u2019 or \u2018paths\u2019. This is why I used big-O notation to remove any ambiguity. b is regarded as a constant, and so b^(n-1), b^N, b^(N+1) are all O(b^N)<\/p>\n
YES: Depth-first search is probably a good algorithm for finding a Starbucks in downtown Toronto. (see the first video on iterative deepening search at 45 seconds). This may seem like a silly question, but one goal of the quizzes is to ensure as best can that you are looking at the material \u2014 I didn\u2019t think you were likely to forget the Starbuck\u2019s reference if you watched the videos.<\/p>\n","protected":false},"excerpt":{"rendered":"
Question 1: Options 1 and 4 are correct. The belief state transition function results in a change to B A x O x B \u2014> B is correct (the left hand side can be any order) B x A x … Continue reading