Week 3: AI Search & Problem Solving Flashcards
What is a problem-solving agent in AI?
An agent that formulates goals and problems, searches for solutions, and executes actions to reach a goal state.
List the four main steps of a problem-solving agent.
Goal formulation, problem formulation, search, and execution.
What defines a well-structured search problem?
Initial state, actions, transition model, goal test, and path cost.
What is the initial state in a search problem?
The starting point or configuration of the agent.
What is a transition model?
A function that returns the resulting state after applying an action in a given state: Result(s, a).
What is a goal test?
A test to determine whether a given state satisfies the goal condition.
What is a path cost?
A numerical value representing the cost of a sequence of actions leading to a state.
Define state space.
The set of all states reachable from the initial state through any sequence of actions.
What is the difference between state and node?
State is a configuration; node is a data structure in a search tree that includes state, parent, action, and path cost.
What is the frontier in search algorithms?
A data structure containing nodes that have been generated but not yet expanded.
What is the explored set?
A set of states that have already been visited and expanded to avoid repetition.
What is uninformed search?
Search that uses no domain-specific knowledge; only the problem definition guides the search.
Name two common uninformed search strategies.
Breadth-first search (BFS) and Depth-first search (DFS).
What is breadth-first search (BFS)?
A search that expands the shallowest unexpanded nodes first, using a FIFO queue.
What is depth-first search (DFS)?
A search that expands the deepest unexpanded nodes first, using a LIFO stack.
What is a tree search?
A search method that explores nodes without keeping track of previously visited states.
What is a graph search?
A search method that keeps track of explored states to avoid redundant exploration.
What is a solution in search?
A sequence of actions that leads from the initial state to a goal state.
What are the performance criteria for search algorithms?
Completeness, optimality, time complexity, and space complexity.
What is a toy problem?
A simplified, abstract problem used to test search algorithms (e.g., vacuum world, 8-puzzle).
Give an example of a real-world search problem.
Route finding for GPS navigation or airline travel planning.
What is the 8-puzzle?
A sliding tile puzzle with 8 numbered tiles and one blank, solved by arranging tiles into a goal configuration.
What is a state abstraction?
A simplification of the problem by removing irrelevant details from state descriptions.
What is the difference between BFS and DFS in terms of memory use?
BFS uses more memory due to wide exploration; DFS uses less but may get stuck in deep branches.
