Searching trees and game playing Flashcards
(34 cards)
What is the travelling salesman problem?
The minimum cost of a path for a salesperson to starts at any city and must finish at the same city without visiting the same city more than once
What is the travelling salesman problem an example of?
Combinatorial explosion
Unsolved theoretical problems
What is combinatorial explosion?
The feature where the number of solutions for a problem grows exponentially with the problem size
What is the search space of a problem?
Set of all possible solutions to a problem
How do we improve the search technique of a problem
- Define problem into a smaller search tree
- Improve search efficiency
What is the branching factor?
Number of branches a node has
What is the average branching factor?
The average number of branches of all nodes in a tree
Explain how a breadth first search works
- Look at neighbouring nodes first
- Add discovered nodes to the end of the queue
Explain how depth first search work
- Look at children nodes first
- Add discovered nodes to the front of the queue
Explain how uniform cost search works
- Look at neighbouring nodes first
- Add the discovered nodes in order of lowest cost
What is the maximum branching factor?
The maximum number of children a node has
Explain the time, space and optimal completeness of a BFS
b is average branching factor
d is depth of tree
Space: b^d
Time: b^d
Optimal: Yes
Complete: Yes
Explain the time, space and optimal completeness of a UCS
b is the average branching factor
d is the depth of the tree
Space: b^d
Time: b^d
Optimal: Yes
Complete: Yes
Explain the time, space, optimal and completeness of DFS
b is the average branching factor
m is the maximum branching factor
Space: bm
Time: b^m
Optimal: No
Complete: No
What are fringe nodes?
Nodes that have been discovered but have not been processed
What are visited nodes?
Nodes that have been discovered and processed
What are undiscovered nodes?
Nodes which have not yet been discovered nor processed
What is the difference between a blind search and a heuristic search?
- Blind search blindly explores the next node
- Heuristic search searches the next best node using domain knowledge
Explain the concept of the A* search algorithm
Finds shortest path to goal state using heuristics
- Order nodes by:
f(n) = g(n) + h(n)
- g is path cost from initial to current state
- h is heuristic cost from current state to goal state
What does admissible heuristic mean?
if the heuristic never overestimates the actual cost to reach the goal (must be <=)
Provide one guideline in designing a better admissible heuristics
The closer the estimate of the heuristic, the
better! (<= is better than <)
What happens when the heuristic cost from current state to goal state is 0?
Search turns into a UCS, complete and optimal but blind
What happens are h -> ∞? (where the heuristic cost from current state to goal state is very large)
Dominates cost of path from initial state to current state, the search becomes greedy and not optimum
What is a good heuristic?
- It is admissible
- It is close to the actual cost
