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. Calcule la longueur d’un circuit.
distance_point Returns the Euclidian distance between two points. Retourne la distance euclidienne entre deux points.
permutation Switches two points and returns a new path. Echange deux points et retourne le nouveau circuit.
plot_circuit Plots the circuit on a graph. Dessine la solution du voyageur de commerce.
reverse Reverses a sub part of circuit. Retourne une partie du circuit.
voyageur_commerce_simple Solves the TSP using basic permutations, points are 2D coordinates. Résoud le problème du voyageur de commerce.

Documentation

Function solving the TSP problem

source on GitHub

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

Computes the distance of this circuit. Calcule la longueur d’un circuit.

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

source on GitHub

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

Returns the Euclidian distance between two points. Retourne la distance euclidienne entre deux points.

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

distance

source on GitHub

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

Switches two points and returns a new path. Echange deux points et retourne le nouveau circuit.

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

new circuit

source on GitHub

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

Plots the circuit on a graph. Dessine la solution du voyageur de commerce.

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

ax

source on GitHub

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

Reverses a sub part of circuit. Retourne une partie du circuit.

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

new circuit

source on GitHub

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

Solves the TSP using basic permutations, points are 2D coordinates. Résoud le problème du voyageur de commerce.

Paramètres:points – list of points

source on GitHub