Distribution of distances in the Travelling Salesman Problem on a square lattice

• Autorzy: Domański, Z. , Kęsy, J.
• Języki publikacji: EN

Abstrakty

EN

The Manhattan distance between two points is defined as the sum of the horizontal distance along streets and the vertical distance along avenues. We derive an exact formula for the number of zigzag distances travelled by a salesman on a finite N × N, square lattice. In the limit N → ∞, we obtain the density function of distances on a unit square.

Słowa kluczowe

EN

travelling salesman problem; square lattice

• Czasopismo: Prace Naukowe Instytutu Matematyki i Informatyki Politechniki Częstochowskiej
• Rocznik: 2004
• Tom: Vol. 3, nr 1
• Strony: 27--30
• Opis fizyczny: Bibliogr. 4 poz., rys.

Twórcy

autor

Domański, Z.

• Institute of Mathematics and Computer Science, Czestochowa University of Technology
• Polonia University, Częstochowa

autor

Kęsy, J.

• Institute of Mathematics and Computer Science, Czestochowa University of Technology

Bibliografia

• [1] Chang C., Mohapatra P., J. Parallel Distrib. Comput. 1998, 52, 40-68.
• [2] Michalewicz Z., Genetics Algorithms + Data Structures = Evolution Programs, Springer Verlag, Berlin, Heidelberg 1996.
• [3] Whitley D., Starkweather T., Fuquay D.A., Scheduling Problems and Traveling Salesman: The Genetic Edge Recombination Operator, Proc. of the 3th Int. Conf. on Genetic Algorithms, ed. J. Schaffer, Morgan Kaufmann Publishers 1988, 133-140.
• [4] Bender C.M., Bender M.A., Demaine E.D., Fekete S.P., Journal of Phys. A: Math. Gen. 2004, 37, 147-159.