Explain how to solve the evacuation route problem, Science

Assignment Help:

You are the mayor of a beautiful city by the ocean, and your city is connected to the mainland by a set of k bridges. Your city manager tells you that it is necessary to come up with an evacuation plan in the event of a hurricane. Your idea is to add a sign at each intersection pointing the direction of the route to the closest of the k bridges. You realize that this can be modeled as a graph problem, where the street intersections are nodes, the roads are edges, and the edge weights give the driving time between two adjacent intersections. Note that some of the roads in your city are one-way roads.

(a) Explain how to solve the evacuation-route problem in O(mlog n) time, where n is the number of intersections and m is the number of streets connecting two adjacent intersections. Note that the number of bridges k is not a constant, that is, it may depend on n and m. Therefore, a running time of O(k · mlog n) is not an acceptable solution. (Although I will give half credit for such a solution.) The output of your algorithm will be a labeling of the intersections, with an arrow pointing to the road to take to the closest bridge.

(b) Some of the bridges can hold more capacity than others. For 1 ≤ i ≤ k, we associate a positive numeric weight ci with each bridge. To encourage people to use bridges with higher capacity, we treat distances to different bridges differently. In particular, if δ is the actual distance from some intersection to bridge i, we assign it a capacity-weighted distance of δ/ci. Therefore, the higher the bridge capacity is, the lower the weighted distance. Present an O(mlog n) time algorithm to solve the evacuation-route problem using capacity-weighted distances. (Again, I will give half credit for a solution running in O(k · mlog n) time. Problem 4 additional info: 2b - some of the bridges will be higher capacity. Their weights will be function of (distance/number of lanes) → this will give us shorter weight and we can treat it as a better route to take even though the distance is farther away.


Related Discussions:- Explain how to solve the evacuation route problem

Explain hiccup reflex actions - respiratory process, Explain Hiccup reflex ...

Explain Hiccup reflex Actions - Respiratory Process It is also a reflex associated with stimulation of sensory endings in the gastrointestinal tract or other tissue through irr

Illustrating an eclipse of the sun, Illustrating an eclipse of the sun ...

Illustrating an eclipse of the sun Hold a small coin a few inches from one eye and close the other eye while looking at the lighted electric bulb on the ceiling of a room. The

Explain examination of urine, Explain Examination of Urine Examination ...

Explain Examination of Urine Examination of urine is done to detect the presence of any abnormal constituent(s) and hence can be used as an important screening test for identif

Define the levels of drugs in urine, Define the Levels of Drugs in Urine ...

Define the Levels of Drugs in Urine Levels of alcohol and barbiturates (a group of drugs derived from barbituric acid that is used to sedate, to control convulsions or to induc

Physical science, Imagine a small observer is positioned in front of cork i...

Imagine a small observer is positioned in front of cork in your picture above. As the cork approaches, the observer measures the wavelength of the waves passing by. How does this w

Hazards of a nuclear world, Hazards of a Nuclear World : The-picture pai...

Hazards of a Nuclear World : The-picture painted abdve  seems rosy. Yet, it does have a few shades of grey. There are many  risks associated with the use of  nuclear fission ene

Medicare operates as vendor payment program, Question 1 Which are the d...

Question 1 Which are the different types of health insurance plans? Explain 2 Define the following terms used in E/M services        a) New and established patient        b) Na

Determine the sieve analysis method of soil texture, Determine the Sieve An...

Determine the Sieve Analysis Method of Soil texture As the name suggests sieve analysis is done using sieves and may give a true distribution of soil particles.  This method i

Determine the term - soil moisture, Determine the term - soil moisture ...

Determine the term - soil moisture The higher the soil moisture, the more rapid is the rate of reaction. The quantity of liming material to be applied to raise the soil pH to a

Explain the hormones in the urine, Explain the Hormones in the urine In...

Explain the Hormones in the urine Increased or decreased production of a hormone in the body alters the amount of hormone or its degraded products excreted in the urine. For ex

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd