|
|
back to boardHints & ideas Posted by decay 1 May 2019 18:36 A problem asks to find longest path in Hyper cube graph that visits each vertex at most once. If two numbers have odd amount of bits in common then there is always a Hamiltonian path (length 2^n). Parity of common bits is checked using xor. If parity is even then one can build a path of length 2^n - 1. This path can be built by successively building Hamiltonian paths on lower dimension cube. That is, build a path of length 2^(n - 1) and recurse to find path of length 2^(n - 1) - 1. So, the solution is built around knowing how to construct Hamiltonian path. There is, in fact, a very simple approach. My algorithm works in O(2^n) and doesn't use extra memory. |
|
|