Test python fourmi.py

import numpy as np
import random
import math
import functools

from ant_colony_commente import AntColony

def construit_ville(n, x=1000, y=700):
    """
    Tire aléatoirement *n* villes dans un carré ``x * y``,
    on choisit ces villes de sorte quelles ne soient pas trop proches.
    """
    #deux villes ne pourront pas être plus proches que mind
    mind = math.sqrt(x * x + y * y) / (n * 0.75)
    # liste vide
    lt = []
    while n > 0:
        #on tire aléatoirement les coordonnées d'une ville
        xx = x * random.random()
        yy = y * random.random()
        #on vérifie qu'elle n'est pas trop proche d'aucune autre ville
        ajout = True
        for t in lt:
            d1 = t[0] - xx
            d2 = t[1] - yy
            d = math.sqrt(d1 * d1 + d2 * d2)
            if d < mind:
                ajout = False  # ville trop proche
        #si la ville n'est pas trop proche des autres, on l'ajoute à la liste
        if ajout:
            lt.append((xx, yy))
            n = n - 1  # une ville en moins à choisir
    return lt



def distance_euclidienne_carree(villes):
    """
    Calcule la distance euclidienne entre deux points.
    """
    liste_distances = []
    for i in range(len(villes)):
        liste_distances.append([])
        for j in range(i):
            liste_distances[i].append(liste_distances[j][i])
        liste_distances[i].append(np.inf)
        for j in range(i+1, len(villes)):
            liste_distances[i].append(math.sqrt( ((villes[i][0]-villes[j][0])**2) + ((villes[i][1]-villes[j][1])**2) ))
    distances = np.array(liste_distances)
    return distances

villes = construit_ville(100)
distances = distance_euclidienne_carree(villes)

ant_colony = AntColony(distances, 10, 2, 100, 0.95, alpha=1, beta=1)
shortest_path = ant_colony.run()
print("shortest_path : {}".format(shortest_path))