teachpyx.practice.tsp_kruskal

teachpyx.practice.tsp_kruskal.amelioration_chemin(chemin: List[Tuple[float, float]], taille_zone: int, X: float, Y: float, taille: int = 10, max_iter: int | None = None, distance: Callable[[Tuple[float, float], Tuple[float, float]], float] | None = None, verbose: int = 0)

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.

teachpyx.practice.tsp_kruskal.arbre_poids_minimal(villes: List[Tuple[float, float]], zone_taille: float, distance: Callable[[Tuple[float, float], Tuple[float, float]], float]) → Dict[str, Any]

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 – see 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

teachpyx.practice.tsp_kruskal.circuit_eulerien(villes: List[Tuple[float, float]], arbre: List[List[int]], verbose: int = 0) → List[int]

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.

teachpyx.practice.tsp_kruskal.circuit_hamiltonien(chemin: List[int]) → List[int]

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

teachpyx.practice.tsp_kruskal.construit_ville(n: int, x: int = 1000, y: int = 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.

teachpyx.practice.tsp_kruskal.dessin_arete_zone(chemin: List[Tuple[float, float]], taille_zone: float, X: Tuple[float, float], Y: Tuple[float, float]) → List[List[List[int]]]

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.

teachpyx.practice.tsp_kruskal.distance_euclidian(p1: float, p2: float) → float

Calcule la distance euclienne entre deux villes.

teachpyx.practice.tsp_kruskal.echange_position(chemin: List[Tuple[float, float]], taille: float, taille_zone: float, X: float, Y: float, grande: float = 0.5, distance: Callable[[Tuple[float, float], Tuple[float, float]], float] | None = None, verbose: int = 0) → int

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.

teachpyx.practice.tsp_kruskal.echange_position_essai(chemin: List[Tuple[float, float]], a: int, b: int, x: float, inversion: bool, negligeable: float = 1e-05, distance: Callable[[Tuple[float, float], Tuple[float, float]], float] | None = None) → bool

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.

teachpyx.practice.tsp_kruskal.equation_droite(p1: Tuple[float, float], p2: Tuple[float, float]) → Tuple[float, float, float]

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

teachpyx.practice.tsp_kruskal.evaluation_droite(a: float, b: float, c: float, p: Tuple[float, float]) → float

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

teachpyx.practice.tsp_kruskal.intersection_segment(p1: Tuple[float, float], p2: Tuple[float, float], p3: Tuple[float, float], p4: Tuple[float, float]) → bool

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

teachpyx.practice.tsp_kruskal.longueur_chemin(chemin: List[Tuple[float, float]], distance: Callable[[Tuple[float, float], Tuple[float, float]], float]) → float

Retourne la longueur d’un chemin.

teachpyx.practice.tsp_kruskal.oppose_vecteur(vec: Tuple[float, float]) → Tuple[float, float]

retourne le vecteur opposé.

teachpyx.practice.tsp_kruskal.repartition_zone(villes: List[Tuple[float, float]], zone_taille: float, ask_zone: bool = False) → Tuple[Tuple[int, Tuple[float, float], Tuple[int, int], int], Tuple[float, float], float, float, float]

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.

teachpyx.practice.tsp_kruskal.retournement(chemin: List[Tuple[float, float]], taille: float, distance: Callable[[Tuple[float, float], Tuple[float, float]], float], verbose: int) → int

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

teachpyx.practice.tsp_kruskal.retournement_essai(chemin: List[Tuple[float, float]], i: int, j: int, negligeable: float = 1e-05, distance: Callable[[Tuple[float, float], Tuple[float, float]], float] | None = None) → bool

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.

teachpyx.practice.tsp_kruskal.simulation(points: List[Tuple[float, float]] | None = None, size: Tuple[int, int] = (800, 500), zone: int = 20, length: int = 10, max_iter: int | None = None, nb: int = 700, distance: Callable[[Tuple[float, float], Tuple[float, float]], float] | None = None, verbose: int = 0) → Tuple[List[Tuple[float, float]], List[Tuple[float, float]]]

Implémente la recherche du court chemin passant par tous les noeuds d’un graphe en partant d’une simplification avec l’algorithme de Kruskal.

Paramètres:

• points – ensemble de points

• size – taille de l’écran

• zone –

  …

• length –

  …

• max_iter – maximum number of iteration

• nb – number of cities

• distance – distance function

Renvoie:

see tsp_kruskal_algorithm

teachpyx.practice.tsp_kruskal.supprime_croisement(chemin: List[Tuple[float, float]], taille_zone: float, X: float, Y: float, distance: Callable[[Tuple[float, float], Tuple[float, float]], float] | None = None, verbose: int = 0) → int

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

teachpyx.practice.tsp_kruskal.tsp_kruskal_algorithm(points: List[Tuple[float, float]], size: int = 20, length: int = 10, max_iter: int | None = None, distance: Callable[[Tuple[float, float], Tuple[float, float]], float] | None = None, verbose: int = 0) → List[Tuple[float, float]]

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

• 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.

teachpyx.practice.tsp_kruskal.vecteur_cosinus(vec1: Tuple[float, float], vec2: Tuple[float, float]) → float

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

teachpyx.practice.tsp_kruskal.vecteur_norme(vec: Tuple[float, float]) → float

Retourne la norme d’un vecteur.

teachpyx.practice.tsp_kruskal.vecteur_points(p1: float, p2: float) → Tuple[float, float]

Retourne le vecteur entre les points p1 et p2.

teachpyx.practice.tsp_kruskal.vecteur_sinus(vec1: Tuple[float, float], vec2: Tuple[float, float]) → float

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

teachpyx.practice.tsp_kruskal.voisinage_zone(z: float, Zmax: float, X: float, Y: float) → List[int]

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.

teachpyx.practice.tsp_kruskal.voisinage_zone_xy(x: float, y: float, X: float, Y: float) → List[Tuple[float, float]]

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