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
Related Tags
matrices × 188algorithms × 89
linear-algebra × 36
graphs × 15
optimization × 15
complexity-theory × 14
algorithm-analysis × 12
dynamic-programming × 12
parallel-computing × 12
time-complexity × 11
numerical-algorithms × 11
runtime-analysis × 10
combinatorics × 10
multiplication × 8
data-structures × 7
machine-learning × 7
reference-request × 7
arrays × 6
permutations × 6
discrete-mathematics × 5
sparse-matrices × 5
image-processing × 4
lower-bounds × 4
search-algorithms × 3
shortest-path × 3