Path Searching

Efficient searching

How do you eliminate parts of the search 'universe?'

Uniform Cost Search

- always finds the optimal solution if a solution is found

- sacrifice to these benefits is the cost of getting to a state is minimized

- - G is used a cost function

- - in our example it is total cost of travel from beginning to current position

- expand the search based on smallest total cost

- to stop: a)no more nodes to consider b)goal reached & cost of others is > goal cost

Greedy Search

- Use a heuristic to guide search

- not guarenteed to be optimal

- estimate remaining cost (call the function which does this h)

- guide search by minimizing h

- can get stuck

A*

Best first search : one can find the optimal solution to a search with A*, rather than greedy

searches which cannot be proven to find the most optimal solution to search needs

can be used for path finding, and also other searches

Basically build a tree and apply the A*

- best of greedy + uniform cost

A* uses the same algorithm as the other two

- uses cost & heuristic

- heuristic must be valid estimate of cost

- - cannot overestimate straight line distance is good

To represent a graph

- sparce matrix - quicker, lots of RAM

- adjecency list - less ram, slower

http://en.wikipedia.org/wiki/A*_search_algorithm

## Wednesday, January 23, 2008

Subscribe to:
Post Comments (Atom)

## No comments:

Post a Comment