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, starting with "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 >>, and
they are the building blocks of the optimal closed bitonic tour we're trying to
find.

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 edges

For 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 with
the 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 lengths
for 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 also
include all intermediate points C<1>-C<4>.  This means C<T(0,5)> is composed of
points C<0> through C<5> in order.  This is also the union of C<T(0,4)> and the
line 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 of
C<5>.  To preserve the bitonicity of C<T(1,5)>, the only possibility for the
tour is the union of C<T(1,4)> and line segment C<4>-C<5>.  I have included a
short proof by contradiction of this in the source code.

=begin comment

Proof 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 in
      the 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 the
    middle 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 its
    left.
 4. Combined with the segment from 5 to P, a vertical line immediately to the
    left of point 4 must cross at least three line segments, thus our proposed
    T(1,5) is not bitonic.

Thus points 4 and 5 must be adjacent in tour T(1,5), so the tour must be the
optimal tour from 1 to 4 (more convenently called "T(1,4)"), plus the segment
from 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)>, because
the leftmost point (point 4) must be an endpoint in the tour.  Via proof by
contradiction similar to the above, our choices for constructing C<T(4,5)> are:

    T(0,4) + line segment from 0 to 5
    T(1,4) + line segment from 1 to 5
    T(2,4) + line segment from 2 to 5
    T(3,4) + line segment from 3 to 5

All of them meet our bitonicity requirements, so we choose the shortest of
these 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_tour

Find the length of the optimal complete (closed) bitonic tour.  This is done by
choosing 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 other
endpoint 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 the
optimal 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 from
C<$i> to "C<$x>" to C<$j>.  All points C<$x> in the range C<(0 .. $i - 1)> are
examined to find the optimal tour.

=cut

sub optimal_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 the
optimal 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, going
from C<$i> to C<$j-1> to C<$j>.

=cut

sub optimal_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 with
endpoints (C<$i>, C<$j>).

=cut

sub tour {
    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>.

=cut

sub tour_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 open
bitonic tour with endpoints (C<$i>, C<$j>).

If C<@points> is specified, set the endpoints to C<@points>.

=cut

sub tour_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/, 'die on unpopulated tour length';
throws_ok { $b->tour_points(1,2) } qr/Don't know the points/, 'die on 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 exception
throws_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';