Conception et Pratique de l'algorithmique
UPMC - 4I505 CPA

TME 9 - Problème k-center

Dans cette séance nous allons implémenter l'algorithme de flux "l'algorithme doublant" pour le problème de k-center. Celui-ci est décrit dans les notes de cours.

L'espace métrique

Nous considérons les points dans R2 muni de la distance euclidienne.

Les paramètres en ligne de commande

Votre programme reçoit deux paramètres en ligne de commande, un entier k, qui est le nombre maximal de centres recherchés, et le nom du fichier d'entrée.

Le fichier d'entrée

Les fichiers d'entrée sont des fichier texte, avec une ligne par point, contenant les coordonnées séparées par un espace.

L'affichage de la solution

Votre programme affichera la solution dans la sortie standard, dans le même format : une ligne par point, contenant les coordonnées séparées par un espace.

Visualiser la solution

Pour afficher votre solution (exemple), vous pourriez utiliser ce programme ou ce formulaire.
flux d'entrée :
Solution produite par votre programme :

Les fichiers d'entrée

Trois fichiers sont mis à votre disposition.
grid3x3.txt
contient les 9 points de la grille de dimension 3x3.
paris.txt
contient les 11348 points d'intersection des rues dans Paris intramuros.
france.txt
contient les 36568 centres de villes de la France métropolitaine.
Ce fichiers proviennent d'ici et là. Les coordonnées GPS ont été grossièrement projetés dans le plan en multipliant la latitude par -1.5.

Les étapes de programmation

Les points

Pour représenter les points, en python on utilisera les tuplets, et en Java on écrira une classe Point avec deux attributs double x,y. Un ensemble de points sera représenté en Python par une liste, et en Java par une LinkedList<Point>. Il faut ensuite écrire une fonction dist, qui retourne la distance entre deux points. Pour cela, vous pouvez utiliser la fonction Math.hypot ou math.hypot.
Écrivez également une fonction distSet, qui retourne la distance minimale entre un point x donnée et un point y d'une liste de points S donnée.

Flux de points

Écrivez une classe FluxPoints qui lit un fichier texte et produit un flux de points. Elle sera muni d'un constructeur qui prend en paramètre le nom du fichier à lire, et d'une méthode next qui retourne le prochain point du flux, ou rien si la fin du flux est atteint. (en Java: Null, en Python:None)

Solution aléatoire

Écrivez un premier programme qui choisit uniformément au hasard et indépendamment k points du flux d'entrée. Votre programme ne doit pas connaître la taille du flux en avance. Testez le sur la petite instance grid3x3.

L'algorithme

Le cœur de votre programme est l'implémentation de l'algorithme doublant, qui à partir d'un flux de points produit une solution approchée au problème de k-center. Concrètement vous allez écrire une classe KCenter, le constructeur prend en argument k et il initialise les structures de données internes. Puis vous ajoutez une méthode update(item) qui traite un point item du flux, et une méthode val() qui retourne une solution, sous forme de liste de points.
La partie la plus difficile pour vous sera de déterminer le sous-ensemble maximal $R'\subset R$, qui satisfait que $d(x,y)\geq \tau$ pour tous les points distincts $x,y\in R'$. L'ensemble $R'$ doit être maximal pour l'inclusion pas de cardinalité maximum. Donc par un simple parcours glouton de $R$ vous pourriez constituer $R'$.

Pour aller plus loin

Dans /Vrac/cpa2016/gutenberg vous trouverez une collection de quelques milliers de fichiers texte en français, récupérés de gutenberg.org. Ces fichiers ont une entête contenant titre et auteur. Vous pouvez utiliser votre programme pour les classifier. Choisissez une petite constante c, par exemple 2. Puis pour chaque document produisez un vecteur, qui compte la fréquence de c lettres adjacentes dans le document. Puis appliquez votre programme sur ces vecteurs pour classifier les documents en k groupes distincts. Avec un peu de chance si c est suffisamment grand et k bien choisit vous pourriez peut-être déterminer des groupes de textes similaires, par exemple écrits par un même auteur. Il peut être une bonne idée d'ignorer les ponctuations (considérer tout caractère inférieur à 'A' comme un espace ' ') et de convertir les lettres en minuscules.