Excerpt from The Satellite List
and New Data Structures for Symmetric Traveling Salesman Problems ††
by Colin Osterman and César Rego
Hearin
Center for
Latest Revision: March, 2003.
3.1 The Satellite List
Our new data
structure, the satellite list, provides a basis for representing any
symmetric path or cycle that may have been previously encoded using a
doubly-linked list. The satellite list can operate in the same capacity as a
doubly-linked list with the following key difference: the satellite list
represents a tour without implying a fixed orientation of the path, which is
why we qualify our claim for symmetric tours. The “next” node in the path
depends on the current orientation, information that is naturally preserved in
traversing the satellite list but otherwise neglected by the doubly-linked
list. A primary consequence of avoiding a fixed orientation is that the subpath reversal operation is performed easily and in
constant time. In addition, the satellite list retains the same efficiency as
the doubly-linked list in terms of the memory it occupies and the commands it
requires to access adjacent nodes.
To obtain a suitable
structure that lacks the structural weakness of the linked list but retains its
simplicity, its strict representation is disassembled. A linked list node
contains two data members: a pointer to the previous client node and a pointer
to the next client node. Pointers should operate in a symmetric fashion,
suggesting that they point toward “adjacent” nodes, rather than “next” or
“previous” ones. To accomplish this, the pointers are first removed from the
structure and given their own structures, called satellites, whose sole purpose is handling the links
among clients in the list. Each satellite points not to an adjacent list node,
as in the linked list representation, but rather to the list node’s satellite.
To read the tour starting from a client, one of its satellites is chosen to
begin the traversal. It is arbitrary which satellite is chosen, just as it
should be, since it makes no difference in which direction a symmetric tour is
traversed. The traversal operation then follows the satellite’s pointer to the
next satellite, the client is noted, and the process continues. Therefore,
reading the tour involves traversing one of two distinct singularly linked
lists of satellites and noting the associated cities.
3.2 Logical Representation
Figure 3.1 depicts a
city represented first as a doubly-linked list node and then as a satellite
list node. The distinguishing characteristic of the satellite list node is its
avoidance of direct links with adjacent structures. Instead, its satellites
link the cities indirectly. The dashed lines in the figure emphasize the parts
of the structure that indicate relationships among components of the list node.
From a satellite, there exists some means to immediately access the complement satellite. A similar relationship associates a
satellite with its city. It is possible for these relationships to be
constructed (e.g. storing a pointer or an index value of the desired
component), but it is more efficient to take advantage of the implementation in
which these relationships are implied, as is illustrated in more detail in the
next section …
|
Figure
3.1 discloses the functional differences between the two types of nodes. The
city represented by the doubly-linked list node
is constructed in memory in such a way that its data members (typically “Next”
and “Previous”) cannot be referenced directly†. The data members
are accessed by name, and are thus not interchangeable and necessitate an
orientation. Also, since the data members store references to entire list
nodes, the node from which a reference was obtained is not remembered. For
instance, it is not correct to assume that a node has been obtained from the
“Next” pointer of the preceding node because it is equally likely to have been
obtained from the “Previous” pointer of the following node, and storing the
information explicitly costs time and memory. On the other hand, this
information remains evident when using the satellite list because each
satellite is reached from a distinct source. Furthermore, two satellites
sharing a list node operate as independent nodes in separate singly-linked
lists, lending directional independence to the list node as a whole. Its
unique symmetry allows the “direction” of the node to depend on how the node
was obtained without incorporating any costly, explicit decision making into
the code.
3.3 Efficient Physical Representation
A satellite list may
be constructed and used without specifically declaring each satellite’s links
(pointers or indices) to its associated complement satellite or its client
(city). This property reduces the number of pointers needed to represent a
list node from four to two, cutting the memory requirement by half.
The tour is
maintained in a single one-dimensional array of length twice n (where n is the number of cities). Each element in
the array is a satellite node and contains the value of (or pointer to) its
adjacent satellite. For each city, there exists two
physical array positions (satellites), which, together, are considered a
logical position representing the client. The city itself needs no physical
position since it can be uniquely identified by the indices of its satellites.
Figure 3.2 diagrams an example satellite list stored in an integer array
representing the circuit (0,1,2,3,4,0).
|
Figure 3.2. Example of Efficient Satellite List
Implementation |
|
|
A key factor that
makes the use of the efficient implementation desirable is the ease with which
the implied relationships mentioned in the previous section can be found.
Given some satellite, the queries are to determine its complement satellite
and its client (city). The general formulas to compute these queries are given
in the figure along with the equivalent bitwise operations in the C language.
A satellite’s client (city) can be computed by integer-dividing the index by 2
(no remainder). An identical result is achieved with the bitwise shift
operator, “>>”. To find a satellite’s complement, the index should be
incremented if it is even and decremented if it is odd. The “%” gives the
remainder of division. A bitwise operator is also available for computing a
satellite’s complement satellite—the exclusive or, “^”. These and other
bitwise operators are extremely fast because they don’t request any
arithmetical or logical computation from the processor; thus, the measure of
overhead they contribute to routine operations such as Previous() is insignificant. For languages that do not support bitwise
operations, using the general formulas may be too costly. In this case, the
computational overhead can be avoided by storing “client” and “complement”
explicitly, although doing so doubles the memory requirement for the
structure. Example C code for both full and efficient implementations and for
queries using the bitwise operators is provided in the appendix.
Although Figure 3.2
shows all odd satellites pointing to odd satellites, the list is perfectly
functional when some odd satellites point to even satellites, or vice versa.
Indeed, this becomes the case for the endpoints of a reversed subpath. Interestingly, when a satellite list is organized
so that the entire list can be read from just the even or
odd satellites, the
satellite list array can be unioned with a
doubly-linked list structure, and the tour can be read correctly from either.
3.4 Memory and Time Efficiency
Unlike other data
structures proposed for the TSP, the satellite list does not impose additional
memory requirements for representing the tour. The memory required to store a
tour represented by the satellite list is exactly equal to that required by
the doubly-linked list—two pointer slots per city. This is not to say that
additional fields cannot be added to a list node for use with specialized
algorithms.
Also, the satellite
list does not impose additional computational effort for the traversal
procedures. Enumerating across several nodes is simply a matter of following a
singly-linked list of satellite nodes; thus, the computational cost is the
same as for the array representation. There is no need to check a “Reverse”
bit (2-level tree) or to splay to the root of a tree (splay tree).
3.5 Subpath
Reversal
We return to the subpath reversal issue, discussed in Section 2.2. This
problem has been of great interest to scholars studying TSP data structures
due to its occurrence in both classic k-opt and state-of-the-art search
methods. In fact, this issue motivates the satellite list design.
The tree-based data
structures mentioned in Section 2 were proposed with the aim of lowering the
computational complexity of the subpath reversal
operation. The splay tree claims to handle the operation in O time, while the 2-level tree claims (log)n(On) time, with better
results for problems as large as n = 106 due
to lower overhead costs. Clearly, however, because of the satellite list’s
symmetric design, the subpath reversal operation is
a natural one and is performed easily in constant time, .
The ease of the operation is illustrated in Figure 3.3.
|
Figure 3.3. Subpath
Reversal with a Linked List vs. a Satellite List |
Figure 3.3 depicts
isolated subpaths for a doubly-linked list (top) and
a satellite list (bottom), where straight arcs point to the following nodes in
the list, and the curved arcs point to preceding nodes (only applicable to the
doubly-linked list). An analogy would be to view the linked list as a one-way
street and the satellite list as a two-lane road. As is easily seen, the subpath in the satellite list reforms the original
structure when rotated 180 degrees—only pointers associated with nodes in the
broken edges need to be changed. The subpath in the
doubly-linked list, however, does not match correctly when rotated—every
pointer associated with nodes in the subpath must be
changed. The “street” analogy would have traffic flowing smoothly only on the
two-lane road if a section of the road were reversed. In the linked list,
additional computational time must be taken to correct the intermediate arcs in
the reversed subpath. Although the 2-level tree
reduces the time complexity of this correction, the satellite data structure
eliminates the problem. The data structure currently thought to be the
state-of-the-art, the 2-level tree, maintains for each level a doubly-linked
list. Therefore, it is a natural idea to use the satellite list to improve the
2-level tree for any algorithm that is thought to be most efficiently implemented
with this structure….
† In pointer-supporting languages, it is, in
fact, possible to obtain a direct reference for these members, but the
reference can only be used to indirectly retrieve values that can also be
stored directly, and so the reference is not meaningful
††Traveling
salesman problem.
If a salesman starts at point
A, and if the distances between any two points is
known, what is the shortest round-trip the salesman can make which will visit
all points once and return to point A?
The traveling salesman problem[1] (TSP) is a problem in discrete or combinatorial optimization. It is a
prominent illustration of a class of problems in computational complexity theory
which are hard to solve.
Problem statement
Given a number of cities and
the costs of traveling from any city to any other city, what is the cheapest
round-trip route that visits each city exactly once and then returns to the
starting city?
An equivalent formulation in
terms of graph theory is: Given a complete weighted graph (where the
vertices would represent the cities, the edges would represent the roads, and
the weights would be the cost or distance of that road), find a Hamiltonian
cycle with the least weight. It can be shown that the requirement of
returning to the starting city does not change the computational complexity of the problem.
The problem is of
considerable practical importance, apart from evident transportation and
logistics areas. A classic example is in printed
circuit manufacturing: scheduling of a route of the drill machine to drill
holes in a PCB. In robotic machining or drilling applications, the
"cities" are parts to machine or holes (of different sizes) to drill,
and the "cost of travel" includes time for retooling the robot
(single machine job sequencing problem