#NEWLINE# def optimise_points( points ) : #NEWLINE# #INDENT# '\n    This algorithm takes some points and then tries to figure out the shortest\n    route between them.\n    \n    It uses "as the crow flies" distance, which may not necessarily be the best.\n    \n    Points should be a list of tuples, where the first element is the object\n    and the second element is the location of that object (first element is\n    ignored by this algorithm, but is useful for you to correlate the resulting\n    order with your original).\n    \n    This assumes that the first point is always the starting point of the user\n    ' #NEWLINE# if ( len ( points ) > 10 ) : #NEWLINE# #INDENT# raise NotImplementedError ( ) #NEWLINE# #UNINDENT# distances = { #NEWLINE# #INDENT# #NEWLINE# #UNINDENT# } #NEWLINE# for ( e , x ) in points : #NEWLINE# #INDENT# for ( e , y ) in points : #NEWLINE# #INDENT# distances [ ( x , path ) ] = haversine ( x , y ) #NEWLINE# #UNINDENT# #UNINDENT# def tsp_recurse( current , remaining ) : #NEWLINE# #INDENT# weights = [ ] #NEWLINE# for point in remaining : #NEWLINE# #INDENT# path = [ point [ 0 ] ] #NEWLINE# weight = distances [ ( current , point [ 1 ] ) ] #NEWLINE# next = set ( remaining ) #NEWLINE# next . remove ( point ) #NEWLINE# if next : #NEWLINE# #INDENT# ( path_r , weight_r ) = tsp_recurse ( point [ 1 ] , next ) #NEWLINE# weight += weight_r #NEWLINE# path += path_r #NEWLINE# #UNINDENT# weights . append ( ( path , weight ) ) #NEWLINE# #UNINDENT# return min ( weights , key = itemgetter ( 1 ) ) #NEWLINE# #UNINDENT# ( path , weight ) = tsp_recurse ( points [ 0 ] [ 1 ] , set ( points [ 1 : ] ) ) #NEWLINE# return ( [ points [ 0 ] [ 0 ] ] + path )