6.01 Lecture Notes - Lecture 1: Dynamic Programming, Dfs Furniture, Init
13 Apr 2016
School
Course
Professor
Document Summary
Ef cient algorithms for searching underlie many of computer science"s biggest successes. Find the best solution by considering as few cases as possible. We can represent all possible paths with a tree. Represent the grid as a n instance of class grid. Construct a tree and nd a path to the goal. Initialize agenda, meaning the list of nodes to consider, to contain starting node. Repeat the following steps until goal is found or agenda is empty: Replace last node by its successors implement with stack (last in, rst out) work down on branch of the tree before moving to another branch. Remove rst node from agenda and add its successors to the end of the agenda. Consider all path of length n before paths of length n+1. Prune the tree to reduce the amount of work. Pruning strategy one: don"t consider paths that visit the same state twice.
