I am working on my research problem that essentially boils down to the following question. Consider an $N \times N$ matrix. There is a man at given a starting point $(x,y)$. In each unit of time, the man can move east, west, north or south of the point (no diagonal moves). Given an end point $(p,q)$ and $K$, the goal is to reach $(p,q)$ in at most $K$ steps such that the path taken maximizes the number of blocks 'visited' by the man. There is no constraint on the structure of the path taken (it can contain cycles or revisit the same block again). A block is said to be 'visited' if the man has never been to the said block before and he then goes to the block. Revisiting a 'visited' block does not increase the count of total blocks 'visited'.

Another variant of the problem is when instead of one man, there are $\ell$ men, each of whom want to reach $(p,q)$ in at most $K$ steps while maximizing the total number of blocks visited by all of them.

I thought that a simple DP algorithm would suffice to solve it but now I am suspecting that this problem is NP-hard but can't show that either. Any leads appreciated!

  • 1
    $\begingroup$ Hint: use the NP-hardness of path TSP on grid graphs. See theorem 2.1 of epubs.siam.org/doi/abs/10.1137/0211056 . $\endgroup$ – Yonatan N May 5 at 1:59
  • $\begingroup$ @YonatanN Thanks!! $\endgroup$ – karmanaut May 5 at 2:13
  • 1
    $\begingroup$ Are you considering the $N\times N$ matrix to be an $N\times N$ two-dimensional grid graph with all $N^2$ vertices and all $2N^2-O(N)$ edges present (i.e., each internal node has four edges)? And by "block" do you mean a vertex in this graph? If so, isn't there always a path that visits $\min(K, N\times N)$ blocks (which is optimal)? If not, can you give an example that illustrates why the problem is hard? $\endgroup$ – Neal Young May 7 at 20:22

Your Answer

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

Browse other questions tagged or ask your own question.