New answers tagged hamiltonian-path
1
Let $P$ be an arbitrary simple path in the graph. If $P$ appears in a Hamiltonian cycle of the graph, you can remove all the vertices of $p$ except the first and the last vertex, connect these two vertices with an edge and the resulting graph must be Hamiltonian.
Keeping this in mind, we can build the Hamiltonian cycle step by step starting with path of ...
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
