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()
.
Functions#
function |
truncated documentation |
---|---|
Amélioration du chemin par un algorithme simple, utilise des retournements de taille au plus taille, traite les … |
|
Construit l’arbre de poids minimal, retourne une liste de listes, chaque sous-liste associée à une ville contient la … |
|
Définit un circuit eulérien, villes contient la liste des villes, tandis que arbre est une liste de listes, |
|
Extrait un circuit hamiltonien depuis un circuit eulérien, passe par tous les sommets une et une seule fois. |
|
Tire aléatoirement n villes dans un carrée |
|
Retourne une liste de listes de listes, |
|
dessine le graphe de poids minimal dꧩni par arbre |
|
dessine le chemin à l’écran |
|
dessine les villes à l’écran |
|
Calcule la distance entre deux villes. |
|
Regarde si on ne peut pas déplacer un segment de longueur taille pour supprimer les arêtes les plus longues, au … |
|
Echange la place des villes ka et kb pour les placer entre les villes i et i+1, si inversion est True, on inverse … |
|
retourne l’équation d’une droite passant par p1 et p2, ax + by + c = 0, retourne les coefficients a,b,c |
|
L’équation d’une droite est : |
|
Dit si les segments [p1 p2] et [p3 p4] ont une intersection, ne retourne pas l’intersection. |
|
Retourne la longueur d’un chemin. |
|
retourne le vecteur opposé. |
|
Répartit les villes en zones, retourne les villes rangées par zones, chaque éléments zones [z][k] contient : |
|
Amélioration du chemin par un algorithme simple, utilise des retournements de taille au plus <taille>, retourne … |
|
Dit s’il est judicieux de parcourir le chemin entre les sommets i et j en sens inverse, si c’est judicieux, change … |
|
Supprime les croisements d’arêtes, retourne le nombre de changement effectués, X est le nombre de zones horizontalement, … |
|
Finds the shortest path going through all points, points require to be a 2 dimensional space. |
|
Retourne le cosinus entre deux vecteurs, utilise le produit scalaire. |
|
Retourne la norme d’un vecteur. |
|
Retourne le vecteur entre les points p1 et p2. |
|
Retourne le sinus entre deux vecteurs, utilise le produit vectoriel. |
|
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 … |
|
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
.
- 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.
- 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_taille –
repartition_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
- 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.
- 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.
- 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.
- 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 inres[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.
- 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
- ensae_teaching_cs.special.tsp_kruskal.display_chemin(neurones, bn, screen, pygame)#
dessine le chemin à l’écran
- ensae_teaching_cs.special.tsp_kruskal.display_ville(villes, screen, bv, pygame)#
dessine les villes à l’écran
- ensae_teaching_cs.special.tsp_kruskal.distance_euclidian(p1, p2)#
Calcule la distance entre deux villes.
- 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.
- 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.
- 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
- 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.
- 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.
- ensae_teaching_cs.special.tsp_kruskal.longueur_chemin(chemin, distance)#
Retourne la longueur d’un chemin.
- ensae_teaching_cs.special.tsp_kruskal.oppose_vecteur(vec)#
retourne le vecteur opposé.
- 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:
La simulation ressemble à ceci :
Pour lancer la simulation:
from ensae_teaching_cs.special.tsp_kruskal import pygame_simulation import pygame pygame_simulation(pygame)
- 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.
- 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.
- 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.
- 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
- 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.
- ensae_teaching_cs.special.tsp_kruskal.vecteur_cosinus(vec1, vec2)#
Retourne le cosinus entre deux vecteurs, utilise le produit scalaire.
- ensae_teaching_cs.special.tsp_kruskal.vecteur_norme(vec)#
Retourne la norme d’un vecteur.
- ensae_teaching_cs.special.tsp_kruskal.vecteur_points(p1, p2)#
Retourne le vecteur entre les points p1 et p2.
- ensae_teaching_cs.special.tsp_kruskal.vecteur_sinus(vec1, vec2)#
Retourne le sinus entre deux vecteurs, utilise le produit vectoriel.
- 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.
- 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