Algorithm-TravelingSalesman-BitonicTour
view release on metacpan or search on metacpan
lib/Algorithm/TravelingSalesman/BitonicTour.pm view on Meta::CPAN
Points are numbered from left to right, startingwith"https://metacpan.org/pod/0">0", then"1", and so on.For convenience I call the rightmost point C<R>.=head2 Key Insights Into the Problem=over 4=item 1. Focus on optimal B<open> bitonic tours.B<Optimal open bitonic tours> have endpoints (i,j) where C<< i < j < R >>, andthey are the building blocks of the optimal closed bitonic tour we're trying tofind.An open bitonic tour, optimal or not, has these properties:* it's bitonic (a vertical line crosses the tour at most twice)* it's open (it has endpoints), which we call "i" and "j" (i < j)* all points to the left of "j" are visited by the tour* points i and j are endpoints (connected to exactly one edge)* all other points in the tour are connected to two edgesFor a given set of points there may be many open bitonic tours with endpoints(i,j), but we are only interested in the I<optimal> open tour--the tour withthe shortest length. Let's call this tour B<C<T(i,j)>>.=item 2. Grok the (slightly) messy recurrence relation.A concrete example helps clarify this. Assume we know the optimal tour lengthsfor all (i,j) to the right of point C<5>:T(0,1)T(0,2) T(1,2)T(0,3) T(1,3) T(2,3)T(0,4) T(1,4) T(2,4) T(3,4)From this information, we can find C<T(0,5)>, C<T(1,5)>, ... C<T(4,5)>.=over 4=item B<Finding C<T(0,5)>>From our definition, C<T(0,5)> must have endpoints C<0> and C<5>, and must alsoinclude all intermediate points C<1>-C<4>. This means C<T(0,5)> is composed ofpoints C<0> through C<5> in order. This is also the union of C<T(0,4)> and theline segment C<4>-C<5>.=item B<Finding C<T(1,5)>>C<T(1,5)> has endpoints at C<1> and C<5>, and visits all points to the left ofC<5>. To preserve the bitonicity of C<T(1,5)>, the only possibility for thetour is the union of C<T(1,4)> and line segment C<4>-C<5>. I have included ashort proof by contradiction of this in the source code.=begin commentProof by contradiction:1. Assume the following:* T(1,5) is an optimal open bitonic tour having endpoints 1 and 5.* Points 4 and 5 are not adjacent in the tour, i.e. the final segment inthe tour joins points "P" and 5, where "P" is to the left of point 4.2. Since T(1,5) is an optimal open bitonic tour, point 4 is included in themiddle of the tour, not at an endpoint, and is connected to two edges.3. Since 4 is not connected to 5, both its edges connect to points to itsleft.4. Combined with the segment from 5 to P, a vertical line immediately to theleft of point 4 must cross at least three line segments, thus our proposedT(1,5) is not bitonic.Thus points 4 and 5 must be adjacent in tour T(1,5), so the tour must be theoptimal tour from 1 to 4 (more convenently called "T(1,4)"), plus the segmentfrom 4 to 5.=end comment=item B<Finding C<T(2,5)-T(3,5)>>Our logic for finding C<T(1,5)> applies to these cases as well.=item B<Finding C<T(4,5)>>Tour C<T(4,5)> breaks the pattern seen in C<T(0,5)> through C<T(3,5)>, becausethe leftmost point (point 4) must be an endpoint in the tour. Via proof bycontradiction similar to the above, our choices for constructing C<T(4,5)> are:T(0,4) + line segment from 0 to 5T(1,4) + line segment from 1 to 5T(2,4) + line segment from 2 to 5T(3,4) + line segment from 3 to 5All of them meet our bitonicity requirements, so we choose the shortest ofthese for C<T(4,5)>.
lib/Algorithm/TravelingSalesman/BitonicTour.pm view on Meta::CPAN
my@coords=map{ [$self->coord($_) ] }@points;return($length,@coords);}=head2 $ts->optimal_closed_tourFind the length of the optimal complete (closed) bitonic tour. This is done bychoosing the shortest tour from the set of all possible complete tours.A possible closed tour is composed of a partial tour with rightmost point C<R>as one of its endpoints plus the final return segment from R to the otherendpoint of the tour.T(0,R) + delta(0,R)T(1,R) + delta(1,R)...T(i,R) + delta(i,R)...T(R-1,R) + delta(R-1,R)=cut
lib/Algorithm/TravelingSalesman/BitonicTour.pm view on Meta::CPAN
# if $i and $j are NOT adjacent, then only one bitonic tour (i => j-1 => j)# is possible.return$self->optimal_open_tour_nonadjacent($i,$j)if$i+ 1 <$j;croak"ERROR: bad call, optimal_open_tour(@_)";}=head2 $obj->optimal_open_tour_adjacent($i,$j)Uses information about optimal open tours to the left of <$j> to find theoptimal tour with endpoints (C<$i>, C<$j>).This method handles the case where C<$i> and C<$j> are adjacent, i.e. C<< $i =$j - 1 >>. In this case there are many possible bitonic tours, all going fromC<$i> to "C<$x>" to C<$j>. All points C<$x> in the range C<(0 .. $i - 1)> areexamined to find the optimal tour.=cutsuboptimal_open_tour_adjacent {my($self,$i,$j) =@_;
lib/Algorithm/TravelingSalesman/BitonicTour.pm view on Meta::CPAN
my@path=reverse($j,$self->tour_points($x,$i) );[$len,@path];} 0 ..$i- 1;my$min_tour= reduce {$a->[0] <$b->[0] ?$a:$b}@tours;return@$min_tour;}=head2 $obj->optimal_open_tour_nonadjacent($i,$j)Uses information about optimal open tours to the left of <$j> to find theoptimal tour with endpoints (C<$i>, C<$j>).This method handles the case where C<$i> and C<$j> are not adjacent, i.e. C<<$i < $j - 1 >>. In this case there is only one bitonic tour possible, goingfrom C<$i> to C<$j-1> to C<$j>.=cutsuboptimal_open_tour_nonadjacent {my($self,$i,$j) =@_;my$len=$self->tour_length($i,$j- 1) +$self->delta($j- 1,$j);my@points= ($self->tour_points($i,$j- 1),$j);return($len,@points);}=head2 $b->tour($i,$j)Returns the data structure associated with the optimal open bitonic tour withendpoints (C<$i>, C<$j>).=cutsubtour {my($self,$i,$j) =@_;croak"ERROR: tour($i,$j) ($i >= $j)"unless$i<$j;croak"ERROR: tour($i,$j,...) ($j >= @{[ $self->N ]})"unless$j<$self->N;$self->_tour->{$i}{$j} = []unless$self->_tour->{$i}{$j};return$self->_tour->{$i}{$j};}=head2 $b->tour_length($i, $j, [$len])Returns the length of the optimal open bitonic tour with endpoints (C<$i>,C<$j>). If C<$len> is specified, set the length to C<$len>.=cutsubtour_length {my$self=shift;my$i=shift;my$j=shift;if(@_) {croak"ERROR: tour_length($i,$j,$_[0]) has length <= 0 ($_[0])"
lib/Algorithm/TravelingSalesman/BitonicTour.pm view on Meta::CPAN
return$self->tour($i,$j)->[0];}else{croak"Don't know the length of tour($i,$j)";}}=head2 $b->tour_points($i, $j, [@points])Returns an array containing the indices of the points in the optimal openbitonic tour with endpoints (C<$i>, C<$j>).If C<@points> is specified, set the endpoints to C<@points>.=cutsubtour_points {my$self=shift;my$i=shift;my$j=shift;if(@_) {croak"ERROR: tour_points($i,$j,@_) ($i != first point)"unless$i==$_[0];
t/02-optimal-tours.t view on Meta::CPAN
$b->add_point(1,1);$b->add_point(2,1);$b->add_point(3,0);is($b->N, 4);is_deeply( [$b->sorted_points], [[0,0], [1,1], [2,1], [3,0]] );# optimal open tours aren't populated yet...throws_ok {$b->tour_length(1,2) }qr/Don't know the length/, 'dieon unpopulated tourlength';throws_ok {$b->tour_points(1,2) }qr/Don't know the points/, 'dieon unpopulated tour points';# make sure population with bad endpoints is caught...throws_ok {$b->tour_points(1,2,0,1,2) }qr/ERROR/,'die on bad endpoints';throws_ok {$b->tour_points(1,2,1,2,3) }qr/ERROR/,'die on bad endpoints';throws_ok {$b->tour_points(1,2,1,2) }qr/ERROR/,'die on wrong number of points';# populate the optimal open tours$b->populate_open_tours;#diag(Dumper($b));# make sure invalid tour queries throw an exceptionthrows_ok {$b->tour(1,0) }qr/ERROR/,'die on invalid tour limits';throws_ok {$b->tour_length(42,142) }qr/ERROR/,'die on invalid length limits';throws_ok {$b->tour_length(0,1,-1) }qr/ERROR/,'die on invalid length';
( run in 0.363 second using v1.01-cache-2.11-cpan-87723dcf8b7 )