Class Notes (836,153)
Canada (509,662)
CMPT 225 (60)
John Edgar (28)
Lecture

CMPT 225 Week 12 Lecture 1

2 Pages
159 Views
Unlock Document

Department
Computing Science
Course
CMPT 225
Professor
John Edgar
Semester
Summer

Description
Dijkstra's AlgorithmAnalysis Want to find path fromAto B - Dijk's gets you fromAto everywhere. If graph doesn't change, Dijk's can be very useful, as you can precompute. However, if you have to check on the fly, not as good, wasting time processing the same thing. Looks in direction that is easy to travel, even if doesn't actually get any closer to the goal. If lots of easy stuff in direction you don't want, end up wasting a lot of calculations/time. No measure of "how long do I think this node will take me to get to the end?" - no end cost estimate. No judgement if path is likely to be a good one. A* helps address both these issues. Doesn't do it with magic though. :( Returns path from start vertex to target end vertex Uses estimate of remaining cost to reach target and direct its search (how long will it take to reach end vertex from current vertex) Essentially the same implementation as Dijk's, but uses a different cost metric f f has to components: g: cost to reach current vertex from start (like Dijk's) h: estimate of cost to reach goal vertex from current vertex (heuristic) f = g + h Key to efficiency is accuracy of h To find optimal path h should be admissible: Should not overestimate cost (underestimating is totally fine) - if overestimate, may reach goal through another path, alg
More Less

Related notes for CMPT 225

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit