TSP solver
This page implements a solver for Travelling Salesman Problems. It is the type where you have to specify
the distances between the places, where a place is defined with a unique
identifier. The specified distances are bi-directional, meaning that the
distance is the same for both directions. For distances that are not
specified are calculated, where it is possible to specify a maximum number of
intermediate places (hops) or a maximum distance through any number of hops.
Setting both values to zero, will cause no additional distances to be
calculating and thus only find solutions that never revisit a place. This is
only possible if the problem contains at least one
Hamiltonian cycle.
Furthermore, it allows you to define a maximum distance. Solutions larger than
the distance are not displayed. The algorithm works by extending a set of
partial solutions one connection at the time. The bag size determines the
maximum number solutions for each step. The larger the number, the more likely
the algorithm finds a smaller solution, but the more time the algorithm takes
to finish. (But it could also find less solutions. I do not understand
exactly why.)
Programs |
Home