1A.e - Enoncé 22 octobre 2019 (1)

Correction du premier énoncé de l’examen du 22 octobre 2019. L’énoncé propose une façon de disposer des tables rondes dans une salle ronde.

On sait d’après les dernières questions qu’il faudra tout répéter plusieurs fois. On prend le soin d’écrire chaque question dans une fonction. C’est un mariage dans une salle ronde. On veut disposer les tables de sortes qu’elles soient éloignées le plus possible les unes des autres et du bord de la salle. Les tables sont toutes rondes et toutes la même taille.

Q1 - distance_table

Ecrire une fonction qui calcule la distance entre deux tables rondes dont on connaît le centre. Et comme ce sont des tables rondes, on considère que la distance entre deux tables est la distance entre leurs centres.

def distance_table(x1, y1, x2, y2):
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5


distance_table(0, 0, 2, 1)

2.23606797749979

Q2 - distance_bord

Ecrire une fonction qui calcule la distance entre une table (son centre) et le bord de la salle de rayon R.

def distance_bord(x1, y1, R):
    dist = distance_table(x1, y1, 0, 0)
    return R - dist


distance_bord(1, 1, 5)

3.585786437626905

distance_bord(10, 1, 5)

-5.04987562112089

Q3 - table_alea

Ecrire une fonction qui tire aléatoirement une table dans le cercle de rayon R.

import random


def table_alea(R):
    R2 = R**2
    dist = R2 * 2
    while dist > R2:
        x = random.uniform(-R, R)
        y = random.uniform(-R, R)
        dist = x**2 + y**2
    return x, y


table_alea(5)

(0.04023026006364461, -4.613278941761477)

On peut utiliser une autre façon en utilisant les coordonnées polaires.

import math


def table_alea_pol(C):
    t = random.uniform(0, math.pi)
    y = random.uniform(0, C)
    x = math.cos(t) * t
    y = math.sin(t) * t
    return x, y


table_alea_pol(5)

(0.2697993898932539, 0.07781479211233774)

Q4 - n_table_alea

Ecrire une fonction qui tire aléatoirement N tables dans le cercle de rayon R.

def n_table_alea(N, R):
    return [table_alea(R) for n in range(N)]


n_table_alea(3, 5)

[(-2.104239515207136, -1.7109081402403072),
 (-0.46932352351540807, -0.3259610442266929),
 (-1.1743368223886739, 3.2821629999494295)]

Q5 - table_proches

Ecrire une fonction qui retourne la table la plus proche d’une table ou du bord. La fonction doit retourner l’indice de la table la plus proche ou -1 si c’est le bord, puis la distance associée. On ajoute un paramètre skip_i pour éviter une table dans la liste list_tables.

def table_proches(x1, y1, list_tables, R, skip_i):
    proche = -1
    best = distance_bord(x1, y1, R)
    for i, table in enumerate(list_tables):
        if i == skip_i:
            continue
        dist = distance_table(x1, y1, table[0], table[1])
        if dist < best:
            best = dist
            proche = i
    return proche, best


R = 5
list_tables = n_table_alea(3, R)
table_proches(1, 1, list_tables, R, None)

(0, 1.7403604958859722)

table_proches(R * 0.9, 0, list_tables, R, None)

(-1, 0.5)

Q6 - distance_n_tables_alea

Ecrire une fonction qui tire N tables aléatoirement et qui retourne la distance minimum entre deux tables ou le mur et les tables.

def distance_n_tables_alea(N, R):
    distrib = n_table_alea(N, R)
    best = R**2
    for i, table in enumerate(distrib):
        proche, dist = table_proches(table[0], table[1], distrib, R, skip_i=i)
        if dist < best:
            best = dist
    return best, distrib


distance_n_tables_alea(3, R)

(1.151393678876878,
 [(-0.0883943109284333, -3.2251498896276685),
  (1.9591970274173125, -0.8759281350069976),
  (0.8362221630472657, 3.7566611650530053)])

Q7 - meilleur_table_alea

Ecrire une fonction qui tire N tables aléatoirement et qui retourne la distance minimum entre deux tables ou le mur et les tables.

def meilleur_table_alea(k, N, R):
    dist = 0
    best = None
    for i in range(k):
        d, distrib = distance_n_tables_alea(N, R)
        if d > dist:
            best = distrib
            dist = d
    return best, dist


meilleur_table_alea(10, 3, R)

([(-1.0002849316792242, -3.5208215962264875),
  (1.537577072452744, -0.650373925673775),
  (2.339568894819979, 0.31652883529303466)],
 1.256221251336387)

Q8 - résultat numérique

Ecrire une fonction qui retourne le résultat pour 11 tables et une salle de diamètre 1.

best, dist = meilleur_table_alea(10, 11, 1)
best, dist

([(0.5565818929001787, 0.05896867240161785),
  (-0.5288969098327476, 0.28733719348942466),
  (-0.6110699282390006, 0.32241732345580165),
  (-0.14909553247181195, -0.9356539992681199),
  (0.026230694145464417, -0.2908024901550055),
  (0.4975323234658624, -0.06918255935350293),
  (0.60937258121247, 0.16579629631884596),
  (0.22654870937824634, 0.12601838486539685),
  (-0.651232619461013, 0.05440550117493803),
  (-0.25693188063963546, 0.044795815889184576),
  (-0.07316443943516515, 0.8533292769508105)],
 0.0525413549133239)

Q9 - plot_tables

Ecrire une fonction qui représente la solution avec matplotlib en partant de l’exemple donnée.

%matplotlib inline

import matplotlib.pyplot as plt
from matplotlib.patches import Circle

fig, ax = plt.subplots(1, 1, figsize=(4, 4))
R = 1
ax.set_xlim([-R, R])
ax.set_ylim([-R, R])
c = Circle((0, 0), 1, alpha=0.2)
ax.add_artist(c)
ax.plot([b[0] for b in best], [b[1] for b in best], "o");

Q10 …

Il est difficile de tomber sur une bonne répartition de tables en partant du hasard et plus il y aura de tables, plus il faudra de tirages. On peut aussi chercher à positionner les tables selon un quadrillage hexagonal en formant une spirale et de chercher le meilleur écartement. On peut aussi partir d’un tirage puis d’éloigner les deux tables les plus proches. L’éloigner de combien, c’est une autre question. C’est la première option et elle ne marche pas très bien.

import numpy


def improve_distrib(iter, tables, R, alpha=0.2):
    for it in range(iter):
        # On cherche la pair la plus proche.
        best = R**2
        pair = None
        for i, table in enumerate(tables):
            proche, dist = table_proches(table[0], table[1], tables, R, skip_i=i)
            if dist < best:
                best = dist
                pair = i, proche

        if it % 50 == 0:
            print(it, "paire", pair, "distance", best)

        # On choisit une table.
        if pair[0] == -1:
            i = 1
        elif pair[1] == -1:
            i = 0
        else:
            i = numpy.random.randint(0, 1)

        pi = pair[i]
        if pair[1 - i] == -1:
            pjp = (0, 0)
            sign = 1
        else:
            pjp = tables[pair[1 - i]]
            sign = -1

        # On calcule le vecteur entre les deux tables.
        dx, dy = (pjp[0] - tables[pi][0], pjp[1] - tables[pi][1])

        # Un peu d'aléa.
        h = numpy.random.uniform(0, alpha)
        dx *= h * sign
        dy *= h * sign

        # On bouge la table.
        table = tables[pi]
        tables[pi] = (table[0] + dx, table[1] + dy)
        if distance_bord(tables[pi][0], tables[pi][1], R) < 0:
            # Table hors du cercle
            tables[pi] = (table[0] - dx, table[1] - dy)


R = 1
best_sol, dist = meilleur_table_alea(10, 11, R)
improve_distrib(351, best_sol, R, alpha=0.5)

0 paire (4, 5) distance 0.16110855450954664
50 paire (4, 6) distance 0.13158100390586172
100 paire (4, 5) distance 0.2384176552949989
150 paire (4, 5) distance 0.218691822411302
200 paire (4, 5) distance 0.19838094003303594
250 paire (4, 5) distance 0.2162723387696761
300 paire (4, 10) distance 0.20826241454101815
350 paire (4, 5) distance 0.2094900548253301

fig, ax = plt.subplots(1, 1, figsize=(4, 4))
ax.set_xlim([-R, R])
ax.set_ylim([-R, R])
c = Circle((0, 0), 1, alpha=0.2)
ax.add_artist(c)
ax.plot([b[0] for b in best_sol], [b[1] for b in best_sol], "o");

Q10 - Voronoï

On peut aussi écarter une table de ses voisins les plus proches, voisins trouvés grâce à un diagramme de Voronoï ou à une triangulation de Delaunay.

from scipy.spatial import Voronoi, voronoi_plot_2d, Delaunay

points = numpy.array(best_sol)
vor = Voronoi(points)
dela = Delaunay(points)

fig, ax = plt.subplots(1, 1, figsize=(4, 4))
c = Circle((0, 0), 1, alpha=0.2)
ax.add_artist(c)
ax.plot([b[0] for b in best_sol], [b[1] for b in best_sol], "o")
voronoi_plot_2d(vor, ax=ax)
ax.triplot(points[:, 0], points[:, 1], dela.simplices.copy(), "--", label="Delaunay")
ax.set_xlim([-R, R])
ax.set_ylim([-R, R])
ax.legend();

On ajoute le bord.

N = 12
bords = []
for i in range(0, N + 1):
    bords.append((R * math.cos(i / N * math.pi * 2), R * math.sin(i / N * math.pi * 2)))
points2 = numpy.vstack([points, bords])

fig, ax = plt.subplots(1, 1, figsize=(4, 4))
c = Circle((0, 0), 1, alpha=0.2)
ax.add_artist(c)
ax.plot([b[0] for b in best_sol], [b[1] for b in best_sol], "o")
vor2 = Voronoi(points2)
dela2 = Delaunay(points2)
voronoi_plot_2d(vor2, ax=ax)
ax.triplot(points2[:, 0], points2[:, 1], dela2.simplices.copy(), "--")
ax.set_xlim([-R, R])
ax.set_ylim([-R, R]);

Le diagramme de Voronoï permet de construire un voisinage de points pour qu’on peut rapprocher le plus possible d’en ensemble de triangles équilatéraux ou rapprocher une table le plus possible de sa frontière la plus éloignée. Après quelques essais, je ne peux pas que ce fut là la meilleure inspiration.

Q10 - KMeans

Une autre idée consiste à recouvrir la salle de points puis à effectuer un KMeans pour créer artificiellement des zones.

def points_in_circle(N, R):
    points = numpy.empty(((N + 1) ** 2, 2))
    pos = 0
    for i in range(0, N + 1):
        for j in range(0, N + 1):
            points[pos, 0] = 1.0 * i / N * R * 2 - R
            points[pos, 1] = 1.0 * j / N * R * 2 - R
            pos += 1
    dist = points[:, 0] ** 2 + points[:, 1] ** 2
    points = points[dist <= R**2, :]
    return points


R = 1
points = points_in_circle(25, R)

fig, ax = plt.subplots(1, 1, figsize=(4, 4))
c = Circle((0, 0), R, alpha=0.2)
ax.add_artist(c)
ax.plot(points[:, 0], points[:, 1], ".");

from sklearn.cluster import KMeans

km = KMeans(n_clusters=11)
km.fit(points)

KMeans(algorithm='auto', copy_x=True, init='k-means++', max_iter=300,
       n_clusters=11, n_init=10, n_jobs=None, precompute_distances='auto',
       random_state=None, tol=0.0001, verbose=0)

pred = km.predict(points)

Les centres des clusters sont les emplacements des tables cherchées.

fig, ax = plt.subplots(1, 2, figsize=(10, 4))
c = Circle((0, 0), 1, alpha=0.2)
ax[0].add_artist(c)
ax[0].set_xlim([-R, R])
ax[0].set_ylim([-R, R])
ax[0].scatter(points[:, 0], points[:, 1], c=pred)

c = Circle((0, 0), 1, alpha=0.2)
ax[1].add_artist(c)
ax[1].set_xlim([-R, R])
ax[1].set_ylim([-R, R])
ax[1].plot(km.cluster_centers_[:, 0], km.cluster_centers_[:, 1], "o")
vor2 = Voronoi(km.cluster_centers_)
voronoi_plot_2d(vor2, ax=ax[1])
ax[1].set_title("Centres des clusters - KMeans")
ax[1].set_xlim([-R, R])
ax[1].set_ylim([-R, R]);

def distance_n_tables(distrib, R):
    best = R**2
    for i, table in enumerate(distrib):
        proche, dist = table_proches(table[0], table[1], distrib, R, skip_i=i)
        if dist < best:
            best = dist
    return best


distance_n_tables(km.cluster_centers_, 1), distance_n_tables(best_sol, 1)

(0.22015129672480682, 0.13834146640009876)

On essaye avec un mélange de lois normales.

from sklearn.mixture import GaussianMixture

gau = GaussianMixture(11)
gau.fit(points)
pred = gau.predict(points)

fig, ax = plt.subplots(1, 2, figsize=(10, 4))
c = Circle((0, 0), 1, alpha=0.2)
ax[0].add_artist(c)
ax[0].set_xlim([-R, R])
ax[0].set_ylim([-R, R])
ax[0].scatter(points[:, 0], points[:, 1], c=pred)

c = Circle((0, 0), 1, alpha=0.2)
ax[1].add_artist(c)
ax[1].set_xlim([-R, R])
ax[1].set_ylim([-R, R])
ax[1].plot(gau.means_[:, 0], gau.means_[:, 1], "o")
vor2 = Voronoi(gau.means_)
voronoi_plot_2d(vor2, ax=ax[1])
ax[1].set_title("Centres des clusters - gaussian mixture")
ax[1].set_xlim([-R, R])
ax[1].set_ylim([-R, R]);

distance_n_tables(km.cluster_centers_, 1), distance_n_tables(gau.means_, 1)

(0.22015129672480682, 0.21874003784217044)

---

Notebook on github