Routing Problem

TreeSearch

TreeSearch(Problem)

frontier = {[InitialState]}
loop:
 If frontier empty return fail - no route exists
 path = removeChoice(frontier)
 s = path.end
 if goalTest(s) return path
 for a in actions
   add [ path + a -> result(s,a)] to frontier

Key is how removeChoice is made

Must continue until the next path returned from the frontier is the goal to get optimal route - i.e. not testing if found goal when adding state to frontier

Tree search will return to start

GraphSearch

Graph search remembers nodes visited GraphSearch(Problem)

frontier = {[InitialState]}
explored = {}
loop:
 If frontier empty return fail - no route exists
 path = removeChoice(frontier)
 s = path.end
 add s to explored
 if goalTest(s) return path
 for a in actions
   add [ path + a -> result(s,a)] to frontier unless result(s, a) in explored

Breadth first search

Looks for shortest (steps) next path

Uniform cost search

Looks for cheapest next

A* (best estimate shortest cost first)

f=g(path) + h(path) Where:

• g(path) = path cost so far
• h(path) == h(state) = estimate distance to goal (heuristic)

Admissible heuristics

heuristic must be optimistic

• h(s) < true cost
  • h - never overestimates

Finding lowest f :=

• minimise g - minimise path so far
• minimise h - focus search

best heuristic - h = max(h1, h2) - where h1, h2 admissible

Finding a good heuristic

Take definition of problem, remove a constraint. Removing constraint effectively is adding a new operator that makes the problem simpler.

Complete

Will algorithm find goal given infinite set

Search type	Storage	Complete
Breadth first	2^n	Y
Uniform cost	~ 2^n	Y
Depth first	~n	N