News:

Thank you for your patience during the Forum downtime while we upgraded the software. Welcome back and see this thread for some new features and other changes to the forum.

Main Menu

Interesting Map Question - Visiting all the states in North America

Started by ZLoth, June 13, 2014, 08:03:26 PM

Previous topic - Next topic

ZLoth

Lets admit it. Some of us have the dream of driving to all 48 states. This bring up some interesting map problems. But, more on that in a minute...

First of all, I have an issue with some of these "All 48 State" trips. Look at this example. Sure, he drove all 48 states, but some of it feels like "I drive twenty feet into a state, THAT COUNTS!". My feeling (at the cost of additional mileage) is you really have to drive into the state to count. Why not visit the state capitals?

So, then, I found this Interesting Map Problem. Here, the author of that web page figures out the best path to visit each state once partially because Maine only borders New Hampshire. But, again, we have a slight problem. The author assumes a one-way trip. I prefer a circular trip so that eventually I get home again.

It would be interesting to expand on this concept. What if we include the states of Canada in addition to the lower 48? Hey, that would mean that we could drive to Alaska! Or, what about Mexico? What about both Canada AND Mexico? That would be a epic (and expensive) road trip.

Thoughts? How the heck do we compute the best way to have a circular route under those scenarios?
I'm an Engineer. That means I solve problems. Not problems like "What is beauty?", because that would fall within the purview of your conundrums of philosophy. I solve practical problems and call them "paychecks".


oscar

Aiming to visit all the state capitals by car (except Honolulu, you'll flood the engine) is a good way to consistently make some significant contact with each state.  It's analogous to some county-counters' insistence on visiting the county seat to include the county in their totals.  You could fudge that by going with the city hall of the central city of an officially-defined metropolitan area, but that's too easy to play games with. 

As someone pointed out in one of the latest "48 states" threads, computing the optimal route for a 48-state itinerary is not manageable with current technology (maybe if you could sneak in to "borrow" one of the NSA's supercomputers, which by itself would give you major bragging rights as well as a lengthy prison term).  But the Barry Stiefel 48-state itinerary discussed there (which quite by coincidence starts and ends near where you live) seems a good starting point for roughing out by hand an itinerary including all the lower-48 state capitals.  The key feature you'd want to copy is to snag the northern tier of states in one direction and the southern tier going the other way.

Including Alaska and Canada's provinces (and territories, minus the non-road-accessible capital of Nunavut?) not only complicates the two-tier strategy, but Canada (a) requires a jaunt to almost the eastern edge of North America, one and a half time zones east of Eastern, and (b) the zigzagging needed to snag the northern tier capitals without too much backtracking will send you back and forth across the border, which might make customs agents look at you funny (and subject you to time-wasting secondary searches) if their computer screens show your odd pattern of in-and-out border crossings.  You'll also be on ferries a lot, to cover Victoria BC, Juneau AK, and St. John's NL.
my Hot Springs and Highways pages, with links to my roads sites:
http://www.alaskaroads.com/home.html

mrsman

Definitely check the threads in General Highways that discuss 48 states.  Perhaps this thread should be closed so this discussion can stay in one place?

Duke87

This is an example of the traveling salesman problem.

The number of possible orders the cities can be visited in is (n-1)!/2n. For 48 of them, there are therefore about 2.69 x 1057 possible routes. So, solving the problem by brute force is indeed impossible with current computing power. Even if you could try a million options in a second your solution would take about 1044 years to arrive at, which is about 1034 times the current age of the universe. So even the NSA couldn't solve this problem.

That said, there are plenty of methods out there to arrive at a good (but not necessarily best) solution by eliminating obviously inefficient routes from consideration (you wouldn't go from Boston to Sacramento and then to Albany).

For anyone considering doing this: well, it's been done. This was the route they came up with:
If you always take the same road, you will never see anything new.

ZLoth

Quote from: Duke87 on June 19, 2014, 01:20:30 AM
This is an example of the traveling salesman problem.
AHA! I knew there was a proper math problem name for this issue. And, with a little digging, I found a Fastest Roundtrip Solver which would provide me with a solution to my problems.
I'm an Engineer. That means I solve problems. Not problems like "What is beauty?", because that would fall within the purview of your conundrums of philosophy. I solve practical problems and call them "paychecks".

jeffandnicole

The shortest possible route, in a realistic scenerio, will be different for everyone.  If someone lives right by an interstate highway and near another state, they will be able to clinch their state with ease.  Someone else that lives in the middle of their state will need to drive farther.  Someone who lives in, say, Miami, will need to drive 5 or 6 hours just to leave their state, adding significantly to their travel time.

It also brings up - how much driving does one have to do in a state for it to count.  Say we come up with some random time, say 30 minutes.  Does that mean someone living in Newark, DE, who can leave their state within 5 minutes and only needs another 5 minutes when returning to their state, can't count their own state?

As I mentioned in the other thread - to me for a state to count, I would need some proof that I was in that state - a picture in front of a post office with the zip code, or in front of a store exclusive to that state, or something with an address.  A motorcycle club that does this requires a gas station receipt or other receipt which shows the address, proving they were in that state (they also require the cyclists to get one or two witnesses to sign a paper stating that they were in that state).  And if I were to do it, I would definitely consider driving into Canada & Mexico just to say I hit all 3 North American Countries on one trip.  And I would want to fly and rent a car in Alaska & Hawaii just to say I drove in all 50 states on one trip.  Obviously, I'm just making up my own criteria while sitting at my computer.  Reality may say I don't have the time to do the trip all in one shot anyway.

For other people, maybe they don't count it unless they visited the state capital.  Or a specific landmark.  It's all for fun anyway...some people will question why you didn't go to a certain place, or why driving a 2 lane road for 1/2 mile in a state shouldn't count.  Most others will question the road trip in general: "You drove to all 48 states?  And WHY did you do that???"

texaskdog

getting to all 50 states is an accomplishment enough i dont care if you go in 20 feet.  I don't think flyovers count, you have to put a foot down.  I've been to 27 and the only one I grazed was Tennessee (stopping at the Memphis airport to switch planes).

wphiii

Quote from: jeffandnicole on June 19, 2014, 08:51:01 AM
or why driving a 2 lane road for 1/2 mile in a state shouldn't count. 

If anything, I'd want to undertake something like this with the goal of ONLY using 2-lane roads.

oscar

Quote from: texaskdog on June 19, 2014, 09:29:44 AM
getting to all 50 states is an accomplishment enough i dont care if you go in 20 feet.  I don't think flyovers count, you have to put a foot down.  I've been to 27 and the only one I grazed was Tennessee (stopping at the Memphis airport to switch planes).

What about a drive-through, where your wheels touch the ground but your feet don't?

I have overnight stays in all 50 states and D.C., and all Canadian provinces and territories except Nunavut.  But for counties and county equivalents, some I never set foot, crossing them at ground level by car or ferry (some of the ferries had stops in the county equivalents I passed through, but passengers were not allowed to step off the ferry then get back on -- similar issues for other people with airplane stops).

I don't try to document this all, though my back-year credit card statements should show most of the overnight stays.  There are probably many counties/equivalents where I never did a credit-card transaction, or took a photo, or can otherwise document.  So sue me.

There have been people who have not only visited every county seat, but at each one gotten some county official to sign their log books.  I'm not one of those people.
my Hot Springs and Highways pages, with links to my roads sites:
http://www.alaskaroads.com/home.html

texaskdog

Quote from: oscar on June 19, 2014, 12:13:06 PM
Quote from: texaskdog on June 19, 2014, 09:29:44 AM
getting to all 50 states is an accomplishment enough i dont care if you go in 20 feet.  I don't think flyovers count, you have to put a foot down.  I've been to 27 and the only one I grazed was Tennessee (stopping at the Memphis airport to switch planes).

What about a drive-through, where your wheels touch the ground but your feet don't?

I have overnight stays in all 50 states and D.C., and all Canadian provinces and territories except Nunavut.  But for counties and county equivalents, some I never set foot, crossing them at ground level by car or ferry (some of the ferries had stops in the county equivalents I passed through, but passengers were not allowed to step off the ferry then get back on -- similar issues for other people with airplane stops).

I don't try to document this all, though my back-year credit card statements should show most of the overnight stays.  There are probably many counties/equivalents where I never did a credit-card transaction, or took a photo, or can otherwise document.  So sue me.

There have been people who have not only visited every county seat, but at each one gotten some county official to sign their log books.  I'm not one of those people.

I would say yes.  I always put my feet down just to do it (when I first went to Kansas though I've been back many times) but flying over doesn't count.

vdeane

Quote from: Duke87 on June 19, 2014, 01:20:30 AM
This is an example of the traveling salesman problem.
The Traveling Salesman Problem + Hitler + KFC = hilarous video my Automata Theory professor showed at the end of the semester
http://www.youtube.com/watch?v=GSIodz9GWxc
Please note: All comments here represent my own personal opinion and do not reflect the official position of NYSDOT or its affiliates.

MikeTheActuary

Quote from: texaskdog on June 19, 2014, 12:23:38 PMI would say yes.  I always put my feet down just to do it (when I first went to Kansas though I've been back many times) but flying over doesn't count.

For my county-counting purposes, I count counties where there has been a physical connection between myself and the dry ground of the county in question.

So, I'll count counties where I've driven through without stopping, been on a train through without stopping, and those counties where I drove across the line and immediately turned around to come back.

For awhile, my claim of Tarrant County, Texas was because I was on a plane that taxied on that side of the DFW airport; I also claim St. Louis County, Minnesota by virtue of having been on a plane that diverted there (fuel got too low while waiting to land at MSP, so we went to DUL to get more Jet-A).

I don't, however, count counties that I've boated past or flown over.

These days, I spend more time "county hunting" on amateur radio.   For that, I seek confirmation -- written or electronic -- from the station I contacted in a particular county, before it counts.

wphiii

Quote from: texaskdog on June 19, 2014, 12:23:38 PM
Quote from: oscar on June 19, 2014, 12:13:06 PM
Quote from: texaskdog on June 19, 2014, 09:29:44 AM
getting to all 50 states is an accomplishment enough i dont care if you go in 20 feet.  I don't think flyovers count, you have to put a foot down.  I've been to 27 and the only one I grazed was Tennessee (stopping at the Memphis airport to switch planes).

What about a drive-through, where your wheels touch the ground but your feet don't?

I have overnight stays in all 50 states and D.C., and all Canadian provinces and territories except Nunavut.  But for counties and county equivalents, some I never set foot, crossing them at ground level by car or ferry (some of the ferries had stops in the county equivalents I passed through, but passengers were not allowed to step off the ferry then get back on -- similar issues for other people with airplane stops).

I don't try to document this all, though my back-year credit card statements should show most of the overnight stays.  There are probably many counties/equivalents where I never did a credit-card transaction, or took a photo, or can otherwise document.  So sue me.

There have been people who have not only visited every county seat, but at each one gotten some county official to sign their log books.  I'm not one of those people.

I would say yes.  I always put my feet down just to do it (when I first went to Kansas though I've been back many times) but flying over doesn't count.

I personally don't even count airports. I've been through McCarran, for example, at least a half-dozen times, but I don't consider myself ever having "been in" Nevada.

Alps

I will count a county that I've boated through, but not past. If there's land on both sides of me, I've been there. I use the analogy of being on a lake.

formulanone

I throw out the receipts once the expense account or personal finances are settled and the bills are paid...I do try to keep the plane tickets, but I'd rather take a photo (if not a couple hundred), which means a lot more than a scrap of ephemera.

A visited county is a county counted, to me; I'm not one to split hairs. But I'd like to think truly visiting a state means a bit more if you've visited a few of its largest cities, and perhaps taken in some of its nature, too.

Duke87

If you always take the same road, you will never see anything new.



Opinions expressed here on belong solely to the poster and do not represent or reflect the opinions or beliefs of AARoads, its creators and/or associates.