Find the probability of survival for each leg in the network and draw the network with these probabilities shown. 2. What is the probability of surviving a journey from 1 to 6 along legs (1,2), (2,5) and (5,6)? 3. Prove that for this problem the Principle of Optimal holds: (i.e. “The optimal path from any node to the end does not depend on how you arrived at that node” – adapt the three line proof given in the lecture for the shortest/longest path to this case) and derive a DP recurrence for for this problem.
The network below represents a network of (rather unstable) rope bridges between six villages in some remote corner of Mangrovia. The bridges are so narrow that travel is only possible in one direction (as indicated by the arrows). Further the bridges are now so worn that there is an uncomfortable
high chance of them collapsing when used.
Assume that the edge labels are the likelihood (as percentage) of a bridge collapsing when the crossing is attempted. So for example there is a 20% chance of the bridge from vertex 2 to 5 collapsing, or a probability of 0.8 of getting across unharmed.
please
1. Find the probability of survival for each leg in the network and draw the network with these probabilities shown.
2. What is the probability of surviving a journey from 1 to 6 along legs (1,2), (2,5) and (5,6)?
3. Prove that for this problem the Principle of Optimal holds: (i.e. “The optimal path from any node to the end does not depend on how you arrived at that node” – adapt the three line proof given in the lecture for the shortest/longest path to this case) and derive a DP recurrence for for this problem.
4. Showing your working on the diagram, solve the problem by DP to find the safest route from 1 to 6.
5. Repeat the calculation in a table form.
Step by step
Solved in 2 steps with 2 images
