S4-7. At the Albuquerque Zoo, the armadillos, baboons, chihuahuas, dingos, eleph
ID: 3348330 • Letter: S
Question
S4-7. At the Albuquerque Zoo, the armadillos, baboons, chihuahuas, dingos, elephants, flamingos, and gorillas each live in relative peace in separate enclosures. The dis- tances between their enclosures (in meters) are shown in the following chart armadillos baboons chihuahuas dingos elephants flamingos gorillas armadillos baboons chihuahuas dingos elephants flamingos gorillas 40 13 10 20 45 25 41 30 50 34 32 31 42 12 43 46 a) The zookeeper needs to feed the animals, visiting each type of animal one after the other, and returning to the starting point. Find the shortest such path you can. What type of problem is this, and what technique did you use? b) The Animal Rights Council has successfully petitioned zoo management for the installation of fiber-optic cable, so that they can watch Animal Planet. The zoo has asked for your assistance in planning the connections, because fber-optic cable is expensive. Determine how to connect all seven types of animals to each other, using the least total length of cable. What type of problem is this, and what technique did you use?Explanation / Answer
(A) Shortest Hamiltonian Cycle (Travelling SalesMan Problem) : Algorithm = Branch and Bound
(B) Minimum Spanning Tree : Algorithm = Kruskal’s algorithm
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.