Mulder and Scully have computed, for every road in the United States, the exact

Question

Mulder and Scully have computed, for every road in the United States, the exact probability that someone driving on that road won’t be abducted by aliens. Agent Mulder needs to drive from Langley, Virginia to Area 51, Nevada. What route should he take so that he has the least chance of being abducted?

More formally, you are given a directed graph G = (V, E), where every edge e has an independent safety probability p(e). The safety of a path is the product of the safety probabilities of its edges. Design and analyze an algorithm to determine the safest path from a given start vertex s to a given target vertex t.

For example, with the probabilities shown above, if Mulder tries to drive directly from Langley to Area 51, he has a 50% chance of getting there without being abducted. If he stops in Memphis, he has a 0.7 × 0.9 = 63% chance of arriving safely. If he stops first in Memphis and then in Las Vegas, he has a 1 ? 0.7 × 0.1 × 0.5 = 96.5% chance of being abducted! (That’s how they got Elvis, you know.) Although this example is a dag, your algorithm must handle arbitrary directed graphs.

Explanation / Answer

If a person is travelling from Place A to place Z; The probability of his getting abducted (A) = p(A) (Say) and not getting abducted (N) = P(N) say;

For any travel we know that p(A) + p(N) = 1;

The given diagram shows probability of not getting abducted;
Thus from Y to Z if a person travels directly his probablity of getting abducted P(A)y to z = 1- P(N); Thus P(A)Langley to Area 51 = 1- 0.5 = 0.5;

If say n intermediary stops are taken at a1,a2,a3,...an then probability of getting abducted in the overall journey =
1- probability of getting abducted in none of the journeys;

P(A) y to a1 to a2 to a3 to ...an to z = 1- [ P(N)y to a1 *P(N)a1 to a2 *P(N)a2 to a3 .....*P(A)an to z ]

and Probability of not getting abudcted at all: P(N) y to z overall = 1- P(A) y to a1 to a2 to a3 to ...an to z

Thus if one has to move from a start vertex S to a target vertex T; Calculate the P (N) s to t for individual routes and compare which is the safest route or highest value of that probability. Taking that route would be the safest;

For journey from Langley to Area 51, the possible routes and inidivudal probability of getting abducted are shown below:
1) Langley to Area 51 = 1- 0.5 = 0.5
2) Langley to Las Vegas to Area 51 = 1- 0.2*0.5 = 1-0.1= 0.9
3) Langley to Las Vegas to Memphis to Area 51 = 1- 0.2*0.1*0.9 = 1- 0.018 = 0.982
4) Langley to Memphis to Area 51= 1- 0.7*0.9 = 0.37
5) Langley to Memphis to Las Vegas to Area 51= 1- 0.7*0.1*0.5= 1-0035= 0.965

Thus the most risk route is number 3 and safest route is 4 from langley to memphis to area 51;
For least chance of beign abducted when travelling from Langley start point to Area 51 end point he should take the route from Langley to Memphis to Area 51

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.