Version imprimable
Bonjour, ce pitit problème est intéressant:
- Soit une constante D>0
- on dispose de 2 familles de points (Pi) et (Qj) dans le plan
- on cherche les 2 plus grandes sous-familles de (Pi) et (Qj) telles que la distance entre les Pi et les Qj soit toujours supérieure à D. Ca revient donc à enlever des Pi et des Qj afin que d(Pi,Qj)>D pour les restants.
Qui va tuner l'algo le plus rapide? ;)
Je pense que le problème demande à être précisé:
En effet supposons que tous les points Pi se trouvent tous à plus de 2000 km de tous les points Qj mais il y a une exception :
Un seul point P0 se trouve à 1 km d'un seul point disons Q0.
Supposons que D=1000 km
De sorte que si j'enlève seulement P0 j'ai une solution maximale du point de vue des points Q
Si j'enlève Q0 j'ai une solution maximale du point de vue des points P.
Qu'entends-tu par 'deux familles maximales' ?
Ca ressemble rudement à un problème de SVM...Citation:
Envoyé par Nemerle
La solution n'est évidement pas unique. Mon expression n'est effectivement pas précise: en fait, on cherche à maximiser la somme des points des deux familles. Soit, si A et B sont les deux sous-familles: max(cardA+cardB)Citation:
Envoyé par Zavonen
C'est un problème pratique (j'en parlerai plus tard): on cherche à enlever le moins de points des 2 nuages...
SVM? Sciences et Vie micro? Sodomite vachement méchant? ;)Citation:
Envoyé par pseudocode
En effet, ça ressemble à la recherche d'un hyperplan de séparation optimale de 2 classes
SVM
On peut toujours essayer ça:
Prendre l'isobarycentre P des points Pi.
L'isobarycentre Q des points Qj.
Donc l'isobarycentre H du système global se trouve sur la droite (PQ).
Prendre la droite orthogonale à (PQ) passant par H.
Enlever une bande de largeur d centrée sur H et orthogonale à (PQ)
Conserver les points Pi qui sont du côté de P par rapport à cette bande.
Conserver aussi les points Qj qui sont du côté de Q par rapport à cette bande.
On obtient ainsi rapidement un ensemble de points satisfaisant à la condition requise.
Mais rien ne prouve qu'il soit optimal du point de vue du nombre d'éléments.
C'est juste un truc comme ça à l'arrache, pour lancer les enchères.
1/ batir la matrice des distances et pour chaque point calculer le nombre de points trop pres dans l'autre groupe
2/ batir un tas binaire en fonction de ce nombre (d'autant plus prioritaire que le nombre de points trop pres est eleve)
3/ tant que la racine du tas a des voisins trop pres, retirer la racine en mettant a jour le tas
Pas sur que ca donne le resultat optimal, mais ca ne devrait pas etre loin. A vue de nez, c'est en max(n,m) min(n,m) log(n+m). J'ai l'impression que faire nettement mieux va exiger d'etre beaucoup plus sophistique.
Zavonen: effectivement, c'est loin d'être optimal, d'autant plus que l'enveloppe des nuages est non convexe...
Jean-Marc: c'est aussi mon idée, et ça fonctionne, mais c'est gourmand!
Pour faire mieux, il faut vraisemblablement utiliser l'inegalite triangulaire ou meme le fait que les points sont dans un plan euclidien (sinon on est deja en nm rien que pour regarder une fois toutes les distances, un log en plus, ca semble normal; a moins qu'il n'y ait une structure de queue a priorite plus adaptee -- je connais bien le tas de fibonnacci qui permet l'ajustement de la priorite en temps amorti constant, mais uniquement quand on ajuste la priorite dans l'autre sens :-(). Pas trop le temps de reflechir a cela au boulot, surtout que j'ai meme pas une idee de piste.Citation:
Envoyé par Nemerle
encore plus simple ... voyez cela comme un problème de théorie des graphes .. supposons que nous possédons un graphe biparti ... ou les arêtes sont valuées ( les distances ) ...maintenant on peut le voir comme un problème simple de coloration de sommets avec contraintes que toutes les arêtes n'aient pas d 'arêtes de poids inférieur à D ..
Et pour ajouter sur l'importance du temps de calcul, le problème se généralise à N nuages.. (N<10)Citation:
Envoyé par Jean-Marc.Bourguet
Faudrait développer mon ami...Citation:
Envoyé par benDelphic
On peut déjà faire un quadrillage du plan avec des cases de taille D. Ça limitera les calculs a faire sur un voisinage 3x3. Bon, c'est pas bien glorieux comme optimisation...Citation:
Envoyé par Nemerle
Aucune autre proposition sérieuse à faire pour l'instant.
Simplement, je tiens à la disposition de qui voudra un petit script permettant de trouver par force brute en quelques secondes les solutions pour de petits nuages n'excédant pas en pratique une dizaine de points.
Cela pourrait servir pour la vérification ou pour des contre-exemples.
On peut commencer par associer à tout point de P l'ensemble des points de Q avec lesquels il est incompatible, et vice versa.
Déja c'est gourmand en card(P)*card(Q).
Par la suite chercher parmi tous les points de P et de Q lequel est le plus 'gênant' (se trouve dans le plus de listes d'incompatibilité, l'éliminer en premier, mettre à jour les listes and so on jusqu'à ce que toutes les listes d'incompatibilité soient vides.
C'est pas génial non plus mais faut bien faire avancer le schmilblick...
PS: C'est exactement la proposition de Jean Marc. Un coup pour rien !
Hum... c'est moi ou on a abandonné le coté "optimal" de la solution recherchée ?
Ce n'est pas toi. On doit etre proche de l'optimal dans pas mal de cas (en particulier s'il y a bien des nuages de points et pas des points bien choisis pour rendre le probleme difficile), mais il y a des cas ou on n'y est pas a coup sur (ne fut-ce 5 points alignes, espace de D-epsilon, alternativement d'un ensemble ou l'autre).Citation:
Envoyé par pseudocode
On peut améliorer la proposition de Jean-Marc en prenant deux points de référence.
Par exemple le centre de gravité du premier nuage P
Le centre de gravité du second Q.
On mesure alors les distances PiP et les distances QiQ, la distance PQ c'est en m+n+1
Reprend alors l'idée de Jean-Marc mais en appliquant l'inégalité triangulaire avant.
Cependant, ce procédé ne garantit pas forcément une amélioration des performances (cas où les deux nuages sont confondus). Il est efficace s'ils sont 'globalement suffisamment éloignés'.
@pseudocode. Commencer par chercher des solutions ne veut pas dire qu'on renonce à optimiser, on commence par restreindre le nombre des candidats.
PS: Finalement non parce que les tests pour l'inégalité du triangle nous ramènent en m*n. A abandonner donc si on veut passer en dessous de m*n.
Au fait le minimum est inférieur au sup du cardinal du nuage P et du cardinal du nuage Q. Puisque P et Q isolément sont des solutions (en général non optimales). Juste pour dire que toute prétendue solution ayant moins de points que l'un ou l'autre des deux nuages est forcément non optimale.
Edit: C'est vrai seulement si les nuages sont disjoints. Si les nuages sont confondus optimal= vide !!!
Second point (intuitif): Si on trace les droites de régression des deux nuages, les points 'à problème' devraient se situer a proximité de l'intersection. On pourrait donc prendre comme critère prioritaire de suppression la proximité avec ce point. (quand les deux droites ne sont pas parallèles).
Plus précisément encore, les deux nuages peuvent être mis dans des rectangles minimaux au moyen du coefficient de regression et du coefficient de correlation.
On peut commencer par régler les problèmes de distances entre ces deux rectangles avant de passer aux nuages eux-mêmes.