heuristic search

Question 1

what is an uninformed (blind) search

Answer 1

• brute force approach
• no additional information about state or search space
• does not consider costs provided

Question 2

breadth first search
- how?
- time/space complexity?
- complete?

Answer 2

• implemented using FIFO queue data structure
• time complexity: O(b^d) [d being the shallowest solution]
• space complexity: O(b^d)
• complete: will find a solution if it exists (might not be the best one)

Question 3

depth first search
- how?
- time/space complexity?
- complete?

Answer 3

• implemented using LIFO stack data structure
• time complexity: O(b^m) [m being the max depth of any node]
• space complexity: O(bd)
• complete: depends

Question 4

BFS-Optimal

Answer 4

• considers cost from the start
• uses a priority queue ( increasing cost of path )
• guaranteed to find optimal solution
• if not explored but in pq and lower cost, replace

Question 5

what is an informed search

Answer 5

• being able to estimate the cost to goal (usually through heuristics)

Question 6

what is an admissible heuristic

Answer 6

heuristic of node (n) <= minimum cost to reach goal from n

Question 7

best first search
- how?
- time/space complexity?

Answer 7

• expand ‘most promising’ state according to heuristic
• implemented priority queue according to heuristic
• time complexity: O(b^d)
• space complexity: O(bd); O(b^d) if heuristic always 0
• not optimal, IS GREEDY
• duplicate nodes are allowed if heuristic different and not explored

Question 8

A* search
- how?

Answer 8

• considers cost so far + heuristic cost to goal
• f(n) = g(n) + h(n)
• implemented priority queue according to f(n)
• consistent admissible heuristic; optimal
• if f lower, replace and reopen node

Question 9

what is a consistent heuristic

Answer 9

• heuristic n <= sum of heuristic p and step cost from n to p
• a consistent heuristic is also admissible h(g) =0