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 minimum edge that is connected to the graph you are building up that connects to a vertex not already in the graph
2 Minimum Spanning Trees a) Perform Prim’s algorithm to find the minimum spanning tree of the above graph. Pick A as the initial node. Whenever there are more than one node with the same cost, process them in alphabetical order. (BE comes before CE)
Kruskal’s Algorithm - Always pick the minimum edge (unless it creates a cycle) - How do we check cycles?
Weighted Quick Union with Path Compression - Used to represent connectivity between items - Each item belongs to its own set, “union” the items together by connecting the sets together - Sets will have a tree like structure - Optimizations: - Union by weight: connect the root of the “lighter” set to the root of the “heavier” set (determined by number of nodes in the set) - Path compression: when you “find” a node, compress the node and the path to the node by connecting it to the root of the set - 61BL Lab about Disjoint Sets
2 Minimum Spanning Trees b) Use Kruskal’s algorithm to find a minimum spanning tree. Is it the same as the one found by Prim’s? c) Draw the resulting WQU tree at the end of the execution of Kruskal’s. When there are ties, choose the root to be the alphabetically first node. (There may be multiple possible answers)
显示前 16 页。下载资料查看完整内容。
暂无评论。快来抢沙发吧！
评论 (0)
暂无评论。快来抢沙发吧！