teachpyx.video.tsp_kruskal_pygame

teachpyx.video.tsp_kruskal_pygame.amelioration_chemin(chemin: List[Tuple[float, float]], taille_zone: float, X: float, Y: float, taille: int = 10, screen=None, pygame=None, max_iter: int | None = None, images=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.video.tsp_kruskal_pygame.circuit_eulerien(villes: List[Tuple[float, float]], arbre: List[List[int]], screen, pygame, verbose: 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.video.tsp_kruskal_pygame.display_arbre(villes, arbre, mult=1, screen=None, pygame=None)

Dessine le graphe de poids minimal dꧩni par arbre.

teachpyx.video.tsp_kruskal_pygame.display_chemin(neurones, bn, screen, pygame)

Dessine le chemin à l’écran.

teachpyx.video.tsp_kruskal_pygame.display_ville(villes, screen, bv, pygame)

Dessine les villes à l’écran.

teachpyx.video.tsp_kruskal_pygame.pygame_simulation(size: Tuple[int, int] = (800, 500), zone: int = 20, length: int = 10, max_iter: int | None = None, nb: int = 700, pygame=None, folder=None, first_click: bool = False, distance=None, flags=0, verbose: int = 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

• distance – distance function

• flags – see pygame.display.set_mode

• verbose – verbosity

Renvoie:

see tsp_kruskal_algorithm

La simulation ressemble à ceci :

Pour lancer la simulation:

import pygame
from teachpyx.video.tsp_kruskal_pygame import pygame_simulation
pygame_simulation(pygame)

Voir Circuit hamiltonien et Kruskal.

teachpyx.video.tsp_kruskal_pygame.tsp_kruskal_algorithm(points: List[Tuple[float, float]], size: int = 20, length: int = 10, max_iter: int | None = None, pygame=None, screen=None, images=None, distance: Callable[[Tuple[float, float], Tuple[float, float]], float] | None = None, verbose: int = 0)

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

• images – save intermediate images

• distance – distance function

• verbose – veerbosity

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.