Heuristic Search

Question 1

How can be improve upon the previous algorithms?

Answer 1

By having problem specific knowledge, we can guide the search, and perhaps reduce the algorithm time complexity from exponential to polynomial.

Question 2

UCS?

Answer 2

Uniform cost search - orders the agenda as a priority queue using the lowest path cost of a node.

Expand cheapest path first.

• Guaranteed to find cheapest sol if path costs grow monotonically, else exhaustive search is required.
• Still has a high time complexity

Question 3

What is informed strategies ?

Answer 3

Use problem specific knowledge and choose the most promising path first ie the ones that seem to be getting nearer your goal state.

More efficient than blind search!

Question 4

Greedy Search

Answer 4

• Expands the node that appears to be the closest to goal -> short sighted
• Not (necessarily) the cheapest, but far less effort.
• Finds solutions quickly
• May not find a solution if there is one (incomplete)
• Susceptible to false starts
• Only looks at current node, ignores poast

Question 5

A* search

Answer 5

Combine UCS and greedy search - we look at cost so far AND estimated cost to goal.

f(n) = g(n) + h(n)

g(n) is path cost of n
h(n) is expected cost of cheapest solution from n

Aims to minimise overall cost.

• Exponential time
• Admissible heuristic is used
• Keeps all nodes in memory
• Optimal

Question 6

Summary ?

Answer 6

• Heuristic functions estimate costs of shortest paths
• Good heuristics can dramatically reduce search cost
• Greedy best-first search expands lowest h
• A* search expands lowest g + h