view release on metacpan or  search on metacpan

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

}

=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];
        croak "ERROR: tour_points($i,$j,@_) ($j != last point)"
            unless $j == $_[-1];
        croak "ERROR: tour_points($i,$j,@_) (wrong number of points in @_)"
            unless scalar(@_) == $j + 1;
        $self->tour($i,$j)->[1] = \@_;
    }
    if (exists $self->tour($i,$j)->[1]) {
        return @{ $self->tour($i,$j)->[1] };
    }
    else {
        croak "Don't know the points for tour($i,$j)";
    }
}

=head2 $b->delta($p1,$p2);

Returns the euclidean distance from point C<$p1> to point C<$p2>.

Examples:

    # print the distance from the leftmost to the next point
    print $b->delta(0,1);
    # print the distance from the leftmost to the rightmost point
    print $b->delta(0,-1);

=cut

sub delta {
    my ($self, $p1, $p2) = @_;
    my ($x1, $y1) = $self->coord($p1);
    my ($x2, $y2) = $self->coord($p2);
    return sqrt((($x1-$x2)*($x1-$x2))+(($y1-$y2)*($y1-$y2)));
}


=head1 RESOURCES

=over 4

=item

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford
(2001). Introduction to Algorithms, second edition, MIT Press and McGraw-Hill.
ISBN 978-0-262-53196-2.

=item

Bentley, Jon L. (1990), "Experiments on traveling salesman heuristics", Proc.
1st ACM-SIAM Symp. Discrete Algorithms (SODA), pp. 91-99,
L<http://portal.acm.org/citation.cfm?id=320186>.

=item

L<http://en.wikipedia.org/wiki/Bitonic_tour>

=item

L<http://en.wikipedia.org/wiki/Traveling_salesman_problem>

=item

L<http://www.tsp.gatech.edu/>

=item

L<http://en.wikipedia.org/wiki/Dynamic_programming>

=back

=head1 AUTHOR

John Trammell, C<< <johntrammell at gmail dot com> >>

=head1 BUGS

Please report any bugs or feature requests to C<bug-cormen-bitonic at
rt.cpan.org>, or through the web interface at
L<http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Algorithm-TravelingSalesman-BitonicTour>.
I will be notified, and then you'll automatically be notified of progress on
your bug as
I make changes.

=head1 SUPPORT

You can find documentation for this module with the perldoc command.

    perldoc Algorithm::TravelingSalesman::BitonicTour

You can also look for information at:

=over 4

=item * RT: CPAN's request tracker

L<http://rt.cpan.org/NoAuth/Bugs.html?Dist=Algorithm-TravelingSalesman-BitonicTour>

=item * AnnoCPAN: Annotated CPAN documentation

L<http://annocpan.org/dist/Algorithm-TravelingSalesman-BitonicTour>

=item * CPAN Ratings

L<http://cpanratings.perl.org/d/Algorithm-TravelingSalesman-BitonicTour>