module algorithm.tsp

Short summary

module code_beatrix.algorithm.tsp

Function solving the TSP problem

source on GitHub

Functions

function truncated documentation
distance_circuit computes the distance of this circuit
distance_point returns the distance between two points
permutation switch two points and return a new path
plot_circuit plot the circuit on a graph
reverse reverse a sub part of circuit
voyageur_commerce_simple solves the TSP using basic permutations, points are 2D coordinates

Documentation

Function solving the TSP problem

source on GitHub

code_beatrix.algorithm.tsp.distance_circuit(points)[source]

computes the distance of this circuit

Paramètres:points – list of points, the circuit assumes they are giving in that order
Retourne:distance

source on GitHub

code_beatrix.algorithm.tsp.distance_point(p1, p2)[source]

returns the distance between two points

Paramètres:
  • p1 – point 1
  • p2 – point 2
Retourne:

distance

source on GitHub

code_beatrix.algorithm.tsp.permutation(points, i, j)[source]

switch two points and return a new path

Paramètres:
  • points – circuit
  • i – first index
  • j – second index (< len(points))
Retourne:

new circuit

source on GitHub

code_beatrix.algorithm.tsp.plot_circuit(points, ax=None, **kwargs)[source]

plot the circuit on a graph

Paramètres:
  • points – points
  • ax – axe
  • kwargs – sent to plt.subplots
Retourne:

ax

source on GitHub

code_beatrix.algorithm.tsp.reverse(points, i, j)[source]

reverse a sub part of circuit

Paramètres:
  • points – circuit
  • i – first index
  • j – second index (<= len(points))
Retourne:

new circuit

source on GitHub

code_beatrix.algorithm.tsp.voyageur_commerce_simple(points)[source]

solves the TSP using basic permutations, points are 2D coordinates

Paramètres:points – list of points

source on GitHub