6.01 Lecture Notes - Lecture 1: Priority Queue, Dynamic Programming, Popping
13 Apr 2016
School
Course
Professor
Document Summary
A path that passes from y in going to x to z can be broken into two parts: x to y and y to z. The shortest path from x to z that goes through y is made up of the shortest path from x to y and the shortest path from y to z. Some actions can be more costly than others, so we need to modify search algorithms to account for action costs. Bfs with dynamic programming fails if path costs are not equal. Enumerate paths in order of their total path cost. Find the path with the smallest path cost, which is the sum of action costs along a path. Priority queue: same basic operations as stacks and queues with two differences: Items are pushed with numeric score, the cost. Popping returns the item with the smallest cost.
