Data structures

N

It’s a common convention to use N for overall number of cities (points/vertices) in a problem. Since number of cities in given problem doesn’t change during searching for solutions and we do not deal with input/output questions, for simplicity in all places we use positive integer N just as it were a constant:

  const N = 100

Yet there should be no problem to make it a global variable assigned once, in proc reading a problem. In this case arrays dependent on it (see below) would be openarrays or sequences. Anyway in all algorithms we treat N as given and not changing.

City_Number

Cities are identified by their numbers. We starting numbering them from zero and for clarity use a distinct type:

  type City_Number = range[0 .. N-1]

You may replace it by int (see above).

Tour_Array and Tour_Index

Tours are represented by arrays. Tour_Index type is introduced to easily and clearly distinguish between a city number and a number representing position of city in tour.

  type Tour_Index = range[0 .. N-1]
  type Tour_Array = array[Tour_Index, City_Number]

Note that this representation suggest us the “natural” direction in tour, where in fact none of both directions is anyway natural or better than the other. Tour properties considered in symmetric TSP problem are the same in both directions. Even if we — because of ascending array index — tend to treat the direction from tour[i] to tour[i+1] as obvious and preferred “forward”.

Note also that array representation forces us to keep an eye on boundaries and to not forget that a tour is cyclic — and therefore after tour[N-1] city (in ascending order of indices) goes tour[0], to close the tour.

Additional remark

If the difference between City_Number and Tour_Index, both integers ranging from zero to N-1, is not clear enough for you, consider two examples:

  type City_Number = range[0 .. 4]
  type Tour_Index = range[0 .. 4]

Here a variable of type Tour_Array has indices ranging from 0 to 4 and contains numbers of subsequent cities on tour, e.g.: tour[3] == 4 (position no. 3 in tour is occupied by city number 4).

  type City_Number = range["A" .. "D"]
  type Tour_Index = range[0 .. 4]

And here a variable of type Tour_Array has indices ranging from 0 to 4 and contains letters of subsequent cities on tour, e.g. tour[2] == "C" (position no. 2 in tour is occupied by city “C”).

Length and Length_Gain

Numbers representing distances between two cities, sums of such distances, lengths of parts or of whole tour are all of Length type. We follow a common custom of using distances rounded to integers. Differences between lengths, computed during optimizations, are of Length_Gain type.

type
  Length = range[0 .. high(int)] # length is non-negative
  Length_Gain = int              # could be negative (loss)

distance(...)

The most often used function in solving TSP problems is distance(), returning the distance between two cities given as parameters.

proc distance(X, Y: City_Number): Length =
  ...

Important

To speed up processing for small problems distances are usually precomputed and stored in an array, then function returning suitable element from this array is used.