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)

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)

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)

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)

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)

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)

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