8
$\begingroup$

A particular programming problem I came across recently reduces to finding hamiltonian paths in a rectangular grid that would look something like,

A  0  0  0

0  0  0  0

0  0  C  D

What are some effective heuristics that could be applied to find them - and particularly, techniques to trim/discard paths along the way?

Edit: Just to clarify, the edges are formed when elements are connected horizontally and vertically, but not diagonally. The problem also states that any element that is marked 0 can be used to form a path, but non 0 elements are "obstacles" that need to be avoided.

A-0-0-0
      |
0-0-0-0
|
0-0-C D

could be one path, for instance. Another may be,

A 0-0-0
| |   |
0 0 0-0
| | |
0-0 C D
$\endgroup$
  • 2
    $\begingroup$ Which are the edges in your example? $\endgroup$ – Alexandru Aug 16 '10 at 20:17
  • 1
    $\begingroup$ Did this per chance come from Quora's jobs challenge page? quora.com/challenges $\endgroup$ – majelbstoat Jan 10 '11 at 10:20
3
$\begingroup$

I don't see an easy way of counting without enumerating. You can easily visit all hamiltonian paths with an exaustive depth-first search with backtracking. You can actually cheat a bit, and realize that, if N is the number of hamiltonian paths that start by going to the right, the total number of hamiltonian paths is 2N (due to the symmetry if the grid). This does not extend all the way (for some vertices not all paths will lead to the same number of cycles, but you can upper bound the number of hamiltonian paths easily with a similar argument (with the bonus that you can solve parts of it exactly to improve your bound with symmetry arguments). This is the strategy I'd choose.

But if you don't want this, some generic heuristics:

  • You can also easily upper bound the number of hamiltonian paths as |E| choose |V|-1 (where |E| is the number of edges and |V| the number of vertices in the graph), which can be a lot better for a sparse graph than |V|! (the naive bound that assumes that the graph is complete).

  • An easy way to improve this bound is by trimming known-bad combinations, by not considering twice edges from the same vertex. So you'd get something like prod_v(deg_v-1) (which should still upper bound the number of hamiltonian paths, since you're now counting cycles more than once, I think).

$\endgroup$
  • 1
    $\begingroup$ Can this not be improved to a kind of dynamic programming with memoization? $\endgroup$ – András Salamon Aug 17 '10 at 2:17

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.