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

Gases -hazard identification, Gases : Critical temperature is the A substa...

Gases : Critical temperature is the A substance which has a critical temperature below 50°C, has a vapour temperature above which pressure of more than 3 bars absolute (highly

Prejudice-discrimination and stereotype, What are the differences between p...

What are the differences between prejudice, discrimination and stereotype? Prejudice; This is generally referred to as being unfair, bias or opinions towards another person

Explain the pyramids - feature of medulla, Explain the Pyramids - Feature o...

Explain the Pyramids - Feature of Medulla Pyramids are the bulges of ventral surfaces, where most of the lateral corticospinal tracts originating from motor area of cerebrum de

The effect of petrol on surface tension, The effect of petrol on surface te...

The effect of petrol on surface tension Being sure that the plate is has to be clean. It is wise to rinse the plate in cold water for a time before filling it. Instead of soap,

Define transport of carbon dioxide combination with protein, Define the Tra...

Define the Transport of Carbon Dioxide in combination with protein Carbon dioxide forms a neutral carbamino compound with haemoglobin. It combines with the haemoglobin in the r

State the categories of bulky organic manures, State the categories of bulk...

State the categories of bulky organic manures These are evaluated mainly on the basis of their nitrogen content and the amount of organic matter present in them. The two import

Aprons for personal protective devices, Aprons : Additional protection, su...

Aprons : Additional protection, such as a rubber apron is recommended for work with appreciable amounts of chromic acid, hydrofluoric acid and other highly corrosive liquids.

Electronics, what is meant by three phase signal..

what is meant by three phase signal..

Explain the types of artificial kidney dialysis, Explain the Types of Artif...

Explain the Types of Artificial Kidney Dialysis Two types of artificial kidney dialysis are used clinically - Hemodialysis and Peritoneal dialysis

Malnutrition and ill health, Malnutrition and ill health: Are you famil...

Malnutrition and ill health: Are you familiar with the term malnutrition? Malnutrition means either lack of sufficient food or imbalance of nutrients in the diet, resulting in

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