Besoin d'aide pour un algorithme

[invite5119e3ea]

Bonjour à tous !

Je suis en train de développer une application, et je bloque depuis quelques jours sur le développement d'un algo.
Voilà ce que je voudrais faire :
J'ai en entrée un nombre quelconque de points, et leurs coordonnées GPS.
Je voudrais pouvoir les rassembler par groupe de 3, en tenant compte de leur proximité.
Je vais essayer de montrer un exemple (je travaille avec des coordonnées cartésiennes, j'espère que l'algo ne change pas en passant en coordonnées GPS) :
| |B| | | | | | |
| |A| | | |D| | |
| | | | | |C| |E|
| | | | | | | | |
| | | | | | | | |
| | | | | | | |F|

A(2,5) B(2,6) C(6,4) D(6,5) E(8,4) F(8,1)

Donc le but serait de produire en sortie deux groupes BAD et CEF.

Si par hasard on avait un nombre de points qui ne soit pas un multiple de 3, il faudrait faire un groupe avec ce qui reste tout en tenant compte de la proximité (qui sera donc constitué de 4 ou 5 points).

J'espère que vous pourrez m'aider ! Merci d'avance !
-----

[invite4492c379]

Hello,

il s'agit là d'un problème moins simple qu'il n'y paraît, sauf dans le cas où il a 3 points ou moins.

Tu formules le problème d'une manière un peu floue. Pourquoi ton example doit-il donner ABD et CEF et non ABF, CDE ?
Pourquoi devrait-il rester 4 ou 5 points (au pire on devrait s'attendre à 1 ou 2) ?

Que cherches-tu à minimiser ? la surface des triangles ? La somme des longueurs des côté ? Le rayon de cercle inscrit ?

[danyvio]

C'est effectivement un problème assez complexe qu'on voit en recherche opérationnelle. On utilise fréquemment le "critère de Ward" pour regrouper au mieux les points .. Mais c'est loin pour moi, et je conseille de voir la littérature actuelle à ce sujet. Bon courage.

[invite5119e3ea]

Pourquoi ton example doit-il donner ABD et CEF et non ABF, CDE ?

Alors en fait c'est parce que si on fait ABF, F est trop loin de A et B. Le but de l'appli est de créer des groupes de points le plus près possible des uns des autres, a terme il y aura des groupes de personnes qui auront un triangle à parcourir à pied.

Pourquoi devrait-il rester 4 ou 5 points (au pire on devrait s'attendre à 1 ou 2) ?

Tout à fait, mais j'ai un minimum de 3 points à respecter, donc 1+3 ou 2+3.

Que cherches-tu à minimiser ? la surface des triangles ? La somme des longueurs des côté ? Le rayon de cercle inscrit

Justement je ne sais pas ce qu'il faut que je minimise pour obtenir un résultat conforme à ce que j'attends :/. Au début j'étais partisur les périmètres, mais du coup ça me produirait ABF et CDE sur l'exemple que j'ai donné.

C'est effectivement un problème assez complexe qu'on voit en recherche opérationnelle. On utilise fréquemment le "critère de Ward" pour regrouper au mieux les points .. Mais c'est loin pour moi, et je conseille de voir la littérature actuelle à ce sujet. Bon courage.

Je vais aller voir merci.

[A voir en vidéo sur Futura]

[invite8666d089]

a terme il y aura des groupes de personnes qui auront un triangle à parcourir à pied

Il s'agit donc de la somme des côtés des triangles.

Mais on ne sait toujours pas ce qu'on cherche. Je vois déjà au moins trois possibilités :
- chercher l'agencement où la somme de l'ensemble des côtés des triangles est la plus petite possible
- chercher l'agencement ou l'écart entre le parcours le plus long et le plus petit est le plus petit possible
- chercher l'agencement où le parcours le plus long est le plus petit possible

Que veux-tu faire au juste ?

[invite5119e3ea]

Déjà trouver une solution qui me produit le résultat que je veux obtenir dans l'exemple que je fournis. La première solution que tu me donnes ne fonctionne pas, par contre les deux autres peuvent fonctionner je pense !

Aurais tu une idée de comment fonctionnerais un de ces deux algos ?

J'imagine déjà qu'il faut construire un tableau avec toutes les configurations possibles, de taille n*(n-1)*(n-2), n étant le nombre de points, ça c'est pas trop difficile. Mais ensuite ?

[invite2216f80a]

Je sais pas si ça peut vous aider, mais j'ai vu ça en data mining avec la méthode du K-Mean, il suffit de donner le nombre de groupe que l'on veut et l'algorithme mets les points dans les groupes en fonctions de leurs distances par rapport au centre du groupe.

Sur internet, il devrait y avoir des détails sur l'implémentation de l'algo dans un langage, sinon j'ai l'algo.

[invite4492c379]

Déjà trouver une solution qui me produit le résultat que je veux obtenir dans l'exemple que je fournis. La première solution que tu me donnes ne fonctionne pas, par contre les deux autres peuvent fonctionner je pense !

Aurais tu une idée de comment fonctionnerais un de ces deux algos ?

J'imagine déjà qu'il faut construire un tableau avec toutes les configurations possibles, de taille n*(n-1)*(n-2), n étant le nombre de points, ça c'est pas trop difficile. Mais ensuite ?

Hello,

peut-être explorer une solution à base de :

ensemble de points => triangularisation delaunay (ou autre ?) => transformer en graphe où chaque triangle est un sommet, y stocker le périmètre du triangle =>
soit : prendre le dual du graphe, poids des arêtes = périmètre du triangle => chercher le couplage de poids minimum
soit : chercher le stable de poids minimum
=> revenir au pb initial, rajouter les points non compris dans un parcours au parcours le plus proche

[Dlzlogic]

Bonjour,
Deux questions :
Quel est l'ordre d'idée du nombre de personnes ?
Ce groupe est-il évolutif, et de quelle façon ? Par exemple, que se passe-t-il lorsqu'un nouveau membre intègre le groupe ?

A mon avis, déjà il sera difficile de déterminer les groupes de 3, alors, pour trouver la meilleure répartition, ce sera encore plus dur.

[invite8666d089]

Trois modèles ont été cités. J'ai fait pas mal de RO il y a des lustres (pour moi aussi c'est loin), mais ne les connais pas. Donc gratte du côté des modèles qui t'ont été donnés, inutile de réinventer l'eau chaude s'ils sont adaptés à ton besoin.

Et si tu ne trouves pas chaussure à ton pied, lis la suite.

Comme Dlzlogic, je commencerais par l'ordre de grandeur des points du graphe. Je m'explique : si je n'ai pas fait d'erreur, un graphe de 6 points offre 20 combinaisons différentes. Un graphe de 9 points : 84 combinaisons. Si le nombre de points est trop important (entre 2300 et 2400), un processeur 32 bits atteindra sa limite de capacité et tu seras bloqué.

Si tu as besoin d'un ordre de grandeur inférieur à cette limite, tout est possible en RAM, même de réchauffer une tasse de café sur le processeur si tu n'es pas pressé. Si cet ordre de grandeur est supérieur à la mémoire vive de ton ordi, je ne vois qu'une solution : stocker dans un premier temps toutes les combinaisons dans un fichier à accès aléatoire, puis traiter le fichier pour en extraire la meilleure solution.

[invite8666d089]

#ngagne
Je pense que tu ferais bien d'ouvrir ton propre fil (en précisant le langage de programmation que tu utilises), car on risque de se prendre les pieds dans le tapis et de ne plus savoir qui répond à qui. Un fil = 1 sujet.

#olivi3R
Tu as le choix entre le périmètre du triangle et la somme des médianes (isobarycentre). Les résultats sont sensiblement identiques.
Sur les 10 combinaisons (20 étaient une erreur due aux doublons) qu'on obtient avec les 6 points de ton exemple, les résultats sont les suivants :
- la somme minimum des côtés (périmètre) place en tête les combinaisons ABD-CEF puis ABC-DEF et place en queue les combinaisons ACE-BDF puis ADF-BCE.
- la somme minimum des médianes place en tête les combinaisons ABD-CEF puis ABC-DEF et place en queue les combinaisons ADF-BCE puis ACE-BDF.
Les deux donnant sensiblement les mêmes résultats, je choisirais la stratégie la plus simple à programmer : la somme des périmètres minimum.

Je n'ai pas étudié les cercles circonscrits, mais les cercles inscrits ne sont pas du tout adaptés dans la mesure où pour un même cercle on peut construire des triangles dont les périmètres peuvent varier de l'infiniment petit à l'infiniment grand.

[yoda1234]

#ngagne
Je pense que tu ferais bien d'ouvrir ton propre fil (en précisant le langage de programmation que tu utilises), car on risque de se prendre les pieds dans le tapis et de ne plus savoir qui répond à qui. Un fil = 1 sujet.

J'ai déplacé le message pour en faire un sujet à part entière.

[invite8666d089]

Merci, ce sera plus simple.