A useful transform of standard input data for a classical NP-complete problem (Q1058470)

The archetypal symmetric travelling salesman problem can be seen in a new and interesting way, by using first a standard preparatory phase of input data, and then by applying a transform from the set D of 'distances' among 'cities' and the set B of 'loss of optimality'. The specific form of the \(D\to B\) transform is introduced and discussed. In order to show in realistic terms the interest of the approach proposed, a class of 'diffusive' heuristic procedures operating from B is defined. An example of solution by an algorithm included in this class is completely worked out; an outline of computational tests done on the same algorithm is also given.