Answered

At Westonci.ca, we connect you with the answers you need, thanks to our active and informed community. Explore comprehensive solutions to your questions from knowledgeable professionals across various fields on our platform. Get detailed and accurate answers to your questions from a dedicated community of experts on our Q&A platform.

You have n warehouses and n shops. At each warehouse, a truck is loaded with enough goods to supply one shop. There are m roads, each going from a warehouse to a shop, and driving along the ith road takes d i hours, where d i is an integer. Design a polynomial time algorithm to send the trucks to the shops, minimising the time until all shops are supplied.

Sagot :

Following are the steps of the polynomial-time algorithm:

  • Split the routes according to their categorization
  • Assuming that mid = di of the middle road, low = road with the least di, and high = road with the highest di, we may do a binary search on the sorted list.
  • All shops must be approachable only using these roads for every road, from low to mid.
  • Check if all shops can be reached from[tex]\bold{ low \ to\ mid+1}[/tex] using only these roads.
  • There is a solution if every shop can be reached by road only up to [tex]\bold{mid+1}[/tex], but not up to mid.
  • You can [tex]\bold{set \ low = mid+1}[/tex] if all businesses aren't accessible using both [tex]\bold{mid\ and\ mid+1}[/tex] roads.
  • If every shop could be reached using both mid and mid+1, then set high to mid-1.
  • With these layouts of businesses and roads, no response can be given because [tex]\bold{ low > high}[/tex]
  • You can do this by [tex]\bold{set\ mid = \frac{(low + high)}{2}}[/tex]
  • The new low, mid, and high numbers are used in step (a).

In a minimum amount of time, this algorithm will determine the best strategy to supply all shops.

Learn more:

polynomial-time algorithm: brainly.com/question/20261998

We hope this was helpful. Please come back whenever you need more information or answers to your queries. Thank you for your visit. We're committed to providing you with the best information available. Return anytime for more. We're glad you chose Westonci.ca. Revisit us for updated answers from our knowledgeable team.