18+19 Flashcards
What does a state space search involve? How do we solve them?
A set of possible states, we know the best states but don’t know how to get there.
These are solved using a search tree: Create a root node at start node, expand the node, finding all states we can reach from it and adding as children. Expand all nodes in this open list. Check if a node is goal state before expanding.
What do we store in our nodes?
The parent node, a set of successor nodes, the state, the action which got us to the state, we could store the depth and a path cost, storing the combined step cost of all actions from start state.
What are the search strategy evaluation criteria?
Completeness:does it find a solution if one exists
Time complexity: number of nodes generated/expanded
Space complexity- maximum number of nodes in memory
Optimality: does it always find a least-cost solution.
What is breadth first search, evaluate it.
Nodes are expanded row by row. This is complete assuming breadth is finite, time complexity is exponential, as is space (both b^(d+1)). An optimal solution will be found as long as cost =1 per step.
What is uniform-cost search, evaluate it.
Like breadth first search, each node has a path cost c, always pick node with lowest cost.
This is complete. The time and space complexity is the number of nodes with less cost than optimal, these are both exponential, but less bad than BFS.
This is optimal.
What is depth first search, evaluate it
Expand most recent generated sucessor node, new successor nodes put at front of open list.
This is not complete if repeated states are not avoided. Time complexity is exponential O(b^m) making it better for dense solutions. Space complexity is linear. This is not guaranteed to find an optimal path.
What is depth-limited search, evaluate it.
Depth-first search with depth limit of I, making no more successors once at this depth. This is complete if I is greater than or equal to required depth. Time is O(b^I). Space is linear. It is not optimal.
What is iterative deepening?
Iteratively perform depth-limited search in tree, starting at 0, then level 1 etc.
This is complete, has time complexity of b^final depth.
Space is linear.
It will find an optimum solution if step cost=1, though it can be modified to explore a uniform cost tree.
What is the closed list?
Holds all states encountered so far, only add a node to open list if it isn’t in closed list. This is important in graph search.
What does informed look-ahead search have compared to non informed?
An evaluation function, giving a cost estimate for potential paths.
What is a heuristic function and what search is only defined by this? Evaluate this search
An estimate of the cheapest path cost from current state to goal(h(n)), greedy search only uses this.
Greedy search is not complete unless repeat states cannot occur. It has exponential time at worst, but a good heuristic can make it much faster. It keeps all nodes in memory so exponential space. It is not guaranteed to find an optimal solution.
What is A* search? Evaluate it
Evaluation function is c(n) + h(n). So current path cost + heuristic cost.
It is provably optimal and complete(unless infinite nodes with cost less than solution) if it uses an admissable heuristic.
Exponential time, but typically does far better.
Space: all nodes in memory, exponential.
What is an admissable heuristic?
One which never over estimates the cost of the path from the current state to goal state.
What is a consistent heuristic?
One which guarantees the heuristic for the child is greater than or equal to the heuristic of the parent - the cost of the path from the parent to the child.
Consistent heuristics can prevent returning to previously checked nodes and ensures the first path found to a given state is the shortest.
