Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Une contrainte sur 2 nuages de points
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' ?
Ce qu'on trouve est plus important que ce qu'on cherche.
Maths de base pour les nuls (et les autres...)
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)Envoyé par Zavonen
C'est un problème pratique (j'en parlerai plus tard): on cherche à enlever le moins de points des 2 nuages...
Ca ressemble rudement à un problème de SVM...
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
SVM? Sciences et Vie micro? Sodomite vachement méchant?
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.
Ce qu'on trouve est plus important que ce qu'on cherche.
Maths de base pour les nuls (et les autres...)
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.
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 ..
Faudrait développer mon ami...
Et pour ajouter sur l'importance du temps de calcul, le problème se généralise à N nuages.. (N<10)
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...
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
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.
Ce qu'on trouve est plus important que ce qu'on cherche.
Maths de base pour les nuls (et les autres...)
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 !
Ce qu'on trouve est plus important que ce qu'on cherche.
Maths de base pour les nuls (et les autres...)
Si je comprend correctement le problème :
- On a 1 nuage de points
- Dans ce nuage, on souhaiterait faire la différenCe entre 2 classes (forme du style bilboquet)
- Cette séparation serait basée sur une distance minimale D
C'est bien ça ??
autre idée basée sur les enveloppes
autre idée :
je récapitule l'énoncé :
on a des nuages de points (non convexes) et on veut qu'il existe une distance minimale R entre eux. en gros : qu'une bille de diamètre R puisse rouler librement autour de chaque nuage sans en toucher un autre.
Voila une suggestion d'algos:
1/ calculer les enveloppes de chaque nuage (il y a des algos qui calculent les enveloppes non convexes me semble-t-il. (*)
2/ dilater chacune des enveloppes E d'un rayon R. On considère le volume entre E et (E+R).
3/ virer tous les points étrangers se trouvant dans ce volume.
Pour optimiser, on peut aussi ordonner ces volumes par ordre croissant.
(*) si mes souvenirs sont bons, on commence à calculer une triangulation de delaunay et l'enveloppe convexe, puis on vire les vertex dont une arête est supérieure à R et un sommet appartient à l'enveloppe convexe.
Répondre avec citation
Partager