In TSP you can only visit each node once, right? You can visit each road (segment of road, really) as many times as you like (there is likely no way to do it without visiting some more than once).
The costs in TSP are associated with the paths. In the driving problem they’re associated with the road segments, so I don’t see how it works if the intersections are the paths.
As I remember the TSP. It is the shortest path visiting each city at least once. I think you can map the length of roads onto new connections between each node.
I don’t want to hijack this thread more than I have already. If people are interested in this topic open let me know and we can open a new thread.
I’m going away for the weekend (in a few minutes, so this has got to be quick), so I’ll be computerless today and tomorrow, but I’d love to hear more of your travels. I had no idea you are an intrepid explorer. Maybe I’ll start a tell us about interesting journeys thread.
At the other end of the US-Canadian border is a complementary situation. Campobello Island, New Brunswick can be reached by a bridge from Lubec ME, but there’s no bridge from the New Brunswick mainland. A Canadian wanting to drive there (without taking a ferry) has to go through the US.
As far as I know, there are none. If there are any, they are quite small and located in remote mountainous areas, such as the Rockies, the Sierras, or the Cascades.
BTW, Churchill MB is also only connected by railway and not by road.
Well known trivium that I’m surprised no one has brought up: Juneau AK is the largest city on the North American mainland not connected to the highway grid.
TSP means exactly once for each node. Crossing each edge once is an Eulerian path/tour and is very easy to test for. (The “hardest” part is testing if the graph is connected. Shades of the OP.) There are Wikipedia articles on those of course.
But a Eulerian path crosses each edge exactly once, right? So it doesn’t apply either. And is it easy to find the shortest such path, or just to determine the existence of one?
Every path that crosses each edge exactly once will be, by definition, exactly as long as every other such path. So there is no “shortest” such path. And yes, the way to determine the existence of an Euler path is easy.
In addition to both Nome and Juneau in Alaska – both of which have a road system connecting them to outlying settlements and isolated dwellings, but which are not connected by road to the rest of the American-Canadian-Mexican road system – there are no doubt small mountainous areas with roads not linked to the main grid within the “Lower 48”). The one I’m aware of is here. At the scale the map is at, you will see roads as pale brownish lines on either side of the southwest part of Stillwater Reservoir. Zoom in (+) and move east and west of the water (>) and (<) to get clearer detail. The Number Four-Big Moose Road west of the reservoir is an integral part of the North American grid, connecting Lowville and Old Forge, New York by a dirt road that is (barely) drivable by normal two-wheel-drive vehicles; Barb and I traveled it once. But east of the reservoir’s southwest embayment, running along the southern shore of the eastern arm of the reservoir, is a road leading over to “Little Rapids” and “Beaver River”, the latter a hamlet. Its sole connection to the outside world is the Adirondack Railway track running through it; cars are brought in (rarely) via rail or by boat across the reservoir. And that road along the south shore east of the embayment has no road connection to anywhere else in the U.S. As I understand it, nobody registers their cars in there, since the only roads are all privately owned. I haven’t been there (to Beaver River) myself, but it was the subject of a story in a local newspaper years back.
They’re paved with bricks. In Louisiana, we have interstate highways with rougher surfaces than those brick roads, and they still consider them to be “paved”. :smack:
I’d be happy to.
OK, but the road thing doesn’t require crossing each edge exactly once. In fact I can assure you, based on the streets down the block from me, that there is no Eulerian path (even among the main set of interconnected roads). Finding the shortest path that crosses each edge at least once is a different problem, and might be much harder, especially when the edges are weighted.