.. _f-tspkruskal: 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 :ref:`l-tsp_kruskal`. La fonction principale est :func:`tsp_kruskal_algorithm`. :githublink:`%|py|10` Functions +++++++++ +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | function | truncated documentation | +===============================================================================================+================================================================================================================================+ | :func:`amelioration_chemin ` | Amélioration du chemin par un algorithme simple, utilise des retournements de taille au plus *taille*, traite les ... | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`arbre_poids_minimal ` | Construit l'arbre de poids minimal, retourne une liste de listes, chaque sous-liste associée à une ville contient la ... | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`circuit_eulerien ` | Définit un circuit eulérien, villes contient la liste des villes, tandis que arbre est une liste de listes, ``arbre[i]`` ... | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`circuit_hamiltonien ` | Extrait un circuit hamiltonien depuis un circuit eulérien, passe par tous les sommets une et une seule fois. | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`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 ... | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`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]``, ... | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`display_arbre ` | dessine le graphe de poids minimal dꧩni par arbre | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`display_chemin ` | dessine le chemin à l'écran | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`display_ville ` | dessine les villes à l'écran | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`distance_euclidian ` | Calcule la distance entre deux villes. | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`echange_position ` | Regarde si on ne peut pas déplacer un segment de longueur taille pour supprimer les arêtes les plus longues, au ... | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`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 ... | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`equation_droite ` | retourne l'équation d'une droite passant par p1 et p2, ax + by + c = 0, retourne les coefficients a,b,c | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`evaluation_droite ` | L'équation d'une droite est : ``ax + by + c``, retourne la valeur de cette expression au point *p*. | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`intersection_segment ` | Dit si les segments *[p1 p2]* et *[p3 p4]* ont une intersection, ne retourne pas l'intersection. | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`longueur_chemin ` | Retourne la longueur d'un chemin. | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`oppose_vecteur ` | retourne le vecteur opposé. | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`pygame_simulation ` | | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`repartition_zone ` | Répartit les villes en zones, retourne les villes rangées par zones, chaque éléments zones [z][k] contient : | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`retournement ` | Amélioration du chemin par un algorithme simple, utilise des retournements de taille au plus , retourne ... | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`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 ... | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`supprime_croisement ` | Supprime les croisements d'arêtes, retourne le nombre de changement effectués, *X* est le nombre de zones horizontalement, ... | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`tsp_kruskal_algorithm ` | Finds the shortest path going through all points, points require to be a 2 dimensional space. | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`vecteur_cosinus ` | Retourne le cosinus entre deux vecteurs, utilise le produit scalaire. | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`vecteur_norme ` | Retourne la norme d'un vecteur. | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`vecteur_points ` | Retourne le vecteur entre les points *p1* et *p2*. | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`vecteur_sinus ` | Retourne le sinus entre deux vecteurs, utilise le produit vectoriel. | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`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 ... | +-----------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------+ | :func:`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 +++++++++++++ .. automodule:: ensae_teaching_cs.special.tsp_kruskal :members: :special-members: __init__ :show-inheritance: