Artificial Intelligence: A Modern Approach Chapter 3: Solving Problems By Searching
Unlock all answers in this set
Unlock answersquestion
Atomic Representation
answer
States of world consider whole with no internal structure visible to the problem solving algorithm.
question
Problem Solving Agent
answer
An agent that uses atomic representation to solve problems.
question
Planning agent
answer
An goal-based agent that uses factored or structures representations.
question
Uninformed Search
answer
Algorithms that are given no information about the problem other than its definition.
question
Informed Search
answer
Algorithms that are given some guidance on where to look for solutions or knows if a state is more promising than another. uses problem-specific knowledge beyond the definition of the problem
question
Goal formulation
answer
Based on the current situation and the agent's performance measure. The first step of problem solving.
question
Goal
answer
A desired outcome that is used to limit what an agent can and will do.
question
Problem Formulation
answer
The process of deciding what actions and states to consider, given a goal.
question
Search
answer
The process of looking for a sequence of actions that reaches the goal.
question
Solution
answer
The output in the form of a action sequence of a search algorithm that takes a problem as input. A path from the initial state to the goal state by actions through the state space.
question
Execution
answer
Performing the action sequence recommended by a solution.
question
Open-loop
answer
Ignoring the percepts received from an environment because the agent already knows what will happen based on the solution.
question
Problem
answer
Consists of Five Components: 1. Initial State 2. Actions 3. Transition Model 4. Path Cost
question
Initial State
answer
The state the agent starts in.
question
Actions
answer
Possible moves that an agent can make in its current state. They are applicable given the state
question
Transition Model
answer
A description of what each action does.
question
Successor
answer
The result states reachable from a given state by performing an action.
question
State Space
answer
Initial state, Actions, Transition Model. Represented by a graph. A path though this is a sequence of states connected by a sequence of actions.
question
Goal Test
answer
Determines if a given state is a goal state.
question
Path cost
answer
A function that assigns a numeric cost to each path. Step cost is the cost of moving from a state by an action to its successor.
question
Optimal Solution
answer
The path with the lowest path cost among all solutions.
question
Abstraction
answer
Removing details from a representation.
question
Search Tree
answer
A graph with the initial state as the root, actions as branches, and successor states as nodes.
question
Expanding
answer
Applying Legal actions to the current state.
question
Generating
answer
Creating a new set of states by performing an action on a given node.
question
Parent Node
answer
The predecessor(s) of a given node
question
Child Node
answer
The successor(s) of a given node
question
Leaf Node
answer
A node with no children
question
Frontier
answer
The set of all leaf node available for expansion at a given point. As known as open list.
question
Search Strategy
answer
The the search algorithm's decision of which node to next.
question
Repeated State
answer
A state that is exactly the same as a state previously expanded. Lead to by a loopy path.
question
Redundant Paths
answer
More than one way to get from one state to another.
question
Explored Set
answer
The set of all states that have been expanded. AKA closed list.
question
Completeness
answer
Is the algorithm guaranteed to find a solution when there is one.
question
Optimality
answer
Does the strategy find the optimal solution?
question
Time Complexity
answer
How long does it take to find a solution?
question
Space Complexity
answer
How much memory is needed to perform the search?
question
Branching Factor
answer
The maximum number of successors of any node.
question
Depth
answer
The number of steps along the path from any node.
question
Total Cost
answer
The path cost plus the search cost which is the time complexity but can including the space somplexity.
question
Breadth-First Search
answer
A strategy in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors etc. Complete if goal is at finite depth. Optimal if path cost is non decreasing. Not practical considering time and space.
question
Uniform-cost search
answer
Expands the node with the lowest path cost. Done by storing the frontier as a priority queue. Goal test applied during expansion not generation. Expands nodes in order of optimality. Complete as long as every step cost is greater than some small positive constant.
question
Depth-first search
answer
Expands the deepest node. Implemented using a LIFO queue. Not optimal. Low space complexity.
question
Backtracking Search
answer
A depth-first search that only generates one successor at a time.
question
Depth-limited search
answer
A depth first search with a predetermined depth limit. Incomplete if limit is less than depth. Not optimal if limit is greater than depth.
question
Diameter
answer
The number of steps to reach any other state from the current state.
question
Iterative Deepening Search
answer
A depth limited search that gradually increases the limit. Generates states multiple times.
question
Bidirectional Search
answer
Two searches: one forward form the root and one backward form the goal. Goal test replaced with frontier intersect test. Requires a method of computing predecessors.
question
Best-first search
answer
Expands nodes base on evaluation function. Use priority queue with estimated cost.
question
Heuristic Function
answer
Estimated cost of the cheapest path form the state as node to a goal state.
question
Greedy Best First Search
answer
Expands the node that is closest to the goal. Incomplete even if finite
question
A* Search
answer
Evaluates nodes by combining cost to get to node and the estimated cost to get from node to goal. Estimated cost of getting to goal through node. Complete and optimal. Tree is optimal if admissible. Graph is optimal if consistent
question
Admissible Heuristic
answer
A heuristic that never overestimates the cost to reach the goal.
question
Consistency
answer
AKA monotonicity. The cost of every successor of a node by an action is not great than the step cost from the successor plus the cost of reaching the goal from the successor.
question
Pruned
answer
Eliminating possibilities from consideration without having to examine them
question
Iterative Deepening A*
answer
Uses f-cost as limit. Each iteration uses smallest f-cost that exceeds last iteration
question
Recursive best-first search
answer
uses f-limit variable to keep track of best alternative path from any ancestor of the current node. Replaces f-value with best f-value of nodes children.
question
SMA*
answer
Drops the node with the highest f-value when memory is full. Backs up forgotten node f-value to its parent.
question
relaxed Problem
answer
A problem with fewer restrictions on the actions.
question
Pattern Database
answer
Storing the exact solution cost all possible solutions to subproblem instance.
question
disjoint pattern database
answer
The combination of two or more subproblem pattern databases which includes all of one and all the solutions that involve moves of the others.
question
Subproblem
answer
Problem definitions with a more general goal than the original problem definitions
