Symbolic algebra packages like Maple and Mathematical can be
extremely useful in your coursework, and they are easy to use
Maple is installed
on the arizona machines (maple and the X-Windows version
xmaple).
Here's a session to compute 50! exactly
and in scientific notation.
tucson.Princeon.EDU% maple
> 50!;
30414093201713378043612608166064768844377641568960512000000000000
> 1.0 * 50!;
65
.3041409320 10
> quit;
tucson.Princeon.EDU%
Maple can do much more than arbitrary precision arithmetic.
Here's a session to compute the integral of x/(x^3 -1),
and then evaluate it from 2 to infinity.
tucson.Princeon.EDU% maple
> int( x/(x^3-1), x );
2 1/2 1/2
1/3 ln(x - 1) - 1/6 ln(x + x + 1) + 1/3 3 arctan(1/3 (2 x + 1) 3 )
> int( x/(x^3-1), x = 2 .. infinity);
1/2 1/2 1/2
1/6 3 Pi + 1/6 ln(7) - 1/3 3 arctan(5/3 3 )
> quit;
Submission and readme  
|
Possibilities for improvement are endless. Here are some
ideas.
If you are shooting for an A+,
you should definitely attempt the extra credit.
For the extra credit, you are permitted to change any
of the files (including tsp.c and TOUR.h) to
suit your needs. Some of the suggested heuristics
do not insert points in the same order as the input, so you
will need a preprocessing step to determine the order.
Other heuristics do a postprocessing step after all the points
are inserted.
Be sure to include compilation instructions for your
extra credit solution.
Here's the source of our
TSP test data.
A
3,795 node TSP problem that arises from circuit drilling
is available in our input format.
Here's a 13,509 city problem that
contains each of the 13,509 cities in the continental US with
population over 500. The
optimal solution
was discovered in 1998 by Applegate, Bixby, Chvatal and Cook
using theoretical ideas from linear and integer
programming.
The following
15,112 city problem was solved
to optimality in April, 2001, and is the current world record.
It took 585,936,700 CPU seconds (along with alot of cleverness)
to find the optimal tour through 15,112 cities in Germany.
Here's a nice pictorial survey of the history of the TSP
problem.
Some folks even use the TSP to create and sell art.
Check out
Julian Lethbridge's page. Feel free to go crazy with PostScript
(use fill instead of stroke) and make your
own art.
Kevin Wayne