patternMinor
Maximize number of museums visited in a day
Viewed 0 times
numbervisitedmaximizemuseumsday
Problem
Given a list of museums, their opening hours and time needed to visit each, make a schedule such that a tourist visits maximal number of museums in a given day.
Suppose that no time is needed in order to travel from one museum to another. Tourist cannot, of course, be in two different museums at the same time.
For example, if given:
One itinerary maximizing number of museums visited would be:
Also, this itinerary would also be valid:
There is no preference over different itineraries having the same number of museums!
Things I have tried:
Greedy algorithm
For the sake of simplicity, let us consider the following table:
Based on Interval scheduling, I tried first sorting this list by earliest museum visit finishing times (i.e. by time museum opens + duration of visit sum):
```
+-----------+-------+--------+-------------------+
| Museum | O
Suppose that no time is needed in order to travel from one museum to another. Tourist cannot, of course, be in two different museums at the same time.
For example, if given:
+-------------+-------+--------+-------------------+
| Museum | Opens | Closes | Duration of visit |
+-------------+-------+--------+-------------------+
| Louvre | 08:00 | 16:00 | 01:00 |
| Hermitage | 08:00 | 15:00 | 01:00 |
| Uffizi | 09:00 | 18:00 | 04:40 |
| Rijksmuseum | 10:00 | 21:00 | 02:20 |
| Vatican | 08:00 | 15:00 | 05:30 |
+-------------+-------+--------+-------------------+One itinerary maximizing number of museums visited would be:
Vatican 08:00 - 13:30
Hermitage 13:30 - 14:30
Louvre 14:30 - 15:30
Rijksmuseum 15:30 - 17:50
---> Total No. of museums visited: 4Also, this itinerary would also be valid:
Uffizi 09:00 - 13:40
Hermitage 13:40 - 14:40
Louvre 14:40 - 15:40
Rijksmuseum 15:40 - 17:40
---> Total No. of museums visited: 4There is no preference over different itineraries having the same number of museums!
Things I have tried:
Greedy algorithm
For the sake of simplicity, let us consider the following table:
+-----------+-------+--------+-------------------+
| Museum | Opens | Closes | Duration of visit |
+-----------+-------+--------+-------------------+
| Louvre | 08:00 | 10:00 | 02:00 |
| Hermitage | 08:00 | 11:00 | 01:00 |
| Uffizi | 08:00 | 11:00 | 03:00 |
+-----------+-------+--------+-------------------+Based on Interval scheduling, I tried first sorting this list by earliest museum visit finishing times (i.e. by time museum opens + duration of visit sum):
```
+-----------+-------+--------+-------------------+
| Museum | O
Solution
The problem is strongly $NP$-complete by reduction from 3-Partition.
Given a set of $3n$ integers with total sum $3M$, we want to determine whether they can be partitioned into $n$ triples, each having sum $M$. Note that we can assume that no four integers have sum $\leq M$.
Suppose a day is $3M+n-1$ units of time long. We want to visit $n-1$ museums $m_1,\ldots,m_{n-1}$ for $1$ unit of time each, and the $i^\textrm{th}$ museum is open from time unit $i\times(M+1)-1$ to time unit $i\times(M+1)$. I.e., there are $n$ museums that can only be visited at one very specific time of day, and they partition the day into $n$ slots of length $M$ each.
For each integer in the 3-Partition instance we now create a museum to visit that can be visited any time during the day, and takes a number of time units equal to the original integer.
Clearly a solutions visiting all museums in a single day corresponds to a solution for the $3$-Partition instance and vice-versa.
This implies that it is unlikely that an algorithm significantly better than brute-force exists. One possible approach would be to use Held-Karp style dynamic programming, similar to solving TSP. One would, for all subsets $S$ of museums and any time of day $T$, compute the maximum number of museums from $S$ that can be visited before time $T$ (i.e., the last visit must be completed before time $T$). This can be evaluated recursively by picking one museum to visit last, and then removing that museum from $S$ and decreasing $T$ and solving the resulting subproblem. This results in an algorithm with running time exponential in the number of museums.
Given a set of $3n$ integers with total sum $3M$, we want to determine whether they can be partitioned into $n$ triples, each having sum $M$. Note that we can assume that no four integers have sum $\leq M$.
Suppose a day is $3M+n-1$ units of time long. We want to visit $n-1$ museums $m_1,\ldots,m_{n-1}$ for $1$ unit of time each, and the $i^\textrm{th}$ museum is open from time unit $i\times(M+1)-1$ to time unit $i\times(M+1)$. I.e., there are $n$ museums that can only be visited at one very specific time of day, and they partition the day into $n$ slots of length $M$ each.
For each integer in the 3-Partition instance we now create a museum to visit that can be visited any time during the day, and takes a number of time units equal to the original integer.
Clearly a solutions visiting all museums in a single day corresponds to a solution for the $3$-Partition instance and vice-versa.
This implies that it is unlikely that an algorithm significantly better than brute-force exists. One possible approach would be to use Held-Karp style dynamic programming, similar to solving TSP. One would, for all subsets $S$ of museums and any time of day $T$, compute the maximum number of museums from $S$ that can be visited before time $T$ (i.e., the last visit must be completed before time $T$). This can be evaluated recursively by picking one museum to visit last, and then removing that museum from $S$ and decreasing $T$ and solving the resulting subproblem. This results in an algorithm with running time exponential in the number of museums.
Context
StackExchange Computer Science Q#109732, answer score: 3
Revisions (0)
No revisions yet.