Module 3 Flashcards
What is an agent that plans ahead
Problem solving agent
What spectrum do problem solving agents use
Atomic structure
What spectrum do planning agents use
Factored or structured
What is an informed algorithm
Agent can estimate how far it is from the goal
What is uninformed algorithm
No estimate available
What are the four phases of problem solving agents
Goal formulation, problem formulation, search, execute
What do search problems consist of?
States space - S Initial state - S0 Action in state - A(s) Transition model - Results (s,a) Goal test - G(s) Action cost c(s,a,s’)
What is a solution
An action sequence that reaches goal state
Optimal solutions reaches goal state with least steps
What are standardized problems
Can be given precise exact descriptions and can compare performance of algorithms
What is a real world problem
Solution people use and formulation is idiosyncratic
Characteristics of state space graphs
Nodes are abstract world configurations
Arcs represent successors
Goal test is a set of goal node(s)
Each state occurs once
State graph vs search tree
Each node in search tree is a path in state graph
Name all search data structures
node. state - current state of node
node. parent - parent of current node
node. action - action through which arrived at current node
node. path-cost - total cost to current node from initial node
List types of nodes, are they reached?
Generated nodes and expanded nodes
Both nodes are considered reached
List frontier functions
IsEmpty - returns true/false
Pop - removes top node and returns it
Top - returns top node
Add -inserts node into place
What measures are there for problem solving performance
Completeness - is algorithm guaranteed to find solution and reports failure
Cost optimality - does it find solution at lowest cost
Time complexity - how long does it take to find a solution
Space complexity - how much memory is needed
List BFS properties ( space + search , complete, optimal)
Space + Search time - O(b^s) B - nodes at solution level S - depth at solution level Complete Optimal if costs are equal FIFO
List UCS properties ( space + search , complete, optimal)
Space + Search time - O( b ^ C* / E ) C* - total cost of solution E - least cost of arc Complete if C* finite Optimal Priority Queue
List DFS properties ( space + search , complete, optimal)
Search time - O( b ^ m) Space - O (bm) B - nodes at lowest level M - levels Not Complete if M infinite Not Optimal LIFO
When is BFS better than DFS
On sparse graph with low branching
Requirement to find optimal solution and search entire space
When there is a shallow solution , s
When is DFS better than BFS
Where tree like search feasible , less memory
When solution at all m, and common at m
What is iterative deepening
Tries to get DFS space advantage with BFS time advantage
Runs DFS with level limits
What is the purpose of an informed search
Guide the search towards the goal using domain specific hints called heuristics
More efficient that uninformed
What are heuristics and notation
Hints H(n) - est cost of cheapest path from node to goal state
List properties of Greedy best first search
Expands node with lowest h(n) value It’s complete Search and Time - O ( V ) With good h(n) - O (bm) Con - does not consider cost already incurred
List properties of A* search
Expands node most likely to be optimal path
Expands node with lowest g(n) + h(n) value
- g(n) cost from root to node
- h(n) optimal cost node to goal
Priority queue
Complete
When is heuristic admissible
If 0<= h(n) <= h*(n)
where h*(n) is true cost to nearest goal
What problems are Admissible heuristics a solution for
Relaxed problems
