2
$\begingroup$

Given a $n*m$ grid, some $1*1$ squares are blocked(can't be entered) and some are unblocked(can be entered).

What is the algorithm which prints the shortest path, such that the path covers all unblocked $1*1$ squares in a $n*m $ grid ?

The starting point is given to be :$(startx,starty)$.

A $1*1$ square can be visited more than once, but all $1*1$ squares should be visited at least once and the length of path has to be minimized.

Path can end any where, when there are no more unvisited $1*1$ squares.

I have thought of dfs, but that doesn't seem to minimize the length of the path.

$\endgroup$
  • $\begingroup$ Related: cs.stackexchange.com/q/68580/755. I think the answers there imply that your problem is NP-hard (you can tell whether the corresponding graph has a Hamiltonian path by checking whether the solution to your problem avoids revisiting any square more than once; but checking for a Hamiltonian path is NP-hard). So, there's not much hope for a polynomial-time algorithm to find the shortest such path. However, you might be able to hope for heuristics or approximation algorithms. $\endgroup$ – D.W. Jan 20 '17 at 11:33
  • $\begingroup$ @D.W. But in my question, squares can be visited more than once $\endgroup$ – nequit Jan 21 '17 at 6:48
  • $\begingroup$ I know. But if there's a Hamiltonian path, then the solution to your problem won't visit any square more than once; if there isn't a Hamiltonian path, the solution to your problem will visit some square more than once. Consequently, if we could solve your problem, we could tell whether or not a Hamiltonian path exists (by solving your problem and then checking whether the solution visits any square more than once or not) -- which is known to be hard. $\endgroup$ – D.W. Jan 21 '17 at 16:13
  • $\begingroup$ @D.W. Just for the sake of curiosity! nequit is asking for the shortest path in a specific case which is a (planar) rectangular grid graph. While I do not know about any specific applications of the Hamiltonian Path Problem to this case, other NP-hard problems (such as the Longest Path Problem, see "A linear-time algorithm for the longest path problem in rectangular grid graphs" by Keshavarz-Kohjerdi et al., Discrete Applied Mathematics, 160 (2012), pp. 210--217) are known to be solvable in polynomial time when restricted to this specific case. $\endgroup$ – Carlos Linares López Jan 23 '17 at 0:28

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.