Re: [boost] BGL: traveling sales man

From: Oliver Kullmann (O.Kullmann_at_[hidden])
Date: 2007-10-23 16:04:08

>   - It would be nice if we had the 1.5x approximation rather than the 2x 
> approximation, of course...
> Sure, it's always good to have shortcut algorithm for the simplest cases.

I would like to take the opportunity to say something about different
algorithms for computing something (similar); actually I wanted to
write already for some time to the Boost mailing lists, alarmed by
a statement like

The current implementation is based on descriptions of a backtracking algorithm in [46,48]. The file isomorphism-impl.pdf contains a "literate" description of the implementation. The algorithm used is simple but slow. A more efficient (and much more complex) algorithm is described in [47]. When (and if) a version of this algorithm is ported to the BGL interface it should replace the current algorithm.

at

http://www.boost.org/libs/graph/doc/isomorphism.html

(I kind of remember having seen something similar elsewhere).

Something like that, heading for the phantom of the "one and only algorithm",
would be a BIG MISTAKE:

1) No algorithm dominates another algorithm (note that I speak of algorithms, not
of implementations), especially not for hard problems like TSP, graph colouring
or graph isomorphism: Every algorithm has its special uses and special favourable
cases (for example "small graphs", or "exact solution").

2) Algorithms are an object of study on their own! Especially the simple ones are studied
extensively for many different purposes (you want to understand their behaviour,
or perhaps they show an interesting pattern).

So the more implementations the better! (I mean implementations of *algorithms*,
which have some meanings, and are not just heuristical hacks --- but even those
are interesting, if they are well-known.)

I do myself research in algorithms similar to TSP and graph colouring,
and I (and every colleague) is happy about every additional implementation
you find (for example for teaching).

Here we really have a field where we can (and should) apply political
correctness: All algorithms are created equal (in some sense) !

Hope this saves some endangered algorithms (and implementations).

Oliver