Discussion 13: A* Search and MST’s Christine Zhou Agenda Announcements Review: Dijkstra’s and A* Search Problem 1 Review: MST’s Problem 2 Announcements HW7 due today! Even if you can’t push, remember to commit your work Proj3: Gitlet is out! Due 12/6, Wednesday of dead week Last discussion and lab is next week! :O Tentative dead week schedule: No discussion section Lab sections Final review (no project questions) Each lab will be focused on a particular topic OH Project questions No extra OH Dijkstra’s Algorithm Any lingering questions about Dijkstra’s algorithm? What if we only wanted to find a path from SF to NYC? Would Dijkstra’s work? Yes, but we can do better... A* Search Useful when we have a single target in mind, we only search in a direction that brings us closer to our goal Introduce heuristics: an estimate from any vertex to the goal vertex These values will be provided for you by someone/something Do the same procedure as Dijkstra’s, except add “distTo(v) + h(v)” to the fringe instead of “distTo(v)” Fringe will contain total distances from the start to the end Explore the path to the goal that is the smallest, according to our heuristic Keep exploring until we have popped off the goal Heuristics Admissible: heuristic cannot overestimate distance from the current vertex to the goal Consistent: change in heuristic between v and w cannot exceed actual change in distance between v and w 1 A* Search a) Given the weights and heuristic values for the graph below, what path would A* search return, starting from A and with G as a goal? b) Is the heuristic admissible? Why or why not? Minimum Spanning Trees Tree: must have V-1 edges, no cycles Spanning: the set of edges must connect all vertices Minimum: the spanning tree must have the smallest total weight MST: a tree that connects all vertices with the smallest total weight Prim’s Algorithm Pick an arbitrary starting point Always pick the m