## 4 Algorithm
### Discrete Particle Swarm Optimization
#### 4.2.1 Representation of Particles  
Due to robustness of the PSO algorithm, it does not demand rigorous representation of particles. A good representation can not only reduce the redundancy of the search space, but also improve the search efficiency, and thereby enhance the performance of the algorithm. Generally speaking, the selection of particle representation should comprehensively consider the following three main principles: non-redundancy, completeness and soundness. **Definition 1** (Non-redundancy): _A one-to-one relationship between the particles in the encoding space and the potential solution in the problem space._  
**Definition 2** (Completeness): _Each point in the problem space (feasible solution) can become the phenotype of points in the particles' encoding space._  
**Definition 3** (Soundness): _Each particle in the encoding space must correspond to a potential solution in the problem space._  
It is well known that it is difficult for an encoding scheme to meet all three principles above. In this paper, as our target is to construct an efficient routing tree structure, we adopt the Prufer sequence in [34] to represent a labeled tree \(T\) whose vertexes are numbered from 1 to \(n\). We can easily construct the Prufer sequence according to the following procedure:  
_Procedure: Encoding_  
Step 1: Let \(j\) be the smallest labeled leaf vertex in the \(T\). Step 2: Set \(k\) to be the first digit in the Prufer sequence if \(k\) is incident to \(j\). Step 3: Remove \(j\) and the edge which connects \(j\) and \(k\) from \(T\). Step 4: Repeat above steps until only one edge is left and produce the Prufer sequence in order. _Procedure: Decoding_  
Step 1: Let \(P\) be a Prufer sequence and \(Q\) be the set of all vertexes not included in \(P\). Step 2: Let \(j\) be the vertex with smallest label in \(Q\) and \(k\) be the leftmost digit in \(P\). Add the edge connecting \(j\) and \(k\) into the tree. Remove \(j\) from \(Q\) and \(k\) from \(P\). If \(k\) does not occur anywhere in \(Q\), put it into \(Q\). Step 3: Repeat above steps till no digit is left in \(P\). Step 4: If no digits remain in \(P\), there are exactly two vertexes in \(Q\). Add the edge connecting remaining vertexes into the tree. An example is given to illustrate above encoding and decoding procedures. The Prufer sequence corresponds to a tree on an 8-vertex complete graph which can be seen in Figure 2.  
Figure 2: A tree and its Prufer sequence. _Properties_: The Prufer sequence that represents a spanning tree of a complete graph can satisfy the principles of non-redundancy and completeness, but does not meet the principle of soundness. _Proof_: Assuming that \(T\) represents a spanning tree of an \(n\)-vertex complete graph and \(A\) represents a non-leaf node of \(T\). Since \(A\) is at least connected with two different nodes, the label of \(A\) must have appeared in the corresponding Prufer sequence when only one edge remains in the \(T\). In reverse, the numbers, which appear in the Prufer sequence finally, are obviously not the leaf nodes of \(T\), while the other numbers are the leaf nodes of \(T\). Assuming that \(B\) represents the smallest number which has not appeared in the Prufer sequence, thus \(B\) is the leaf node which is incident to leftmost labeled vertex in the Prufer sequence. Then, we recursively consider following \(n\)-3 numbers and connect the remaining two vertexes finally. As the number of nodes not processed the rest of the code length by 2, we can always find out a smallest number which has not appeared in the remaining number of coding. Thus, any Prufer sequence can uniquely correspond to an unrooted tree. So the Prufer sequence can satisfy the principle of non-redundancy. One of the classical theorems in graphical enumeration is [PERSON]'s theorem which states that there are \(n(n\)-\(2)\) distinct labeled trees for a complete graph with \(n\) vertices.