0

Sorry if this has been asked before but I wonder how to detect minimum number of nodes for given Hamiltonian Path for fixed endpoints. Lets say below is a Hamiltonian path from $1$ to $16$;

Full Path

And if we keep endpoints ($1$ is start and 16 is end) and say one can only move from $2$ to $3$ we still end up with the same path. So my question is how to detect those unnecessary nodes to remove. Is there any source, subject or type of algorithm that I can use?

Partial Path

P.S. I want to solve this question without generating all other possible Hamiltonian Paths for $4\times 4$ grid. Thanks in advance.

Joseph
  • 23
  • 3

2 Answers2

1

A Hamiltonian path, by definition, must contain all nodes.

And if we keep endpoints (1 is start and 16 is end) and say one can only move from 8 to 9 we still end up with the same path. So my question is how to detect those unnecessary nodes to remove.

This is not too clear, but if you are asking for the shortest path from grid location $g_{ij}$ (row $i$ column $j$), then you can use a shortest path algorithm. If the shortest path (say from 1 to 16) must contain the edge 8-9, you can merge nodes 8 and 9 into a single node (that inherents its edges from the union of 8's and 9's edges) before running the shortest path algorithm. If what you have is a grid and not a graph, you can transform the grid into a graph, which is straight forward: each $g_{ij}$ is a node, and there is a directed edge from $g_{ij}$ to:

$g_{mj}$ where $m=i+1$ (the square above)
$g_{pj}$ where $p=i-1$ (the square below)
$g_{in}$ where $n=j-1$ (the square to the left)
$g_{ik}$ where $k=j+1$ (the square to the right)

Ensure that $k,m,p,n<=$ your grid's size otherwise don't create that edge.

Ali Atiia
  • 11
0

Sorry I've realized that my second image (partial path) was wrong since it has more than one solution actually. I've edited the image. To be more clear (refer to second image);

If I say one should start from node 1, end up at node 16, can only move from node 2 to node 3 and should visit all nodes in 4x4 grid,

this would result in the Hamiltonian Path given in picture 1 (full path).

How can I find node 2 and node 3 (minimum nodes) that would represent the given Hamiltonian Path with fixed start and end points. (without generating and comparing with all other possible paths). Thanks.

Joseph
  • 23
  • 3