4) (2pts) Your company is working on a ridesharing service that matches multiple

Question

4) (2pts) Your company is working on a ridesharing service that matches multiple users together for short rides to their locations. It does this by trying every possible assignment of carpooling riders for all requests in a 15 minute window, and choosing the one that causes people to get to their destinations as fast as possible on average. Upon further analysis, you realize that your program spends almost all of its time measuring the waiting times for rideshare arrangements that end up being much worse than the optimal arrangement. What kind of algorithm can you use to fix this problem? a. Greedy b. Divide and Conquer c. Dynamic Programming d. Backtracking e. Branch and Bound

Explanation / Answer

We can use dynamic programming to solve the problem above.

The core idea of dynamic programming is to avoid repeated work by remembering partial results. This is a very common technique whenever performance problems arise.

We can find the shortest path between source and the series of destination (one by one) out of the various available paths.

And find the optimal one and also store the waiting time of it.which will help in the next ridesharing task.

Hope this will help

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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