22 April 2009

Constrained tourism

Does there exist a Hamiltonian tour of the graph whose vertices are the 48 contiguous United States and whose edges connect states which border each other? More geographically, can you drive through all of the lower 48 states passing through each exactly once? (From 360.)

Here's one possible solution, although I ignored the constraint implicit in the story that provoked the question, which required a start in Michigan. Note that you have to start or end the tour in Maine since it only borders one other state.


Yves said...

Donald Knuth in one of his latest opuses of the Art of Computing Programming (volume 4, section 7.1.4, Binary Decision Diagrams) proves that there are exactly 68,656,026 hamiltonian paths starting in Maine and ending in another state, of which 2,707,075 end in California and 483,194 in New Jersey.

Binary decision diagrams (BDD) and related structures (such as Zero-Suppressed BDDs) turn out to be very efficient algorithms for this kind of combinatorial problems.

Anonymous said...

Michigan borders three states by car. A couple more if you charter a boat.

Anonymous said...

Wait, sorry, misread your statement. It's way too early to be awake, let alone teach.

Anonymous said...

This was probably more interesting pre-World War II and even more interesting pre-Depression; before all the interstate highway building.

Anonymous said...

There should be a bunch of them doable on Interstates only... turns out there are only a few borders not crossed by at least one interstate.

Your sample path includes just one in the east (Arkansas-Mississippi) but some trickier stuff out west.