[math-fun] Shortest Euler path (driving a car) through all US states except Alaska & Hawaii
I thought this was interesting...a Google map allegedly showing how to drive a car through the lower 48 USA states, visiting each state [at least? exactly?] once and minimizing the total distance travelled. http://goo.gl/maps/90i0Y -- Thane Plambeck tplambeck@gmail.com http://counterwave.com/
er, hamiltonian path On Wed, Jun 4, 2014 at 11:36 AM, Thane Plambeck <tplambeck@gmail.com> wrote:
I thought this was interesting...a Google map allegedly showing how to drive a car through the lower 48 USA states, visiting each state [at least? exactly?] once and minimizing the total distance travelled.
-- Thane Plambeck tplambeck@gmail.com http://counterwave.com/
-- Thane Plambeck tplambeck@gmail.com http://counterwave.com/
It couldn't be exactly once, since the graph of the states' connectivity has more than two odd-valence nodes (e.g., California, New Hampshire, West Virginia, North Dakota, Kentucky). --Dan The Traveling Salesman Problem (TSP) is similar, but different: Given that a cost has been assigned to each ordered pair of points of a finite set, find a round trip through all points with the least total cost. The general version doesn't put any conditions on the cost function (it could be asymmetric). Various versions assume the cost is a metric, or that it is Euclidean distance of points in the plane. But this problem seems to be let the U.S. road system define the graph and its cost function, with the requirement being to make a round trip that visits each state (which could be defined as a set of edges) at least once. I suppose it could be called a big generalization of the TSP. --Dan On Jun 4, 2014, at 11:36 AM, Thane Plambeck <tplambeck@gmail.com> wrote:
I thought this was interesting...a Google map allegedly showing how to drive a car through the lower 48 USA states, visiting each state [at least? exactly?] once and minimizing the total distance travelled.
-- Thane Plambeck tplambeck@gmail.com http://counterwave.com/ _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I can find a Hamiltonian tour of the dodecahedron, despite all 20 vertices having odd degree. Perhaps you're confusing this with the Eulerian cycle problem...? Sincerely, Adam P. Goucher
Sent: Thursday, June 05, 2014 at 1:06 AM From: "Dan Asimov" <dasimov@earthlink.net> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Shortest Euler path (driving a car) through all US states except Alaska & Hawaii
It couldn't be exactly once, since the graph of the states' connectivity has more than two odd-valence nodes (e.g., California, New Hampshire, West Virginia, North Dakota, Kentucky).
--Dan
The Traveling Salesman Problem (TSP) is similar, but different: Given that a cost has been assigned to each ordered pair of points of a finite set, find a round trip through all points with the least total cost. The general version doesn't put any conditions on the cost function (it could be asymmetric). Various versions assume the cost is a metric, or that it is Euclidean distance of points in the plane.
But this problem seems to be let the U.S. road system define the graph and its cost function, with the requirement being to make a round trip that visits each state (which could be defined as a set of edges) at least once. I suppose it could be called a big generalization of the TSP.
--Dan
On Jun 4, 2014, at 11:36 AM, Thane Plambeck <tplambeck@gmail.com> wrote:
I thought this was interesting...a Google map allegedly showing how to drive a car through the lower 48 USA states, visiting each state [at least? exactly?] once and minimizing the total distance travelled.
-- Thane Plambeck tplambeck@gmail.com http://counterwave.com/ _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Yes, I must have been. --Dan On Jun 5, 2014, at 5:23 AM, Adam P. Goucher <apgoucher@gmx.com> wrote:
I can find a Hamiltonian tour of the dodecahedron, despite all 20 vertices having odd degree. Perhaps you're confusing this with the Eulerian cycle problem...?
participants (3)
-
Adam P. Goucher -
Dan Asimov -
Thane Plambeck