Pre-requisites:
Degree-Constrained Kruskal's algorithm (see for description
of Degree-Constrained Kruskal's. This algorithm uses it in its construction phases).
For a full description of this algorithm, see the
original paper here.
PACO (Parallel Ant Colony Optimisation for DCMST) is a algorithm that consits of ant agents.
In the exploration phase, the ants traverse the graph in parallel and at
random, but proportional to the phermone levels. Updates are then made
to the edge pheromones based on how many times it was traversed.
In the construction phase, the highest pheromone edges are taken and sorted
by their weights in ascending order, where Degree-Constrained Kruskal's is then applied, to
attemp to try and find a DCMST. If found, the best tree is saved.
The algorithm consists of many cycles, each one having an exploration and construction phase.
Every time a spanning tree is built in the construction phase, it is compared with the best
tree found so far, and replaces it if it has a lower cost. In the end, the algorithm should
return a good DCMST solution.
See an example below with a node degree constraint = 2, and we will be tracking ants starting
on nodes b, o, t, and h.