view release on metacpan or  search on metacpan

lib/Algorithm/TravelingSalesman/BitonicTour.pm  view on Meta::CPAN

The construction of tour C<T(i,j)> depends on knowledge of tours to the left of
C<j>:

    to construct:   one must know:
    -------------   --------------
    T(0,5)          T(0,4)
    T(1,5)          T(1,4)
    T(2,5)          T(2,4)
    T(3,5)          T(3,4)
    T(4,5)          T(0,4), T(1,4), T(2,4), T(3,4)

We also see that a given optimal tour is used I<more than once> in constructing
longer tours.  For example, C<T(1,4)> is used in the construction of both
C<T(1,5)> and C<T(4,5)>.

=head3 Optimal Substructure

As shown in the above analysis, constructing a given optimal tour depends on
knowledge of shorter "included" optimal tours; suboptimal tours are irrelevant.

=head1 EXERCISES

These exercises may clarify the above analysis.

=over 4

=item Exercise 1.

Consider the parallelogram ((0,0), (1,1), (2,0), (3,1)).

    a. Draw it on graph paper.
    b. Label points "0" through "3"
    c. Draw t[0,1].  Calculate its length.
    d. Draw t[0,2] and t[1,2].  Calculate their lengths.
    e. Draw t[0,3], t[1,3], and t[2,3].  Calculate their lengths.
    f. What is the optimal bitonic tour?
    g. Draw the suboptimal bitonic tour.
    h. Why does the above algorithm find the optimal tour,
       and not the suboptimal tour?

=item Exercise 2.

Repeat Exercise 1 with pentagon ((0,2), (1,0), (2,3), (3,0), (4,2)).

=back

=head1 METHODS

=head2 $class->new()

Constructs a new solution object.

Example:

    my $ts = Algorithm::TravelingSalesman::BitonicTour->new;

=cut

sub new {
    my $class = shift;
    my $self = bless { _tour => {}, _points => {} }, $class;
    return $self;
}

=head2 $ts->add_point($x,$y)

Adds a point at position (C<$x>, C<$y>) to be included in the solution.  Method
C<add_point()> checks to make sure that no two points have the same
I<x>-coordinate.  This method will C<croak()> with a descriptive error message
if anything goes wrong.

Example:

    # add point at position (x=2, y=3) to the problem
    $ts->add_point(2,3);

=cut

sub add_point {
    my $self = shift;
    my $valid = { type => SCALAR, regexp => $RE{num}{real} };
    my ($x, $y) = validate_pos(@_, ($valid) x 2);
    if (exists $self->_points->{$x}) {
        my $py = $self->_points->{$x};
        croak "FAIL: point ($x,$y) duplicates previous point ($x,$py)";
    }
    else {
        $self->_sorted_points(undef);   # clear any previous cache of sorted points
        $self->_points->{$x} = $y;
        return [$x, $y];
    }
}

=head2 $ts->N()

Returns the number of points that have been added to the object (mnemonic:
B<n>umber).

Example:

    print "I have %d points.\n", $ts->N;

=cut

sub N {
    my $self = shift;
    return scalar keys %{ $self->_points };
}

=head2 $ts->R()

Returns the index of the rightmost point that has been added to the object
(mnemonic: B<r>ightmost).  This is always one less than C<< $ts->N >>.

=cut

sub R {
    my $self = shift;
    die 'Problem has no rightmost point (N < 1)' if $self->N < 1;
    return $self->N - 1;
}