[OC] A person visiting every county seat in the U.S. in a very naive way.

  1. Does this include city halls in Virginia? Cities are outside of counties there so you would either skip them or have to include them as if they were counties.

  2. This is the Traveling Salesman Problem. The only way to know for sure if you have the shortest solution is to try every possibility, and that becomes computationally impossible when you have more than a certain number of points.

  3. That was fascinating. I wonder whether different starting counties would converge to a similar path or whether you could get a different order entirely.

  4. I didn't really try with other starting counties but I did consider doing that. I'm guessing you'd end up with fairly similar paths. I'm making one now that uses an optimized round-trip (closed-loop) path. That should be independent of starting county. It'll probably be done tomorrow.

  5. Wouldn't a drunkard's walk choose the next destination at random instead of choosing the closest not yet visited destination (as was done here)?

  6. The optimal path one algorithm got was 100,137 miles round trip. There's a link to what the path looks like in another comment. It looks much like what you'd think.

  7. I'm very aware but I figured I'd not confuse the other 90% of the people with "State Administrative Subdivision".

  8. If no county seat, I used the largest city. Some counties in ND (I think) share a county seat with a neighboring county.

  9. A worst solution would be to visit the furthest non visited county from the current one, i wonder how long that would be

  10. Then shouldn't this be the shortest path through all county seats? Since every segment is the shortest path between adjacent seats?

  11. No... this is FAR from optimal. I'm making an optimal one now since I found a nice algorithm for solving (approximately) the Traveling Salesman Problem with 3000 destinations.

  12. FYI, the optimization gave a total distance of 100,137 miles, about 21k miles less than the naive approach here.

  13. This is based on the idea of a greedy algorithm like Dijkstra's. It makes the most optimal LOCAL choice. But systemically that may not be the best over-all choice for an optimal route. It won't give you the best answer, but it'll generally give you a decent answer.

  14. LA has the equivalent to counties. If there was a way to drive to HI, I'd have included it. Same with AK... there are some "counties" there that don't seem accessible by car.

  15. You should run this starting in each location and then sort them by distance traveled. I'd be really curious to see the shortest and longest.

  16. Doing that for the geographic distance would be possible, but I've been using the travel distance here. Getting the turn-by-turn directions between 3000 locations takes some time. Lol.

Leave a Reply

Your email address will not be published. Required fields are marked *

Author: admin