IV: Tree Search Techniques Flashcards
What is combinatorial explosion?
Rapid growth of the complexity of a program - exponential growth of solutions
Why is search so important?
A lot of problems can be seen as a ‘search’ for the right answer
What is a search space?
The set of all possible solutions
What is the input to a search algorithm?
The problem
What does a search algorithm return?
A solution to the problem
In a search tree what is the depth of a node?
The number of branches from the root node to the node
What is the depth of a search tree?
Depth of the deepest level node
How do states of a problem convert to a search tree?
They are the nodes
What is the search space in the search tree model?
The set of all reachable states so all nodes in the tree
How do you model operators in a problem/game to the search tree model?
They’re the branches as they are actions that move the model from one state to another
What is a neighbourhood within a search problem?
All possible states reachable from a given state
What is a goal test within a search problem?
A test to a state to tell if the search reached a state that solves the problem
What is path cost within the search tree model?
Cost of taking a particular path
In the search tree model, what is the branching factor?
Average number of branches of all nodes in a tree
In search tree model, do we want a large or small branching factor?
Small as possible
What does BFS stand for?
Breadth - First - Search
What does BFS do differently to a general search algorithm?
Root node is expanded first, expand all nodes at level d before expanding level d+1
What does a queue function do for BFS?
Add a node to the end of the queue to test
What are the three types of nodes during a BFS (tree search)?
- Fringe nodes (open nodes / leaves)
- Visited nodes (closed nodes)
- Undiscovered nodes
In BFS, what is a fringe node?
- has been discovered
- has not been processed yet
e.g. child nodes not explored and hasn’t been tested to see if goal
In BFS, what are visited nodes?
- have been processed
e.g. nodes explored and tested
What is the difference in a search tree between a goal state and a solution?
A goal state is just a node that passes tests, the solution is the path taken to get there
What are the four criteria for evaluating a search technique?
- Completeness
- Time complexity
- Space complexity
- Optimality
Define completeness as an evaluation criteria.
Is the search tree guaranteed to find a solution
Define time complexity as an evaluation criteria.
How long does it take to find the solution?
Define Space complexity as an evaluation criteria.
How much memory is required to complete the task
Define Optimality as an evaluation criteria.
Can it find the optimal solution? (not just any)
How complete is BFS as a search technique?
A solution will always be found, not necessarily the most optimal, since it won’t go deeper if it’s found a solution
What does big O mean ?
The worst case scenario / most time expensive solution - i.e. if its the very last solution
What are b and d in search tree notation?
b - average branching factor
d - depth of the search tree
What is bd in search tree notation?
Time complexity and space complexity
What does DFS stand for?
Depth First Search
What is the DFS method?
Root node is expanded first, then one whole branch is explored before exploring another branch/
- its queuing functions adds nodes to the front of the queue when discovered
What is space complexity like for DFS?
Only stores the path from the root to the leaf on current branch and unexpanded neighbour nodes
- better than BFS
How is the time complexity for DFS?
Bad, worse than BFS, in the worst case it’s bm
How does DFS weigh up in terms of completeness?
With an infinite branch the search would never terminate if there’s no goal state in that branch - not complete
What does UCS stand for?
Uniform Cost Search
How does UCS work?
Nodes are ordered in the queue based on price (nearest is cheapest) therefore when the closest node in queue is explored it’s the cheapest
What is the point of UCS?
For when different paths cost different amounts (for any kind of ‘cost’ minimisation)
How complete is UCS as a method?
Always finds a solution
How optimal is UCS?
Always explores cheapest nodes first so always finds optimal
How do BFS and UCS compare using the four criteria? What is the caveat here?
Same for all four criteria, BFS can only be applied on trees where all branches have the same cost
What kind of problems can UCS be applied to?
Any as long as costs never decrease along the branches
When is DFS useful?
Useful if its adapted for specific problems
How is Heuristic search different from blind?
guidance is used to consider states rather than blindly adding to front or back of queue or cost.
How does Heuristic search work?
Next best node is explored which is more likely to lead the goal state
What is the A* method an example of?
Heuristic search
What does A* method combine when it evaluates a node?
The path cost so far and an estimated heuristic cost to the goal
In A* method, what does f(n) = g(n) + h(n) mean?
g(n) - path cost from initial state to current state n
h(n) - heuristic cost from current state to goal state n
f - estimated cost of the cheapest solution through n
What does A* become if h is 0?
UCS method, since its only using path cost
What happens to A* if h is too large?
h dominates g and becomes Greedy search
What actually is h as a guess (in A*)?
A lower bound
Why is h a lower bound guess in A*?
To ensure the solution is actually optimal, (the heuristic search isn’t overestimating any of the path costs)
What does it mean for the heuristic to be admissable?
The heuristic cost estimate is the lowest possible and never an overestimate
Give an example of the heuristic estimate being a lower bound in A*.
If the cost is distance to travel between cities then the lowest bound is the straight line distance because you can’t travel a shorter distance than that
