a) Describe and analyze an efficient algorithm to find a path from your current
ID: 3815556 • Letter: A
Question
a) Describe and analyze an efficient algorithm to find a path from your current location to an arbitrary EXIT node, such that the total expected number of vampires encountered along the path is as small as possible. Be sure to account for both the vertex probabilities and the edge probabilities.
b) Describe and analyze an efficient algorithm to find a path from your current location to an arbitrary EXIT node, such that the probability of encountering any vampires at all is minimized.
1. On an overnight camping trip in Sunnydale National Park, you are woken from a restless sleep by a scream. As you crawl out of your tent to investigate, a terrified park ranger runs out of the woods, covered in blood and clutching a crumpled piece of paper to his chest. As he reaches your tent, he gasps, "Get out. while you thrusts the paper into your hands, and falls to the ground. Checking his pulse, you discover that the ranger is stone dead. You look down at the paper and recognize a map of the park, drawn as an undirected graph, where vertices represent landmarks in the park, and edges represent trails between those landmarks. (Trails start and end at landmarks and do not cross. You recognize one of the vertices as your current location; several vertices o the boundary of the map are labeled EXIT. On closer examination, you notice that someone (perhaps the poor dead park ranger) has written a real number between 0 and 1 next to each vertex and each edge. A scrawled note on the back of the map indicates that a number next to an edge is the probability of encountering a vampire along the corresponding trail, and a number next to a vertex is the probability of encountering a vampire at the corresponding landmark (Vampires can't stand each other's company, so you'll never see more than one vampire on the same trail or at the same landmark.) The note warns you that stepping off the marked trails will result in a slow and painful death You glance down at the corpse at your feet. Yes, his death certainly looked painful. Wait, was that a twitch? Are his teeth getting longer? After driving a tent stake through the undead ranger's heart, you wisely decide to leave the park immediately.Explanation / Answer
1) You can use Djikstra's algorithm. Subsitude a weighted vertex A as an edge A1->A2 so that the algo can be applied. Djikstra's algorithm assumes weights only on edges. So, this will give you the correct answer.
2) You can use a Minimum Spanning Tree algorithm. It will give you the least cost to traverse to any node from your current location. Essentially Prim's algo for MST and Djikstra's algo work very similar. You may also Floyd Warshall's algo to find all pair shortest paths.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.