3
$\begingroup$

I have a matrix that consists of 0, 1, 2.

  • 0 - dot.
  • 1 - block.
  • 2 - start dot (initial position in the path).

I have to create a path from the start dot, that

  1. connects all the dots in the matrix and
  2. visits each dot ONE time
  3. doesn't visit blocks

In other words, create a Hamiltonian path in a matrix. A pic below exhaustively shows what I want.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ For small grids (less than 10x10) a backtrack algorithm with some pruning heuristics will be effective. See chapter 5.4 on the book cses.fi/book/book.pdf for some examples of pruning heuristics in this problem. $\endgroup$ – Laakeri Nov 22 '19 at 11:10
4
$\begingroup$

The problem of finding a Hamiltonian path in a partial grid graph (that is, an arbitrary subgraph of a grid, not necessarily even induced) remains NP-complete [1]. Thus, you are likely out of luck for a polynomial-time approach.

A good choice for a heuristic might depend on your instance size and further structure. However, in general, you could try say a genetic algorithm, ant colony optimization, or some more problem specific heuristic.


[1] Papadimitriou, Christos H., and Umesh V. Vazirani. "On two geometric problems related to the travelling salesman problem." Journal of Algorithms 5.2 (1984): 231-246.

$\endgroup$
  • $\begingroup$ Couldn't you help with such type of algorithm? I'm very bad in algorithms and it will take me weeks for understanding and writing algorithm :( $\endgroup$ – Alexander Nov 22 '19 at 12:17
  • 1
    $\begingroup$ @Alexander Sorry, I don't think there's a shortcut to happiness here. Maybe you can find a package or some implementation out there that's helpful for your programming language. $\endgroup$ – Juho Nov 22 '19 at 12:37
  • $\begingroup$ programming language is not important, I need some general idea, a little piece of pseudocode $\endgroup$ – Alexander Nov 22 '19 at 18:12
2
$\begingroup$

Actually, grid graphs are a very specific class of input problems, and a good number of algorithms are known that can solve problems which remain hard in other instances, i.e., non-grid graphs.

Even if it is not directly related to your question, I could not avoid citing the following paper:

F. Keshavarz-Kohjerdi, A. Bagheri, A. Asgharian-Sardroud. A linear time algorithm for the longest path problem in rectangular grid graphs. Discrete Applied Mathematics, 2012 160(3) 210-217.

For your specific problem, the best (up to my knowledge) is a polynomial-time algorithm in solid grid-graphs:

W. Lenhart, C. Umans, Hamiltonian cycles in solid grid graphs, in: Proc. 38th Annual Symposium on Foundations of Computer Science, FOCS’97, 1997, pp. 496–505.

Hope this helps,

$\endgroup$
  • $\begingroup$ as I mentioned above I'm very bad in algorithms. Couldn't you please help me with this one? I need just a general idea of the algorithm or a piece of pseudocode $\endgroup$ – Alexander Nov 23 '19 at 9:00
  • $\begingroup$ Of all answers, I think that Ashkan R.Nejad's reply might be the best one if you want/need a quick implementation. I would then go for the idea of using a state space search formalism. Would you like to see a pseudocode of such approach? What is the size of your instances?? $\endgroup$ – Carlos Linares López Nov 23 '19 at 11:21
1
$\begingroup$

One simple way is to face this problem like a state-space search. Assume that going in each of 4 directions on a node that has not been visited is one action. Make a function that is responsible for producing all the next possible states given the current state. It produces a list of all next actions (at most 4 states). As you may know, we call this function the successor function. Then run a BFS\DFS search using this function. Run till all nodes on your matrice are visited.

Another better way is to face this problem like a traveling salesman problem [1]. Although it tries to find the path with the lowest cost, it is a good choice. There exists a dynamic programming algorithm for solving this problem. Tushar Roy has given a good explanation of this algorithm in his youtube channel (link).

I hope this can help you. Good luck!

$\endgroup$
  • $\begingroup$ if you run BFS/DFS until all nodes are visited, you will generally obtain a tree which is not eligibe as "path". And I am pretty sure there is more adapted algorithm than TSP ones... Using geometric features of the 2D grid for instance. $\endgroup$ – Optidad Nov 22 '19 at 13:49
  • $\begingroup$ @Vince, Yes and it needs an extra condition in addition to visiting all the nodes, which is ending at the goal node. BTW, I agree with you about geometric algos. I thought maybe the question is asked for an old-fashion simple state-search problem in classic AI. $\endgroup$ – Ashkan R. Nejad Nov 23 '19 at 6:41

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.