Collecting the most presents possible with a limited distance that you can travel.

Question

The following map shows towns (in purple) and the number of presents at each town (also in purple). The towns are connecting by roads (in orange) and the length of those roads is shown in orange (the units let’s say are miles). If you can only travel on those roads in a car which can travel at most $70$ miles, what is the maximum number of presents you can collect (assuming you can go back along roads you have already been on, can start at any town, but once the presents have been collected from a town, you cannot get more).

I am not necessarily interested in the actual answer, but I am wondering if there is a method of calculating the answer. I have just made up the numbers for this question, but am wondering if there is a general method (after asking a few people, they seem to say that this problem is made difficult by the fact that you can start and end anywhere).

Many thanks.

Answer 1

The fact that you can start anywhere really only makes the problem $11$ times harder to solve, which is relatively minor. The real hassle is that you can retrace your steps. But we've got this.

Let $T$ be the set of towns. Let $p_x$ represent the number of presents at each town $x$ and $d_{xy}=d_{yx}$ represent the length of the road between towns $x$ and $y$ (with $d_{xy}=\infty$ if there is no direct road between $x$ and $y$).

Let us refer to a $\underline{\text{state}}$ of the solution as a list $(w,x,y,Z)$, where $w\in\mathbb N$ represents the number of miles left in your trip, $x\in T$ represents the town you are at, $y\in\mathbb N$ represents the number of presents you have, and $Z\subset T$ represents the list of towns you have visited in order. The initial states that we start with (assuming you can automatically pick up the presents from your initial town) will be $$\{(70, x,p_x,(x))\mid x\in T\} $$

Let $\mathcal U$ represent the set of all unanalyzed states, which initially consists of the initial states. Given $(w,x,y,Z)\in\mathcal U$, we will analyze it as follows. For each $t\in T$ such that $d_{xt}\leq w$, add $$\begin{cases} (w-d_{xt},t,y,Z+t), & \text{if $t\in Z$} \\ (w-d_{xt},t,y+p_t,Z+t), & \text{otherwise} \end{cases}$$ to $\mathcal U$ (where $Z+t$ represents appending $t$ to the end of list $Z$). Once you've fully analyzed a state, remove it from $\mathcal U$. When $\mathcal U$ is empty, the largest value of $y$ among all analyzed states is the greatest number of presents achievable and the $Z$ for that state is the list of towns you visited to get that total.

This algorithm has to end eventually, since every new state analyzed will decrease the number of miles you are still allowed to travel. There are any number of ways to speed up the algorithm, since the optimal trip will have little if any backtracking and this algorithm will happily count up a whole lot of trips that revisit towns over and over. But this algorithm shouldn't be out of line for a modern computer.

Answer 2

To have an easy reference, let's call your problem the present-hunt-problem.

It is indeed correct, that the problem you posed is difficult. In fact, it is $\mathcal{NP}$-hard, which means as much as that there (most likely) doesn't exist any algorithm that scales well with problem size.

For the proof that this problem is $\mathcal{NP}$-hard, we'll reduce the Knapsack Problem to your problem (i.e. we show that we can take any instance of the Knapsack problem, and turn it in polynomial time into an instance of your problem):

Let's say $M=\{m_1,...,m_n\}$ is the set of all our items,
$v\,:M\to\mathbb{R}$ the function that maps each item to its value, and
$w:M\to\mathbb{R}$ the function that maps each item to its weight.

We're looking for the optimal subset $S\subseteq M$ so that $\sum_{x\in S} v(s)$ is maximized and our subset fullfills the constraint $\sum_{x\in S} w(x)\le b$ (where $b$ is the maximum weight that is allowed).

This is the so called Knapsack problem. To this problem, we create the following graph:

More precisely, we let $G= \{G,m_1,...,m_n, S_1,S_2\}$ be the nodes of our graph, give each node $m_i$ the value $v(m_i)$ as well as an edge $(m_i,C)$ with weight $\frac{w(m_i)}{2}$.

The node $G$ gets the value 0, i.e. $v(G)= 0$.

Finally, we give the two nodes $S_1,S_2$ each a value that is "high enough" (to be precise: At least higher than the sum $\sum_{i=1}^n v(m_i)$) and add the edges $(S_1,C), (S_2,C)$ with weight $d$, which as well has to be "high enough" (at least so that $2d+b<3d$).

On this graph we then run the present-hunt-algorithm for our initial knapsack problem in which we replace $b$ by $b+2d$.
The idea behind the graph is that we fix a start and end point (namely $S_1$ and $S_2$) by making them too good to not be selected, but too expensive to not be the start/end point (precisely the start- and end point only need to walk the connecting edge once; So we only need to set the cost of the edge too high to walk it thrice)

For every other node $p$ that our tour selects, the tour contains the path $C\to p\to C$, i.e. to visit $p$, we'll need fuel equal to $w(p)$.

So, we've started with an instance of the Knapsack problem, and turned it into an instance of the present-hunt-problem. The instance of present-hunt will us in return always return the optimal solution to the initial Knapsack problem (if we strip $S_1,S_2$ from the trip) [technically, one needs to formally proof this].

All in all this means, that if we could efficiently solve the present-hunt-problem, we could also efficiently solve the Knapsack-Problem, and therefore present-hunt is is $\mathcal{NP}$-hard.
(And therefore, there (probably) doesn't exist an efficient algorithm for all instances of the present-hunt-problem)

Answer 3

You can introduce a dummy node with zero-cost edges to all other nodes, and then this is the prize-collecting traveling salesman problem.