Search

Question 1

What’s the difference between a reflex and a planning agent?

Answer 1

Reflex agents consider the present and, maybe, the past, but not the future. Planning agents, on the other hand, ask, “What if?” and consider potential consequences of their actions.

Question 2

What does a search problem consist of?

Answer 2

A state space, a successor function, a start state, and a goal test.

Question 3

What is the solution of a search problem?

Answer 3

A sequence of actions that transforms the start state to a goal state.

Question 4

Describe state space graphs

Answer 4

Mathematical representations of a search problem. Nodes are abstracted configurations of the world, and arcs from nodes lead to their successors.

Question 5

Describe state space trees

Answer 5

Similar to graphs, each node is a world configuration. The start is at the root; each child is a successor. A trail to a leaf corresponds to a plan to achieve that leaf state from the start.

Question 6

What goes in a search tree’s “fringe”?

Answer 6

Partial plans under consideration

Question 7

What kind of data structure does a DFS use for its fringe?

Answer 7

A LIFO stack

Question 8

What’s the DFS time complexity?

Answer 8

O(b^m), where b is branching factor and m is the number of tiers in the tree

Question 9

What’s the DFS space complexity?

Answer 9

O(bm), where b is branching factor and m is the number of tiers in the tree

Question 10

Is DFS complete or optimal?

Answer 10

It’s only complete if it’s not an infinite tree. It isn’t optimal because it looks for the “leftmost” solution regardless of the depth of that solution. What if the solution can also exist on the shallow right side of the tree?

Question 11

What kind of data structure does a BFS use for its fringe?

Answer 11

A FIFO queue

Question 12

What’s the BFS time complexity?

Answer 12

O(b^s), where b is branching factor and s is the depth of the solution

Question 13

What’s the BFS space complexity?

Answer 13

O(b^s) (more than DFS)

Question 14

Is BFS complete or optimal?

Answer 14

It’s complete if a solution exists, and optimal if all costs are 1.

Question 15

What kind of data structure does UCS use for its fringe?

Answer 15

A priority queue, where the priority is based on cumulative cost

Question 16

What’s the UCS time complexity?

Answer 16

O(b^(C/epsilon)), where b is branching factor, C is the solution cost, and episolon is the minimum arc cost

Question 17

What’s the UCS space complexity?

Answer 17

O(b^(C/epsilon)), where b is branching factor, C is the solution cost, and episolon is the minimum arc cost

Question 18

Is UCS complete or optimal?

Answer 18

Yes on both counts; conditions of completeness are that it has a finite cost and minimum arc cost (epsilon) is positive

Question 19

What’s a heuristic?

Answer 19

A purpose-made function that estimates how close a state is to a given goal.

Question 20

What does A* search combine?

Answer 20

The backward (path) cost of UCS (g(n)) and the forward cost of greedy search (h(n)) to produce f(n)

Question 21

When should A* search stop? When SHOULDN’T it?

Answer 21

Stop when it dequeues a goal; don’t when it enqueues a goal.

Question 22

What’s an admissible heuristic?

Answer 22

A heuristic with cost >=0 and <= the actual path cost

Question 23

Contrast UCS and A*

Answer 23

UCS expands equally in all directions, whereas A* expands mainly towards its goal

Question 24

What defines a consistent heuristic?

Answer 24

The arc cost according to the heuristic is less than the actual arc cost for each arc.