Martin: Created page with "=TreeSearch= `TreeSearch(Problem) frontier = {[InitialState]} loop: If frontier empty return fail - no route exists path = removeChoice(frontier) s = path.end..."`


2021-09-14T21:43:49Z
Created page with "=TreeSearch=  <code> TreeSearch(Problem)  frontier = {[InitialState]}  loop:   If frontier empty return fail - no route exists   path = removeChoice(frontier)   s = path.end..."
New page
=TreeSearch=



<code>

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

</code>



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

<code>

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

</code>



=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





{| class="wikitable" border="1" cellspacing="0" cellpadding="5"

|-

! Search type !! Storage !! Complete

|-

| Breadth first || 2^n || Y

|-

| Uniform cost || ~ 2^n || Y

|-

| Depth first || ~n || N

|}

Routing Problem - Revision history

Martin: Created page with "=TreeSearch= TreeSearch(Problem) frontier = {[InitialState]} loop: If frontier empty return fail - no route exists path = removeChoice(frontier) s = path.end..."

Martin: Created page with "=TreeSearch= `TreeSearch(Problem) frontier = {[InitialState]} loop: If frontier empty return fail - no route exists path = removeChoice(frontier) s = path.end..."`