The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Algorithm-TravelingSalesman-BitonicTour-0.05
River stage zero No dependents
++
/ Algorithm::TravelingSalesman::BitonicTour

NAME

Algorithm::TravelingSalesman::BitonicTour - solve the euclidean traveling-salesman problem with bitonic tours

SYNOPSIS

    use Algorithm::TravelingSalesman::BitonicTour;
    my $bt = Algorithm::TravelingSalesman::BitonicTour->new;
    $bt->add_point($x1,$y1);
    $bt->add_point($x2,$y2);
    $bt->add_point($x3,$y3);
    # ...add other points as needed...

    # get and print the solution
    my ($len, @coords) = $bt->solve;
    print "optimal path length: $len\n";
    print "coordinates of optimal path:\n";
    print "   ($_->[0], $_->[1])\n" for @coords;

THE PROBLEM

From Introduction to Algorithms, 2nd ed., T. H. Cormen, C. E. Leiserson, R. Rivest, and C. Stein, MIT Press, 2001, problem 15-1, p. 364:

    The euclidean traveling-salesman problem is the problem of determining the shortest closed tour that connects a given set of n points in the plane. Figure 15.9(a) shows the solution to a 7-point problem. The general problem is NP-complete, and its solution is therefore believed to require more than polynomial time (see Chapter 34).

    J. L. Bentley has suggested that we simplify the problem by restricting our attention to bitonic tours, that is, tours that start at the leftmost point, go strictly left to right to the rightmost point, and then go strictly right to left back to the starting point. Figure 15.9(b) shows the shortest bitonic tour of the same 7 points. In this case, a polynomial-time algorithm is possible.

    Describe an O(n^2)-time algorithm for determining an optimal bitonic tour. You may assume that no two points have the same x-coordinate. (Hint: Scan left to right, maintaining optimal possibilities for the two parts of the tour.)

From Wikipedia (http://en.wikipedia.org/wiki/bitonic_tour):

    In computational geometry, a bitonic tour of a set of point sites in the Euclidean plane is a closed polygonal chain that has each site as one of its vertices, such that any vertical line crosses the chain at most twice.

THE SOLUTION

Conventions

Points are numbered from left to right, starting with "0", then "1", and so on. For convenience I call the rightmost point R.

Key Insights Into the Problem

1. Focus on optimal open bitonic tours.

Optimal open bitonic tours have endpoints (i,j) where 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 optimal open tour--the tour with the shortest length. Let's call this tour T(i,j).

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 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 T(0,5), T(1,5), ... T(4,5).

Finding T(0,5)

From our definition, T(0,5) must have endpoints 0 and 5, and must also include all intermediate points 1-4. This means T(0,5) is composed of points 0 through 5 in order. This is also the union of T(0,4) and the line segment 4-5.

Finding T(1,5)

T(1,5) has endpoints at 1 and 5, and visits all points to the left of 5. To preserve the bitonicity of T(1,5), the only possibility for the tour is the union of T(1,4) and line segment 4-5. I have included a short proof by contradiction of this in the source code.

Finding T(2,5)-T(3,5)

Our logic for finding T(1,5) applies to these cases as well.

Finding T(4,5)

Tour T(4,5) breaks the pattern seen in T(0,5) through 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 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 T(4,5).

To summarize the recurrence, and using function delta() to calculate the distance between points:

if i < j-1:

T(i,j) = T(i,j-1) + delta(j-1,j)

if i == j-1:

T(i,j) = min{ T(k,i) + delta(k,j) }, for all k < i

3. The base case.

The open tour T(0,1) has to be the line segment from 0 to 1.

Dynamic Programming

This problem exhibits the classic features suggesting a dynamic programming solution: overlapping subproblems and optimal substructure.

Overlapping Subproblems

The construction of tour T(i,j) depends on knowledge of tours to the left of 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 more than once in constructing longer tours. For example, T(1,4) is used in the construction of both T(1,5) and T(4,5).

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.

EXERCISES

These exercises may clarify the above analysis.

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?
Exercise 2.

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

METHODS

$class->new()

Constructs a new solution object.

Example:

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

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

Adds a point at position ($x, $y) to be included in the solution. Method add_point() checks to make sure that no two points have the same x-coordinate. This method will 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);

$ts->N()

Returns the number of points that have been added to the object (mnemonic: number).

Example:

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

$ts->R()

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

$ts->sorted_points()

Returns an array of points sorted by increasing x-coordinate. The first ("zeroth") array element returned is thus the leftmost point in the problem.

Each point is represented as an arrayref containing (x,y) coordinates. The sorted array of points is cached, but the cache is cleared by each call to add_point().

Example:

    my $ts = Algorithm::TravelingSalesman::BitonicTour->new;
    $ts->add_point(1,1);
    $ts->add_point(0,0);
    $ts->add_point(2,0);
    my @sorted = $ts->sorted_points;
    # @sorted contains ([0,0], [1,1], [2,0])

coord($n)

Returns an array containing the coordinates of point $n.

Examples:

    my ($x0, $y0) = $ts->coord(0);   # coords of leftmost point
    my ($x1, $y1) = $ts->coord(1);   # coords of next point
    # ...
    my ($xn, $yn) = $ts->coord(-1);  # coords of rightmost point--CLEVER!

$ts->solve()

Solves the problem as configured. Returns a list containing the length of the minimum tour, plus the coordinates of the points in the tour in traversal order.

Example:

    my ($length, @points) = $ts->solve();
    print "length: $length\n";
    for (@points) {
        my ($x,$y) = @$_;
        print "($x,$y)\n";
    }

$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 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)

$ts->populate_open_tours

Populates internal data structure tour($i,$j) describing all possible optimal open tour costs and paths for this problem configuration.

$ts->optimal_open_tour($i,$j)

Determines the optimal open tour from point $i to point $j, based on the values of previously calculated optimal tours to the left of $j.

As discussed above, there are two distinct cases for this calculation: when $i == $j - 1 and when $i < $j - 1.

    # determine the length of and points in the tour
    # starting at point 20 and ending at point 25
    my ($length,@points) = $ts->optimal_open_tour(20,25);

$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 ($i, $j).

This method handles the case where $i and $j are adjacent, i.e. $i = $j - 1. In this case there are many possible bitonic tours, all going from $i to "$x" to $j. All points $x in the range (0 .. $i - 1) are examined to find the optimal tour.

$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 ($i, $j).

This method handles the case where $i and $j are not adjacent, i.e. $i < $j - 1. In this case there is only one bitonic tour possible, going from $i to $j-1 to $j.

$b->tour($i,$j)

Returns the data structure associated with the optimal open bitonic tour with endpoints ($i, $j).

$b->tour_length($i, $j, [$len])

Returns the length of the optimal open bitonic tour with endpoints ($i, $j). If $len is specified, set the length to $len.

$b->tour_points($i, $j, [@points])

Returns an array containing the indices of the points in the optimal open bitonic tour with endpoints ($i, $j).

If @points is specified, set the endpoints to @points.

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

Returns the euclidean distance from point $p1 to point $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);

RESOURCES

AUTHOR

John Trammell, <johntrammell at gmail dot com>

BUGS

Please report any bugs or feature requests to bug-cormen-bitonic at rt.cpan.org, or through the web interface at 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.

SUPPORT

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

    perldoc Algorithm::TravelingSalesman::BitonicTour

You can also look for information at:

COPYRIGHT & LICENSE

Copyright 2008 John Trammell, all rights reserved.

This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.