module special.tsp_kruskal#

Short summary#

module ensae_teaching_cs.special.tsp_kruskal

Implémente un algorithme qui cherche le plus court chemin passant par tous les noeuds d’un graphe (TSP). Applique un algorithme de Kruskal puis cherche à améliorer le chemin localement. Voir Circuit hamiltonien et Kruskal. La fonction principale est tsp_kruskal_algorithm().

source on GitHub

Functions#

function

truncated documentation

amelioration_chemin

Amélioration du chemin par un algorithme simple, utilise des retournements de taille au plus taille, traite les …

arbre_poids_minimal

Construit l’arbre de poids minimal, retourne une liste de listes, chaque sous-liste associée à une ville contient la …

circuit_eulerien

Définit un circuit eulérien, villes contient la liste des villes, tandis que arbre est une liste de listes, arbre[i]

circuit_hamiltonien

Extrait un circuit hamiltonien depuis un circuit eulérien, passe par tous les sommets une et une seule fois.

construit_ville

Tire aléatoirement n villes dans un carrée x * y, on choisit ces villes de sortent qu’elles ne soient pas trop …

dessin_arete_zone

Retourne une liste de listes de listes, res[i][j] est une liste des arêtes passant près de la zone (x,y) = [i][j], …

display_arbre

dessine le graphe de poids minimal dꧩni par arbre

display_chemin

dessine le chemin à l’écran

display_ville

dessine les villes à l’écran

distance_euclidian

Calcule la distance entre deux villes.

echange_position

Regarde si on ne peut pas déplacer un segment de longueur taille pour supprimer les arêtes les plus longues, au …

echange_position_essai

Echange la place des villes ka et kb pour les placer entre les villes i et i+1, si inversion est True, on inverse …

equation_droite

retourne l’équation d’une droite passant par p1 et p2, ax + by + c = 0, retourne les coefficients a,b,c

evaluation_droite

L’équation d’une droite est : ax + by + c, retourne la valeur de cette expression au point p.

intersection_segment

Dit si les segments [p1 p2] et [p3 p4] ont une intersection, ne retourne pas l’intersection.

longueur_chemin

Retourne la longueur d’un chemin.

oppose_vecteur

retourne le vecteur opposé.

pygame_simulation

repartition_zone

Répartit les villes en zones, retourne les villes rangées par zones, chaque éléments zones [z][k] contient :

retournement

Amélioration du chemin par un algorithme simple, utilise des retournements de taille au plus <taille>, retourne …

retournement_essai

Dit s’il est judicieux de parcourir le chemin entre les sommets i et j en sens inverse, si c’est judicieux, change …

supprime_croisement

Supprime les croisements d’arêtes, retourne le nombre de changement effectués, X est le nombre de zones horizontalement, …

tsp_kruskal_algorithm

Finds the shortest path going through all points, points require to be a 2 dimensional space.

vecteur_cosinus

Retourne le cosinus entre deux vecteurs, utilise le produit scalaire.

vecteur_norme

Retourne la norme d’un vecteur.

vecteur_points

Retourne le vecteur entre les points p1 et p2.

vecteur_sinus

Retourne le sinus entre deux vecteurs, utilise le produit vectoriel.

voisinage_zone

Retourne la liste des voisins d’une zone z sachant qu’il y a X zones sur l’axe des abscisses et Y zones sur …

voisinage_zone_xy

Retourne la liste des voisins d’une zone (x,y) sachant qu’il y a X zones sur l’axe des abscisses et Y zones …

Documentation#

Implémente un algorithme qui cherche le plus court chemin passant par tous les noeuds d’un graphe (TSP). Applique un algorithme de Kruskal puis cherche à améliorer le chemin localement. Voir Circuit hamiltonien et Kruskal. La fonction principale est tsp_kruskal_algorithm.

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.amelioration_chemin(chemin, taille_zone, X, Y, taille=10, screen=None, fLOG=None, pygame=None, max_iter=None, images=None, distance=None)#

Amélioration du chemin par un algorithme simple, utilise des retournements de taille au plus taille, traite les arcs qui se croisent, traite les grands arcs, utilise un quadrillage de taille window, X est le nombre de zones horizontalement, Y est le nombre de zones verticalement, taille_zone est la longueur d’un côté du carré d’une zone.

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.arbre_poids_minimal(villes, zone_taille, distance)#

Construit l’arbre de poids minimal, retourne une liste de listes, chaque sous-liste associée à une ville contient la liste des ses voisins, zone_taille permet de découper l’image en zones, les distances ne seront calculées que si deux éléments sont dans la même zone ou dans une zone voisine.

Paramètres:
  • villes – list of tuples (tuple = coordinates)

  • zone_taillerepartition_zone

  • distance – distance function which returns the distance between two elements

Renvoie:

list of lists: each sublist r[i] contains the indexes of neighbors of node i so that the whole graph is only one connected component

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.circuit_eulerien(villes, arbre, screen, pygame, fLOG)#

Définit un circuit eulérien, villes contient la liste des villes, tandis que arbre est une liste de listes, arbre[i] est la liste des villes connectées à la ville i, on suppose que arbre est un graphe de poids minimal non orienté, l’algorithme ne marche pas s’il existe des villes confondues, un circuit eulérien passe par tous les arêtes une et une seule fois.

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.circuit_hamiltonien(chemin)#

Extrait un circuit hamiltonien depuis un circuit eulérien, passe par tous les sommets une et une seule fois.

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.construit_ville(n, x=1000, y=700)#

Tire aléatoirement n villes dans un carrée x * y, on choisit ces villes de sortent qu’elles ne soient pas trop proches.

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.dessin_arete_zone(chemin, taille_zone, X, Y)#

Retourne une liste de listes de listes, res[i][j] est une liste des arêtes passant près de la zone (x,y) = [i][j], si k in res[i][j], alors l’arête k, k+1 est dans la zone (i,j), X est le nombre de zones horizontalement, Y est le nombre de zones verticalement, taille_zone est la longueur du côté du carré d’une zone.

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.display_arbre(villes, arbre, mult=1, screen=None, pygame=None)#

dessine le graphe de poids minimal dꧩni par arbre

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.display_chemin(neurones, bn, screen, pygame)#

dessine le chemin à l’écran

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.display_ville(villes, screen, bv, pygame)#

dessine les villes à l’écran

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.distance_euclidian(p1, p2)#

Calcule la distance entre deux villes.

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.echange_position(chemin, taille, taille_zone, X, Y, grande=0.5, fLOG=None, distance=None)#

Regarde si on ne peut pas déplacer un segment de longueur taille pour supprimer les arêtes les plus longues, au maximum <grande> longues arêtes, retourne le nombre de changement effectués, X est le nombre de zones horizontalement, Y est le nombre de zones verticalement, taille_zone est la longueur d’un côté du carré d’une zone.

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.echange_position_essai(chemin, a, b, x, inversion, negligeable=1e-05, distance=None)#

Echange la place des villes ka et kb pour les placer entre les villes i et i+1, si inversion est True, on inverse également le chemin inséré, si inversion est False, on ne l’inverse pas, si cela améliore, déplace les villes et retourne True, sinon, retourne False.

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.equation_droite(p1, p2)#

retourne l’équation d’une droite passant par p1 et p2, ax + by + c = 0, retourne les coefficients a,b,c

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.evaluation_droite(a, b, c, p)#

L’équation d’une droite est : ax + by + c, retourne la valeur de cette expression au point p.

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.intersection_segment(p1, p2, p3, p4)#

Dit si les segments [p1 p2] et [p3 p4] ont une intersection, ne retourne pas l’intersection.

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.longueur_chemin(chemin, distance)#

Retourne la longueur d’un chemin.

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.oppose_vecteur(vec)#

retourne le vecteur opposé.

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.pygame_simulation(size=(800, 500), zone=20, length=10, max_iter=None, nb=700, fLOG=<function noLOG>, pygame=None, folder=None, first_click=False, distance=None, flags=0)#
Paramètres:
  • pygame – module pygame

  • nb – number of cities

  • first_click – attend la pression d’un clic de souris avant de commencer

  • folder – répertoire où stocker les images de la simulation

  • size – taille de l’écran

  • delay – delay between two tries

  • folder – folder where to save images

  • first_click – pause

  • fLOG – logging function

  • distance – distance function

  • flags – see pygame.display.set_mode

Renvoie:

tsp_kruskal_algorithm

La simulation ressemble à ceci :

Pour lancer la simulation:

from ensae_teaching_cs.special.tsp_kruskal import pygame_simulation
import pygame
pygame_simulation(pygame)

Voir Circuit hamiltonien et Kruskal.

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.repartition_zone(villes, zone_taille, ask_zone=False)#

Répartit les villes en zones, retourne les villes rangées par zones, chaque éléments zones [z][k] contient :

  • les coordonnées de la ville

  • ses coordonnées en zone, (zx, zy)

  • son indice dans la liste villes

La fonction retourne également le nombre de zones selon l’axe des abscisses et l’axe des ordonnées, retourne aussi le nombre de zones, si ask_zone est True, retourne un paramètre supplémentaire : zone.

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.retournement(chemin, taille, fLOG, distance)#

Amélioration du chemin par un algorithme simple, utilise des retournements de taille au plus <taille>, retourne le nombre de modifications.

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.retournement_essai(chemin, i, j, negligeable=1e-05, distance=None)#

Dit s’il est judicieux de parcourir le chemin entre les sommets i et j en sens inverse, si c’est judicieux, change le chemin et retourne True, sinon, retourne False, si j < i, alors la partie à inverser est i, i+1, i+2, …, len(chemin), -1, 0, 1, …, j.

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.supprime_croisement(chemin, taille_zone, X, Y, fLOG, distance=None)#

Supprime les croisements d’arêtes, retourne le nombre de changement effectués, X est le nombre de zones horizontalement, Y est le nombre de zones verticalement, taille_zone est la longueur d’un côté du carré d’une zone

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.tsp_kruskal_algorithm(points, size=20, length=10, max_iter=None, fLOG=<function noLOG>, pygame=None, screen=None, images=None, distance=None)#

Finds the shortest path going through all points, points require to be a 2 dimensional space.

Paramètres:
  • points – list 2-tuple (X,Y)

  • size – the 2D plan is split into square zones

  • length – sub path

  • max_iter – max number of iterations

  • pygame – pygame for simulation

  • screen – with pygame

  • fLOG – logging function

  • images – save intermediate images

  • distance – distance function

Renvoie:

path

The distance is a function which takes two tuples and returns a distance:

def distance(p1, p2):
    # ...
    return d

Les points identiques sont enlevés puis ajoutés à la fin.

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.vecteur_cosinus(vec1, vec2)#

Retourne le cosinus entre deux vecteurs, utilise le produit scalaire.

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.vecteur_norme(vec)#

Retourne la norme d’un vecteur.

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.vecteur_points(p1, p2)#

Retourne le vecteur entre les points p1 et p2.

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.vecteur_sinus(vec1, vec2)#

Retourne le sinus entre deux vecteurs, utilise le produit vectoriel.

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.voisinage_zone(z, Zmax, X, Y)#

Retourne la liste des voisins d’une zone z sachant qu’il y a X zones sur l’axe des abscisses et Y zones sur l’axe des ordonnées, Zmax est le nombre de zones, inclus z dans cette liste.

source on GitHub

ensae_teaching_cs.special.tsp_kruskal.voisinage_zone_xy(x, y, X, Y)#

Retourne la liste des voisins d’une zone (x,y) sachant qu’il y a X zones sur l’axe des abscisses et Y zones sur l’axe des ordonnées, inclus z dans cette liste

source on GitHub