2
$\begingroup$

Consider a network with $N$ nodes $1,...,n$. Every node is connected to every node via a weighted edge, where the weight represents distance.

You start your travel at a given node, say $1$, and end your travel at a given node, say $12$. Your travel has $T$ time steps. At time step $t=1$ you must visit one of nodes $\{1,7,4\}$, at time step $t=2$ you must visit one of the nodes $\{7,3,45,9\}$, and so on. In other words, at a given time step, you are given a set with at minimum $1$ and at maximum $K\leq N$ nodes. Choose the nodes for all time steps such that the cumulative distance is minimized.

Am I correct, that such problem is NP hard? Given $T$ time steps and that at most $K$ nodes are possible at each time step, the complexity would be $O(K^T)$, right?

What algorithms could be applicable or useful for such a problem? In my scenario, $T$ can be very large (up to 20,000) but $K$ is rather low (10 on average, at most 100).

(Edit) - I encountered the problem in a diary of a traveller. For example, you know that a traveller started his journey at some location. For every journey entry, besides the raw text, the writer in the title writes a date and a location name.

The problem is there often exist several different coordinates for a location name (i.e., multiple locations exists with the same name). An (I think reasonable) assumption I have come to, is that the shortest possible path (from start to finish) should approximate the travelled route quite well. I have a data set of multiple travellers with diaries like this and want to plot the routes onto a map (and hope to display a travelled route approximately in the way which in it was really travelled).

I have not yet come up with any good and general solution (besides brute-force computing the distance of every possible route, which may be impossible because there exist tons of diary entries and so many location names have multiple possible coordinates).

$\endgroup$
  • $\begingroup$ Are you allowed to visit a node more than once? What have you tried? Have you tried to prove it NP-complete by finding a reduction? Have you tried to find a polynomial-time algorithm? We expect you to make a significant effort on your own first; we discourage questions where you show us an exercise-style problem and ask us to solve it for you. What's the source or context where you encountered this problem? Where did you run into it? Can you edit the question to incorporate this information? $\endgroup$ – D.W. Sep 22 '18 at 19:03
  • $\begingroup$ Yes, you are allowed to visit a node more than once (see above, node 7 is contained in the possible sets of step 1 and step 2). Regarding the rest of what you said, I will edit the question and try to address your concerns. $\endgroup$ – user142639 Sep 22 '18 at 19:15
  • $\begingroup$ Thanks! I look forward to your revision. We do want you to revise the question so it incorporates all relevant information and so it reads well for someone who encounters it for the first time, so people don't have to read the comments to understand what you are asking. $\endgroup$ – D.W. Sep 22 '18 at 19:18
  • $\begingroup$ Thanks, that makes sense. I hope my edits may provide a better picture now of what my problem is. $\endgroup$ – user142639 Sep 22 '18 at 19:33
0
$\begingroup$

The problem can be solved efficiently: in $O(K^2 T \log (KT))$ time.

Build a graph where each vertex corresponds to a pair $(t,i)$, where $t$ is a time step and $i$ is one of the nodes that is allowed to be visited at time $t$. Add edges from $(t,i)$ to $(t+1,j)$ for every $t,i,j$, with a length that corresponds to the travel time from $i$ to $j$. Add a source node $s$ with edges from $s$ to each $(1,i)$ of length 0, and a sink node $t$ with edges from each $(T,i)$ to $t$ of length 0. Then, find the shortest path in this graph from $s$ to $T$.

The graph has $O(KT)$ vertices and $O(K^2T)$ edges, so Dijkstra's algorithm for finding shortest paths will run in $O(K^2 T \log (KT))$ time.

$\endgroup$
  • $\begingroup$ Thanks, this is very intuitive. I accepted your answer. (But cannot upvote because I am a new user). $\endgroup$ – user142639 Sep 23 '18 at 9:00

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.