[Purdue-pm] Mark's Travelling Capital Problem

[Dave Jacoby]

On 02/18/2011 09:58 AM, Mark Senn wrote:
> Here's a brief statement of the problem.  Starting at any state capital
> in the lower 48 go to the other 47 state capitals visiting each capital
> only once.  Figure out the longest and shortest path.  Send your solution,
> guess, etc., in the form, for example,
>      from: Mark Senn
>      name: states visited in random order
>      path: CADEIN[note: 45 more state abbreviations should go here -mark]
> Use a unique name for each path submitted.
>
> I'll write something up about this.  Let me know if you don't want your
> solution, guess, etc. included in the write-up.

It strikes me that having some consistency in the data so that the 
differences are related to the path-deciding algorithm would make great 
amounts of sense. In that spirit, here's my data for the state capitals, 
tab-delimited.

Right now, I'm seeing that depth-first is giving me a demonstrably-wrong 
solution quickly, but working out a breadth-first algorithm that would 
work is not initially obvious.

I used the haversine formula 
(http://en.wikipedia.org/wiki/Haversine_formula) to determine distances. 
Certainly it is point-to-point and not equivalent to what you'd do for 
driving, but that's a much more complex calculation.

-- 
Dave Jacoby                         Address: WSLR S049
Code Maker                          Mail:    jacoby at purdue.edu
Purdue University                   Phone:   765.49.67368
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: state_data.txt
URL: <http://mail.pm.org/pipermail/purdue-pm/attachments/20110218/d3c519f3/attachment.txt>