3
$\begingroup$

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:

+-------------+-------+--------+-------------------+
|   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: 4

Also, 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: 4

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:

+-----------+-------+--------+-------------------+
|  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   | Opens | Closes | Duration of visit |
+-----------+-------+--------+-------------------+
| Hermitage | 08:00 | 11:00  | 01:00             |
| Louvre    | 08:00 | 10:00  | 02:00             |
| Uffizi    | 08:00 | 11:00  | 03:00             |
+-----------+-------+--------+-------------------+

and then "greedily selecting" the next visit, which gives only:

Hermitage 08:00 - 09:00

while the optimal itinerary would be:

Louvre 08:00 - 10:00
Hermitage 10:00 - 11:00

I have also tried sorting the list using different combinations of criteria (opening/closing time, shortest/longest time needed to visit, etc.) to no avail, thus concluding that the greedy algorithm approach is probably not suitable.


Dynamic programming

Given that we have to "place the maximum number of visits" in "a container of fixed length", i.e. a 24-hour day, it seemed to me that this problem is a variation of the Knapsack problem.

I have tried solving for an optimal itinerary for some $k$ museum visits, where $0\leq k\leq$ no. of museums, but failed to see the correspondence of $k+1$-th solution to $k$-th solution.

[EDIT: Added examples of what might not work] Suppose that we go hour-by-hour from the latest closing time up to the earliest opening time. (Here, the choice of time step as one hour is for the sake of simplicity and would work only if times where given as integer number of hours, as in the following example.) Considering the following table:

+-----------+-------+--------+-------------------+
|  Museum   | Opens | Closes | Duration of visit |
+-----------+-------+--------+-------------------+
| Hermitage | 08:00 | 11:00  | 01:00             |
| Louvre    | 09:00 | 11:00  | 02:00             |
+-----------+-------+--------+-------------------+

At 10:00 o'clock, the tourist can visit:

Hermitage 10:00 - 11:00

At 09:00 o'clock:

Hermitage 10:00 - 11:00

At 08:00 o'clock, still the same:

Hermitage 10:00 - 11:00

i.e. Louvre never appeared because Hermitage occupied its 'time slot' even though the tourist could have gone to Hermitage at 08:00, like so:

Hermitage 08:00 - 09:00
Louvre 09:00 - 11:00

Is this problem, then, solvable only by backtracking or similarly brute-force approach? If so, how?

$\endgroup$
  • $\begingroup$ It is not equivalent to the knapsack problem. But I believe it could be formulated and solved as either a dynamic program or a linear/integer programming problem. Are you open to either of those approaches? $\endgroup$ – LarrySnyder610 May 23 at 0:47
  • $\begingroup$ I am open to any approach, really, as long as it is reasonably efficient. I am actually doing this for learning purposes, so I am in fact most interested in comparing/testing different solutions. $\endgroup$ – Stefan Borović May 23 at 0:54
  • $\begingroup$ I would try formulating it as an LP. Use a continuous variable to represent arrival and/or departure times at each museum, and a binary variable to indicate whether a given museum has been visited. Alternately, if the times are all reasonably discrete (e.g., multiples of 10 or 30 minutes) you could make everything binary and do something like: $x_{it} = 1$ if we are at museum $i$ at time $t$, 0 otherwise. If you try this approach and get stuck, feel free to update your question. $\endgroup$ – LarrySnyder610 May 23 at 1:01
  • $\begingroup$ :offtopic: Is this question more suitable for StackOverflow or CS.StackExchange? I chose CS because I am seeking 'pseudo-code type' solutions w/ complexity analysis, rather than language-specific implementation. $\endgroup$ – Stefan Borović May 23 at 1:10
  • 1
    $\begingroup$ @StefanBorović algorithmic questions are very good fit here, at current form it is probably the best choice. Welcome to Computer Science! $\endgroup$ – Evil May 23 at 1:22
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Well, the original question does not imply visiting all museums in a single day! For example, if given a list of >100 museums, an optimal itinerary could only include 10 museums, if there are no 11 museums that could be visited in a day. Also, working hours are not taken into consideration as a constraint, nor are the durations of visits of the same length. $\endgroup$ – Stefan Borović May 23 at 10:14
  • $\begingroup$ Finding an itinerary visiting the maximum number of museums implies visiting all museums if this is possible. $\endgroup$ – Tom van der Zanden May 23 at 10:21
  • $\begingroup$ Well, I agree that one could iterate from 0 to n, applying this algorithm in order to ''make the itinerary". Still, even if the question was: "Can some k museums be visited in a day and how?" I do not understand how are opening hours taken into account, for e.g. I am not sure if I am missing something, so could you please elaborate a bit, maybe give an example? $\endgroup$ – Stefan Borović May 23 at 10:28
  • $\begingroup$ What I am giving is not an algorithm. What I am giving is a proof, showing NP-completeness. This implies that an efficient algorithm (better than brute-force or backtracking) is unlikely to exist. $\endgroup$ – Tom van der Zanden May 23 at 11:04
1
$\begingroup$

I agree with you that dynamic programming is the best choice. However, I wouldn't recurse over the number of museums, but over the time of day.

In particular: at 11:00pm, what plan gives you the greatest number of museums? Your only option is to go home and see zero.

Now, at 10:00pm, what plan gives you the greatest number of museums? There are only two options here: visit the Hermitage for one hour (so your score is 1 + max_score(11:00pm)) or wait for one hour (so your score is 0 + max_score(11:00pm)).

Continue in this manner, with a nice dynamic-programming memoization table to keep the time complexity low, until you hit the start of the day (the earliest opening time). And voilà!

EDIT: If you need finer granularity than an hour, you can make your times more precise: in your first example, for instance, ten-minute increments will work nicely.

$\endgroup$
  • 1
    $\begingroup$ @Evil I'm guessing the problem doesn't actually involve one-minute intervals, since all the examples OP gave involve intervals no smaller than ten minutes. But I should note that in the answer. $\endgroup$ – Draconis May 23 at 1:56
  • $\begingroup$ @Draconis I have provided what I consider to be an example of why this wouldn't work in my original question. I have edited my question instead of commenting your answer because the counterexample description wouldn't fit in the comment, but also because I think it makes the question more complete. Also, did I correctly interpret your suggestion? $\endgroup$ – Stefan Borović May 23 at 2:06
  • 1
    $\begingroup$ Doesn't the state space need to keep track of which museums have already been visited? If so, it grows exponentially; though maybe that's OK if the model is not meant to solve instances with more than a handful of museums. $\endgroup$ – LarrySnyder610 May 23 at 2:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.