Discussion :

[Aleph69]

Bonsoir Nemerle,

je ne suis pas sûr d'avoir compris ce que tu cherches à faire.
Tu as présenté ta problématique comme ceci :

mon K est décomposé en un pavage de "briques", et il y a en a beaucoup. Je veux decomposer mon K en N ensembles disjoints de briques, ensembles qui doivent tous avoir "à peu près" la meme taille. Ensuite, je vous trouver une brique dans chacun des N ensembles de telle sorte que la somme des distances entre ces N briques soit minimale.

Moi, je lis : je veux faire une partition puis trouver une brique dans chaque sous-domaine pour minimiser la somme des distances entre les briques choisies.

Mais, dans ton dernier message tu écris :

partitionner un domaine de telle sorte que la somme des "distances" entre sous-domaines soit minimale; la "distance entre 2 sous-domaine étant librement définie par le choix préalable d'un point (=une brique) dans le domaine, qui joue le jeu de centroïde.

Là, je lis : je cherche le couple (Partition, Briques) tel que la somme des distances entre briques est minimale, sous la contrainte d'avoir une seule brique par sous-domaine.

Peux-tu préciser quelle est la bonne version?

[Nemerle]

La derniere! Effectivement, il y avait un loup dans ma 1ière définition...

[Aleph69]

Bonjour,

je n'ai pas cherché à le démontrer mais je pense que le problème que tu cherches à résoudre est de classe NP donc, si l'heuristique que tu utilises te convient, je pense que tu perdras ton temps à chercher un algorithme rapide te donnant un minimum global. C'est la partie "recherche de la meilleure partition" qui est sans doute NP. Etant donnée une partition, la recherche des briques minimisant la distance paraît soluble en un temps polynomial (a priori cubique avec peut-être une amélioration possible en polylogarithmie si tu fais des efforts du côté du calcul des distances entre briques).

EDIT (idée en passant) : tu pourrais décomposer ton problème en deux sous problèmes (en fixant des paramètres) et minimiser en utilisant une approche alternée. Les deux problèmes sont :
P1 : étant une partition, trouver les briques qui minimisent etc
P2 : étant des briques fixées, trouver une partition telle que etc
Il faut résoudre un premier sous-problème puis injecter la solution dans le second sous-problème, résoudre ce dernier et injecter la solution dans le premier sous-problème, etc etc.