Traveling Salesman without Farmer's Daughter

Have posted some related details to the problem, specifically some database access boilerplate.

The challenge is not traditional Traveling Salesman, which brings you back to the start. In this case, this is all the state capitals in the continental US, and the challenge is to get through all of them in the shortest distance, but was not getting back to the start.

This is my naive solution, which is starting from what I judged to be the furthest east (Maine) and going westward, choosing the shortest capital-to-capital distance. This is easy, and it avoids the biggest pitfall, the one that makes this a named problem.

Starting at one capital, you have 47 choices. For each of them, there are then 46 choices each, and then 45, and so on. The notation for that is n! (as opposed to !n which means not n) and it is big. 1.24x10⁶¹. This means that generating all possible paths would take forever even on big iron. The CS term is nondeterministic polynomial, or NP. Traveling Salesman is NP-Complete, IIRC. What this means is that, while finding a relatively fast way through this is pretty easy, finding the provably shortest isn't.

But I'm sure I can do better than this naive solution. The backtracking to get Vermont in makes me think that starting with Vermont and New Hampshire might be the better solution, and the jump from Tennessee to Michigan tells me that simple shortest-path is not the best solution there. I can generate this fast with simple recursion, getting a simple ordered list, doing the transforms that could tweak this into a faster path is something I don't really know how to do, code-wise.

Here's my Perl code, including some dyked-out bits covering some other cases. The first thing I can think of is to check every edge and each time two edges cross, switch the order of the second node for each edge. I think that could work, if I could decide how to code it. 

#!/usr/bin/perl

# naive shortest-path determination - sucks

use 5.010 ;
use strict ;
use warnings ;
use Data::Dumper ;
use DBI ;

use lib '/home/jacoby/lib' ;
use MyDB 'db_connect' ;

my $states    = get_states() ;
my $combos    = get_combos() ;
my $distances = get_distances() ;
my %shortest ;

#for my $start ( 1..48 ) {
#    my $state = $states->{ $start }->{ state } ;
#    my $dist  = choose_shortest_path( $start ) ;
#    say join "\t", (sprintf '%02.2f' , $dist), $start, $state ;
#    }
#exit ;

# 23 = maine

#
##say 'long' ;
##say choose_longest_path( 23 ) ;
##say '' ;

#say 'short' ;
#choose_shortest_path( 23 ) ;
#say Dumper \%shortest ;
#say '' ;
#
#my ( $s ) = sort { $shortest{ $a } <=> $shortest{ $b } } keys %shortest ;
#
#say as_mark_list( $s ) ;
#say '' ;
#say as_google_url( $s ) ;
#say '' ;

sub as_mark_list {
    my ( $path ) = @_ ;
    return join '', map { $states->{ $_ }->{ st } }
        split m{\|}mx, $path ;
    }

sub as_google_url {
    my ( $path ) = @_ ;
    my $url1 =
        'http://maps.google.com/maps/api/staticmap?path=color:0xff0000ff|weight:1|'
        ;
    my $url2 = '&size=500x400&sensor=false' ;
    my $body = join '|', map {
        join ',', $states->{ $_ }->{ latitude },
            $states->{ $_ }->{ longitude }
            }
        split m{\|}mx, $path ;
    return join '', $url1, $body, $url2 ;
    }

sub key_from_value {
    my %rev = reverse %shortest ;
    my ( $v ) = @_ ;
    return $rev{ $v } ;
    }

sub choose_shortest_path {
    my @path = @_ ;
    do {
        #say join '|', reverse map {
            #join ',',
        #        $states->{ $_ }->{ latitude },
        #        $states->{ $_ }->{ longitude }
        #        } @path ;
        #say as_mark_list( join '|', @path ) ;
        #say as_google_url( join '|', @path ) ;
        return 0 ;
        }
        if scalar @path == 48 ;

    #say join ' ' , scalar @path , '-' , @path ;
    my $s_id    = shift @path ;
    my $state   = $states->{ $s_id }->{ state } ;
    my @choices = sort {
        $distances->{ $a }->{ distance } <=> $distances->{ $b }->{ distance }
        }
        grep {
                is_not_in_array( $combos->{ $_ }->{ state_id_1 }, \@path )
            and is_not_in_array( $combos->{ $_ }->{ state_id_2 }, \@path )
            }
        grep {
               $combos->{ $_ }->{ state_id_1 } == $s_id
            or $combos->{ $_ }->{ state_id_2 } == $s_id
            } keys %$combos ;
    my $c     = shift @choices ;
    my $c_obj = $combos->{ $c } ;
    my ( $o ) = grep { $_ != $s_id } $c_obj->{ state_id_1 },
        $c_obj->{ state_id_2 } ;
    my $o_state = $states->{ $o }->{ state } ;
    my $d = $distances->{ $c }->{ distance } || 'x' ;

    #say $state ;

    #say join "\t", '', $d, $c, $s_id, $state, $o, $o_state ;
    #say join "\t", '', join ' ' , @path ;
    #say '' ;
    my $dist = choose_shortest_path( $o, $s_id, @path ) ;
    return $dist + $d ;
    }

#sub choose_longest_path {
#    my @path = @_ ;
#    do {
#        say join '|', reverse map {
#            join ',',
#                $states->{ $_ }->{ latitude },
#                $states->{ $_ }->{ longitude }
#                } @path ;
#        say as_mark_list( join '|', @path ) ;
#        say as_google_url( join '|', @path ) ;
#        return 0 ;
#        }
#        if scalar @path == 48 ;
#
#    #say join ' ' , scalar @path , '-' , @path ;
#    my $s_id    = shift @path ;
#    my $state   = $states->{ $s_id }->{ state } ;
#    my @choices = sort {
#        $distances->{ $a }->{ distance } <=> $distances->{ $b }->{ distance }
#        }
#        grep {
#                is_not_in_array( $combos->{ $_ }->{ state_id_1 }, \@path )
#            and is_not_in_array( $combos->{ $_ }->{ state_id_2 }, \@path )
#            }
#        grep {
#               $combos->{ $_ }->{ state_id_1 } == $s_id
#            or $combos->{ $_ }->{ state_id_2 } == $s_id
#            } keys %$combos ;
#    my $c     = pop @choices ;
#    my $c_obj = $combos->{ $c } ;
#    my ( $o ) = grep { $_ != $s_id } $c_obj->{ state_id_1 },
#        $c_obj->{ state_id_2 } ;
#    my $o_state = $states->{ $o }->{ state } ;
#    my $d = $distances->{ $c }->{ distance } || 'x' ;
#
#    #say $state ;
#
#    #say join "\t", '', $d, $c, $s_id, $state, $o, $o_state ;
#    #say join "\t", '', join ' ' , @path ;
#    #say '' ;
#    my $dist = choose_longest_path( $o, $s_id, @path ) ;
#    return $dist + $d ;
#    }

sub is_not_in_array {
    my ( $num, $path ) = @_ ;
    for my $p ( @$path ) {
        return 0 if $num == $p ;
        }
    return 1 ;
    }

sub get_states {
    my $dbh    = db_connect() ;
    my $sql    = 'SELECT * from state_capitals ORDER BY id' ;
    my $states = $dbh->selectall_hashref( $sql, 'id' ) or croak $dbh->errstr ;
    return $states ;
    }

sub get_combos {
    my $dbh    = db_connect() ;
    my $sql    = 'SELECT * from combinations ORDER BY id' ;
    my $combos = $dbh->selectall_hashref( $sql, 'id' ) or croak $dbh->errstr ;
    return $combos ;
    }

sub get_distances {
    my $dbh    = db_connect() ;
    my $sql    = 'SELECT * from distances ORDER BY id' ;
    my $combos = $dbh->selectall_hashref( $sql, 'id' ) or croak $dbh->errstr ;
    return $combos ;
    }