AI1 Flashcards
(20 cards)
What are the 4 problem types?
- Single state problem, deterministic, fully observable
- Sensorless problem, non-observable
- Contingency problem, non-deterministic and/or partially observable
- Exploration problem, unknown state space
What are Single-State Problems defined by?
- Inital state
- Actions or successor function
- Goal test, implicit or explicit
- Path cost
What is considered a solution for Single-State problems?
A sequence of actions leading from the initial state to the goal state.
How do we select a state space for Single-State problems?
- Abstract state
- Abstract action
- Abstract solution, set of real paths that are solutions in the real world. Each abstraction is easier than real problem
What is a state?
A representation of a physical configuration.
What is a node?
A data structure constituting part of a search tree.
What is a search strategy?
The particular way you choose to expand nodes.
Along what dimensions are search strategies evaluated?
Completeness
Time complexity
Space complexity
Optimality
What are the definitions for the following:
- Completeness
- Time complexity
- Space complexity
- Optimality
Completeness = does a search strategy find a solution if one exists? (either complete or not complete)
Time complexity = number of nodes generated
Space complexity = maximum number of nodes in memory
Optimality = does it always find the least cost solution? (optimal or not optimal)
What is time and space complexity measured in terms of?
b: max branching factor of search tree
d: depth of the least-cost solution
m: max depth of state space (might be infinity)
Give 4 examples of uninformed search strategies.
BFS
DFS
Depth-limited search
Iterative deepening search
Evaluation of BFS
- complete if breadth is finite
- time O(b^(d+1))
- space O(b^(d+1))
- optimal if cost is 1 per step
Evaluation of DFS
- complete in finite state space
- time O(b^m)
- space O(bm)
- not optimal
Evaluation of iterative deepening search
- complete
- time O(b^d)
- space O(bd)
- optimal if step cost is 1
What is the motivation for bidirectional search?
b^(d/2) + b^(d/2) is much less than b^d
Evaluation of depth limited search
- complete if solution is above depth limit l
- time O(b^l)
- space O(bl)
- not optimal
Evaluation of greedy best first search
- not complete
- time O(b^m)
- space O(b^m)
- not optimal
Evaluation of A* search
- complete (unless there are infinitely many nodes with f<= (G))
- time exponential
- space O(b^d)
- optimal
What is the idea of simulated annealing?
Escape local maxima by allowing some bad moves, but gradually decrease their likelihood. Ar the start of the search, you’re less likely to be at the global optimum. Towards the end there is a high probability that you found optimal solution.
Who is mini and max in mini max search?
Max is traditionally the computer/player - picks moves with the best heuristic value.
Min is the opponent - picks moves that minimise our advantage.
