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?
Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre
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...)
Ca ressemble rudement à un problème de SVM...Envoyé par Nemerle
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
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)
C'est un problème pratique (j'en parlerai plus tard): on cherche à enlever le moins de points des 2 nuages...
Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre
SVM? Sciences et Vie micro? Sodomite vachement méchant?
Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre
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.
Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.
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!
Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre
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.
Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.
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)
Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre
Faudrait développer mon ami...
Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre
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...)
Hum... c'est moi ou on a abandonné le coté "optimal" de la solution recherchée ?
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
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).
Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.
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.
Ce qu'on trouve est plus important que ce qu'on cherche.
Maths de base pour les nuls (et les autres...)
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.
Ce qu'on trouve est plus important que ce qu'on cherche.
Maths de base pour les nuls (et les autres...)
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Répondre avec citation
Partager