[Purdue-pm] Mark's Travelling Capital Problem

[Bradley Andersen]

Here's some general links I used a long time ago; they may be good or
not; I haven't looked at them in a while:

http://search.cpan.org/~bluefeet/GIS-Distance-0.07/lib/GIS/Distance/Formula/GreatCircle.pm
**** http://mathforum.org/library/drmath/view/51879.html ****
http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL
http://itouchmap.com/latlong.html
http://mathworld.wolfram.com/GreatCircle.html
http://www.codecodex.com/wiki/Calculate_Distance_Between_Two_Points_on_a_Globe

Those are straight from an email I wrote myself.  I don't recall why
the emphasis on the mathforum link.  I do recall the first link for
the perl module gave really fuzzy answers.  That module seems a work
in progress and falls flat at short distances, as the author himself
notes.

Attached is the first great circle perl solution I found online that I
adapted for my ultimate zip codes++ answer.  This code is someone
else's but the standard warranty and license stuff is there.  it is
very old code; surely better ways now.

\brad

++ by 'zip codes' i really mean 'pin codes', as i was working out
distances between 'cities' in India, and they call their zip codes pin
codes.  i had a fat db of lat/lon to use, so this script was helpful,
and gave better answers than, say, the above-quoted perl module.  i
worked out an even fatter crosstable of distances between all cities
in india.



2011/2/18 Dave Jacoby <jacoby at purdue.edu>:
> 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
>
> _______________________________________________
> Purdue-pm mailing list
> Purdue-pm at pm.org
> http://mail.pm.org/mailman/listinfo/purdue-pm
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: distance.pl
Type: application/octet-stream
Size: 7710 bytes
Desc: not available
URL: <http://mail.pm.org/pipermail/purdue-pm/attachments/20110218/11efa691/attachment-0001.obj>