CS124 Problem Set 9
Due April 25
We often need to get to
one place from another in a city, and on the way we want to
visit some other places in a given order. For instance, suppose
that today is your grandfather's birthday and you will go to your
grandparents' house to celebrate. But you also need to go to a number of other
places during the day, and you plan to visit them in the following order:
- Start from your home.
- Go to any bank ATM machine for some cash.
- Go to any McDonald for breakfast.
- Go to any Kinko's to fax an important document
that is due early this morning.
- Go to any post office to mail your graduate school applications
that are due today.
- Go to any Chinese restaurant for lunch.
- Go to any barber shop for a hair cut.
- Go to any Star Market to buy your grandfather a nice birthday cake.
- Finally, go to your grandfather's house.
The goal is to find a shortest route that allows you to reach the
destination and visit all the intermediate places in order.
Your Challenge:
Suppose you are the chief designer of an online map
system. The system accepts from the
user the source, the destination, and an ordered list of sets of
intermediate places the user has to visit, and returns a shortest
route to the user.
Problem 1
Formulate the above as a graph optimization problem.
Problem 2
Describe an efficient algorithm to solve this problem.
Show the running time of your algorithm.
Rule:
Please form groups of 3 to 4 among yourselves. Send email to cs124tf as soon
as you form groups. If you have trouble finding partners, let us know
immediately. Each group should hand in just one write up, and will give us a
10 minute presentation of their solution.