Satsuma
a delicious .NET graph library
 All Classes Namespaces Files Functions Variables Enumerations Enumerator Properties Pages
Public Member Functions | Properties | List of all members
Satsuma.CheapestLinkTsp< TNode > Class Template Reference

Solves the symmetric traveling salesman problem by using the cheapest link heuristic. More...

Inheritance diagram for Satsuma.CheapestLinkTsp< TNode >:
Satsuma.ITsp< TNode >

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]
 

Detailed Description

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.

Definition at line 71 of file Tsp.cs.

Constructor & Destructor Documentation

Satsuma.CheapestLinkTsp< TNode >.CheapestLinkTsp ( IList< TNode >  nodes,
Func< TNode, TNode, double >  cost 
)

Definition at line 83 of file Tsp.cs.

Property Documentation

Func<TNode, TNode, double> Satsuma.CheapestLinkTsp< TNode >.Cost
getset

A finite cost function on the node pairs. Must be symmetric, or at least close to symmetric.

Definition at line 77 of file Tsp.cs.

IList<TNode> Satsuma.CheapestLinkTsp< TNode >.Nodes
getset

The nodes the salesman has to visit.

If your original node collection is not an IList, you can convert it to a list using Enumerable.ToList.

Definition at line 75 of file Tsp.cs.

IEnumerable<TNode> Satsuma.CheapestLinkTsp< TNode >.Tour
get

Definition at line 80 of file Tsp.cs.

double Satsuma.CheapestLinkTsp< TNode >.TourCost
getset

Definition at line 81 of file Tsp.cs.


The documentation for this class was generated from the following file: