Routing Problem

From sheep
Jump to navigation Jump to search

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