Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Minimum Spanning Tree3/25/2009Opening Discussion●Optimization problems–Some problems were simple searches of a 1-D space.–Grocery trip where items can substitute or with combo coupons.–Call tree optimization.–Shortest path.–Most efficient task order waiting tables.–Efficient product production.More Problems–Optimal time allocation.–Shipping networks.–Best meal for lowest price.Approach to Solution●Our problem is connecting the buildings with the least amount of sidewalk.●This is the minimum spanning tree problem and it has a greedy solution.●We want to start at one node and say it is in our “set”. Then we repeatedly make the shortest sidewalk that connects something in the “set” to something outside it.Code●How are we going to go about coding this?●There are two basic approaches to telling if a building is connected yet or not. Give it a boolean or keep two separate lists.●Ideally we will write both of these.Minute Essay●What questions do you have about what we have done this week?●Remember to send me your design
View Full Document
Unlocking...