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.InsertionTsp< TNode > Class Template Reference

Solves the traveling salesman problem by using the insertion heuristic. More...

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

Public Member Functions

void Clear ()
 Reverts the tour to a one-node tour, or a null tour if no node is available. More...
 
bool Insert (TNode node)
 Inserts a given node into the current tour at the optimal place. More...
 
bool Insert ()
 Inserts a new node into the tour according to SelectionRule. More...
 
 InsertionTsp (IEnumerable< TNode > nodes, Func< TNode, TNode, double > cost, TspSelectionRule selectionRule=TspSelectionRule.Farthest)
 
void Run ()
 Completes the tour. More...
 

Properties

Func< TNode, TNode, double > Cost [get, set]
 A finite cost function on the node pairs. More...
 
IEnumerable< TNode > Nodes [get, set]
 The nodes the salesman has to visit. More...
 
TspSelectionRule SelectionRule [get, set]
 The method of selecting new nodes for insertion. More...
 
IEnumerable< TNode > Tour [get]
 See ITsp<TNode>.Tour. More...
 
double TourCost [get, set]
 

Detailed Description

Solves the traveling salesman problem by using the insertion heuristic.

It starts from a small tour and gradually extends it by repeatedly choosing a yet unvisited node. The selected node is then inserted into the tour at the optimal place. Running time: O(n2).

Template Parameters
TNodeThe node type.

Definition at line 148 of file Tsp.cs.

Constructor & Destructor Documentation

Satsuma.InsertionTsp< TNode >.InsertionTsp ( IEnumerable< TNode >  nodes,
Func< TNode, TNode, double >  cost,
TspSelectionRule  selectionRule = TspSelectionRule.Farthest 
)

Definition at line 172 of file Tsp.cs.

Member Function Documentation

void Satsuma.InsertionTsp< TNode >.Clear ( )

Reverts the tour to a one-node tour, or a null tour if no node is available.

Definition at line 197 of file Tsp.cs.

bool Satsuma.InsertionTsp< TNode >.Insert ( TNode  node)

Inserts a given node into the current tour at the optimal place.

Returns
true if the node was inserted, false if it was already in the tour

Definition at line 221 of file Tsp.cs.

bool Satsuma.InsertionTsp< TNode >.Insert ( )

Inserts a new node into the tour according to SelectionRule.

Returns
true if a new node was inserted, or false if the tour was already full.

Definition at line 257 of file Tsp.cs.

void Satsuma.InsertionTsp< TNode >.Run ( )

Completes the tour.

Definition at line 265 of file Tsp.cs.

Property Documentation

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

A finite cost function on the node pairs.

Definition at line 153 of file Tsp.cs.

IEnumerable<TNode> Satsuma.InsertionTsp< TNode >.Nodes
getset

The nodes the salesman has to visit.

Definition at line 151 of file Tsp.cs.

TspSelectionRule Satsuma.InsertionTsp< TNode >.SelectionRule
getset

The method of selecting new nodes for insertion.

Definition at line 155 of file Tsp.cs.

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

See ITsp<TNode>.Tour.

Note
The current tour contains only a subset of the nodes in the middle of the execution of the algorithm, since the insertion TSP algorithm works by gradually extending a small tour.

Definition at line 169 of file Tsp.cs.

double Satsuma.InsertionTsp< TNode >.TourCost
getset

Definition at line 170 of file Tsp.cs.


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