The travelling salesman problem, revisited with APL

ABSTRACT

This paper introduces a new algorithm for the TSP and the class of n-p complete combinatory problems, which was first found empirically, with the help of APL - used as a “tool of thought”. Then, a demonstration was worked out, which shows that simplicity - as well as vector programming - might lead to significant progresses in some fields of optimization. Programs are short and efficient. Reprogramming in Pascal or Fortran leads to a code that proved to run indeed faster than the interpreted APL models.… but only to a certain extent. The use of parallel processors would still greatly improve the solution of the TSP. APL should also play a role in this new tendency of computer science.

REFERENCES

• 1: "Tbe Traveling Salesman Problem", Lawler,E.L. Lcnstra,J.K., Rinooy Kban,h.H.G. C Shmoys,D.B., J.Wiley & Sons Ltd, (1985), ISBN 9-471-99413-9.
• 2: Neuville,F. Science et Vie Micro, (in French) 41, (July 1987) 6r ibid., 43, 97, (Oct. 1987).
• 3: Lin,S. & Kernighan, Oper. Res. 21, 498-516 (1973).
• 4: HopIield,J.J. k Tank,D.W., Biol. Cybern. 52, 3, 141-152 (1985).
• 5: QiEhel,M. Math. Programming Stud. 12, 61-77
• 6: Durbin,R. k Willshaw,D., "The Elastic net method", Nature, 326, (C1987), 689.
• 7: Uhry,J.P., "Applications of Simulated Annealing in Operation Research", Int. Series of Num. Maths., BirkhYuser Verlag, Base1 (1989).
• 8: Y. Burnod, An adaptive neural network: the cerebral cortex, Masson editeur, Paris, France, 1990
• 9: Lang1etG.A. "Sorting algorithms for parallel processing", in preparation for APL-CAM Journal, Belgium (late 1990).
• 10: Padberg,M. & Rinaldi,G. 'Optimization of a 532-city symmetric travelling salesman problem", 20th Anniv. of the Combinatory Group, AFCET (Dec. 1986). See also: {l} p.307-360.
• 11: Sykes,R.A,Jr. "Big-O Notation", APL News, 21,3,10 (1989).
• 12: Langlet,G.A. "Structured Programming in APL: a Must for its future", APL-CAM Journal, BACUS, Belgium, 11, 3, p. 660-668 (in English) (July 1989).

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: APL

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Languages, Theory