Search Flashcards
What’s the difference between a reflex and a planning agent?
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.
What does a search problem consist of?
A state space, a successor function, a start state, and a goal test.
What is the solution of a search problem?
A sequence of actions that transforms the start state to a goal state.
Describe state space graphs
Mathematical representations of a search problem. Nodes are abstracted configurations of the world, and arcs from nodes lead to their successors.
Describe state space trees
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.
What goes in a search tree’s “fringe”?
Partial plans under consideration
What kind of data structure does a DFS use for its fringe?
A LIFO stack
What’s the DFS time complexity?
O(b^m), where b is branching factor and m is the number of tiers in the tree
What’s the DFS space complexity?
O(bm), where b is branching factor and m is the number of tiers in the tree
Is DFS complete or optimal?
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?
What kind of data structure does a BFS use for its fringe?
A FIFO queue
What’s the BFS time complexity?
O(b^s), where b is branching factor and s is the depth of the solution
What’s the BFS space complexity?
O(b^s) (more than DFS)
Is BFS complete or optimal?
It’s complete if a solution exists, and optimal if all costs are 1.
What kind of data structure does UCS use for its fringe?
A priority queue, where the priority is based on cumulative cost