Jon Bentley's Traveling Salesman Programs in C
In "Writing Efficient Programs" (1982), Jon Bentley used a greedy
(non-optimal) traveling-salesman program as running example for
demonstrating various optimizations at the source code level,
resulting in a sequence of programs for the different optimization
steps. The programs in the book were written in Pascal. I
transliterated them to C in 2001, keeping the original optimizations
and a Pascal-like style, except that I did not take Bentley's step 7
of switching from floating point to integer arithmetics. The source
programs are shown below.
tsp1.c
tsp2.c
tsp3.c
tsp4.c
tsp5.c
tsp6.c
No step 7, so no tsp7.c
tsp8.c
tsp9.c
The source programs, IA32 binaries from various compilers with
various options, BUILD and RUN scripts, and
Results: tsp.zip
Anton Ertl