![]() |
Satsuma
a delicious .NET graph library
|
Solves the symmetric traveling salesman problem by using the cheapest link heuristic. More...
Public Member Functions | |
CheapestLinkTsp (IList< TNode > nodes, Func< TNode, TNode, double > cost) | |
Properties | |
Func< TNode, TNode, double > | Cost [get, set] |
A finite cost function on the node pairs. Must be symmetric, or at least close to symmetric. More... | |
IList< TNode > | Nodes [get, set] |
The nodes the salesman has to visit. More... | |
IEnumerable< TNode > | Tour [get] |
double | TourCost [get, set] |
Solves the symmetric traveling salesman problem by using the cheapest link heuristic.
Works in a way very similar to Kruskal's algorithm. It maintains a forest as well, but this time the forest consists of paths only. In each step, it tries to glue two paths together, by using the cheapest possible link.
Running time: O(n2 log n), memory usage: O(n2); where n is the number of nodes.
Satsuma.CheapestLinkTsp< TNode >.CheapestLinkTsp | ( | IList< TNode > | nodes, |
Func< TNode, TNode, double > | cost | ||
) |
|
getset |
|
getset |