I don’t know whether to be disappointed or relieved: I couldn’t find a single fly in my casserole.
Here’s the solution to last week’s traveling pea soup salesman problem.
The shortest possible round-trip route visiting all 35 towns is 3198 miles, as follows (of course you can start at any point on the circuit and proceed in either direction):
Eureka; Redding; Chico; Susanville; Truckee; Sacramento; Stockton; Modesto; Santa Nella; Merced; Sequoia Park; Selma; Fresno; Yosemite; Bishop; Barstow; Needles; El Centro; San Diego; Palm Springs; San Bernardino; Riverside; Long Beach; Los Angeles; Bakersfield; Ventura; Santa Barbara; Buellton; San Luis Obispo; Monterey; Santa Cruz; San Jose; Oakland; San Francisco; Santa Rosa; Eureka.
Dining recently at Pea Soup Andersen’s in Santa Nella, California, I started wondering about the mileage chart on the placemat:
Using the distances given on this chart, how far would I have to drive to visit all 35 towns listed and return to my starting point? Each town should be visited just once. (This restriction is significant, because some mileages on the chart violate the “triangle inequality”: sometimes you can find a shorter distance by going through an intermediate town instead of bypassing it. In most cases the saving is only a few miles, but in a few instances it is substantial. For example, going from San Bernardino to Truckee by the “principal” route, the chart shows the distance as 544 miles, but going via Bishop the total distance would be only 251 + 213 = 464 miles–a saving of 80 miles by using US Route 395 instead of Interstate 5.)
This is of course the well known “traveling pea soup salesman” problem of computer science. I have found a solution which I’ll give next week, but for now I would be interested to see if anyone can come up with a better answer than mine.