DPS906 Lecture 5

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