["BayesicFitting"]

Global	Documentation
Home	Manual
Readme	Glossary
Notes	Design
Examples	Classes
	Trouble
	Style

class SalesmanProblem( OrderProblem )	Source

Traveling Salesman Problem.

The parameters give the order in which the nodes are visited.

The result is a list of distances.

[dist( x[p[k-1]], x[p[k]] ) for k in range( len( p ) )]

The number of parameters is equal to the length of the xdata array The parameters are initialized at [k for k in range( npars )]

Examples

tsm = SalesmanProblem( 100 )
print( tsm )
TravelingSalesman in 2 dimensions with 100 nodes.
print( tsm.npars )
100

SalesmanProblem( xdata=None, weights=None, distance="euclid", scale=None, table=None, oneway=False, copy=None )

Traveling Salesman problem.

Parameters

xdata : array_like of shape [np,ndim]
the nodes to be visited
weights : array_like
weights on the arrival nodes
distance : str or callable
     to calculate the distance between point1 and point2
     "manh" : Manhattan distance (1 norm) (2 or more dimensions)
     "euclid" : Euclidic (2 norm) (2 or more dimensions)
     "spher" : spherical, distance over sphere (2 dimensions only)
     "table" : tabulated distance values
     callable of the form callable( xdata, pars )
scale : None or float
scale all distances by this number.
None : take minimum distance as scale
table : arraylike or None
table of all distances, Only when distance is "tabulated"
oneway : bool
Don't close the loop; cut at position 0.
copy : SalesmanProblem
to be copied

copy( )

Copy method.

acceptWeight( )

True if the distribution accepts weights.

result( params )

Calculates the distance between the nodes (xdata) in the order given by the parameters (params), multiplied by the weight at the starting node (if present), divided by the scale

Each result is

res[k] = dis[k] * weight[params[k]] / scale

Parameters

params : array_like
values for the parameters.

Returns

An array of distances

manhattan( xdata, pars, roll=1 )

Use Manhattan distances (1-norm)

Each distance is

dis[k] = SUM_i ( abs( xdata[pars[k],i] - xdata[pars[k+roll],i] ) )

Parameters

xdata : array-like of shape (ndata,ndim)
positional info in several dimensions
pars : list of indices
designating the order of the nodess
roll : int
number of positions to roll

euclidic( xdata, pars, roll=1 )

Use Euclidic distances (2-norm)

Each distance is

dis[k] = sqrt( SUM_i ( ( xdata[pars[k],i] - xdata[pars[k+roll],i] )² ) )

Parameters

xdata : array-like of shape (ndata,ndim)
positional info in several dimensions
pars : list of indices
designating the order of the nodes
roll : int
number of positions to roll

spherical( xdata, pars, roll=1 )

Use distances over a 2-d unit sphere.

Each distance is calculated according to the Haversine formula.

It is assumed that the xdata is in decimal degrees: [longitude, latitude]

The results are in radian.

Parameters

xdata : array-like of shape (ndata,2)
longitude, latitude info
pars : list of indices
designating the order of the nodes
roll : int
number of positions to roll

tabulated( xdata, pars, roll=1 )

Use tabulated distances from self.table

Each distance is

dis[k] = table[ pars[k], pars[k+roll] ]

Parameters

xdata : array-like of shape (ndata,ndim)
positional info in several dimensions
pars : list of indices
designating the order of the nodess
roll : int
number of positions to roll

minimumDistance( )

Return the smallest distance in the data.

ndata = len( self.xdata[:,0] ) pars = numpy.arange( ndata, dtype=int ) md = self.distance( self.xdata, pars ).min() for roll in range( 2, ndata )
md = self.distance( self.xdata, pars, roll=roll ).min( initial=md )

return md

baseName( )

baseName( self ) return str( "TravelingSalesman in %d dimensions with %d nodes. %s distance" %
( self.ndim, self.npars, self.disname ) )

Methods inherited from OrderProblem

Methods inherited from Problem