New answers tagged matrices
2
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 ...
1
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 ...
4
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 ...
Top 50 recent answers are included
