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

Inheritance diagram for Satsuma.InsertionTsp< 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(n²).

Template Parameters

TNode The 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:

src/Tsp.cs

Public Member Functions

Properties

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Property Documentation