Discussion :

[olibara]

Bonjour

Je suis confronté au problème suivant et je cherche un algorythme permetant de traiter cela


Je dispose d'un nombre N de points et leurs coordonées XY disposé aléatoirement sur un plan

De dois creer G groupes ayant un maximum de M points chacun

Chaque groupe doit evidement etre constitué en assemblant les points ayant la meilleure proximité

Donc Hypothese :

100 points XY
Maximum 3 groupes
Maximum 40 points par groupe

Comment aborder cela ?

Merci de vos suggestions

[dourouc05]

Tu peux regarder du côté de l'algorithme des k moyennes, c'est assez facile à implémenter (https://en.wikipedia.org/wiki/K-means_clustering). Par contre, il ne peut rien faire pour la taille maximale d'un groupe, mais la discussion est arrivée il n'y a pas si longtemps sur les forums (tu peux construire un petit truc par-dessus pour t'assurer que ça marche ; pour les détails…).

[olibara]

Merci Dourouc05 et cher compatriote

J'avais le pressentiment de devoir passer par du Delaunay ou du Voronoi
Et tu me conforte donc dans l'idée que c'est la bonne piste

Cela étant je ne suis pas pratiquant je dois donc me faire un peu la main
L'objectif est de traduire ca en cSharp pour faire le boulot

Si j'ai bien compris l'exemple, il partitionne selon le nombre de groupe
Donc dans mon cas je devrais le cas échéant muter un certain nombre de points d'un groupe a l'autre en fonction de la densité et la proximité

[dourouc05]

M'est avis que tu cherches à faire bien compliqué. Vu le nombre de points, a priori, pas besoin d'aller aussi loin. Simplement partir de centres (prendre des points au hasard pour commencer) qui définissent des groupes, assigner chaque point au groupe dont le centre est le plus proche, recalculer les centres comme la moyenne des points du groupe, itérer. Et peut-être réassigner des points à un autre groupe pour la contrainte de quarante points par groupe, ça sera un peu plus inventif.

Ça sera beaucoup plus facile à implémenter qu'une triangulation du genre (et tu trouveras facilement des implémentations existantes, au besoin).

[tbc92]

L'un des problèmes si on choisit 3 centres au hasard, c'est qu'on biaise pas mal les résultats. En caricaturant, si les 3 centres choisis sont tous les 3 très voisins l'un de l'autre, et tous les 3 très excentrés, on arrive à n'importe quoi.

Un algorithme (un peu coûteux) est la méthode de la CAH (Classification hiérarchique ascendante).
- On calcule toutes les distances 2 à 2.
- On prend le couple de points avec la distance minimale, et on associe ces 2 points. Et on a un nouvel élément qui est ce couple de points. On recalcule donc la distance entre ce couple de points et les 98 autres points... A ce niveau là, on a 2 ou 3 choix qui peuvent donner des résultats différents. On peut dire que la distance entre un couple de points AB et un point C est au choix min ( Dist(AC), Dist(BC) ), ou bien Moyenne( Dist(AC), Dist(BC) ) ... ou bien d'autres formules envisageables.
- Et on répète l'opération autant de fois que nécessaire pour avoir les 3 groupes voulus. en associant à chaque fois les 2 éléments avec la distance minimale (un élément étant soit un individu isolé, soit un groupe)
- Et si on veut, on peut ajouter des contraintes pour qu'aucun groupe ne dépasse 40 individus.

[olibara]

Merci Dourouc05
Merci tbc92

tbc92 tu a raison sur le choix at random des trois point de départ et c'est la Remarque que je voulais faire a dourouc05
Maintenant il est sans doute possible de poser des contraintes pour mieux determiner le choix de ces trois points


Mais dans les deux proposition je me demande si on ne va tomber dans un problème classique d'affectation ou a force d'itérer "bêtement" sur les choix les meilleurs le resultat sera une répartition asser hétérogène et mal balancée

Je vais bientot me lancer sur le coding a partir d'un échantillon et voir ce que ca donne

[wiwaxia]

Bonjour,

Je crois qu'il y a une solution relativement simple, la partition du nuage de points relevant le plus souvent d'un choix arbitraire, sauf configuration très particulière (où le nuage comporterait par exemple 3 lobes relativement isolés).
En effet, la distance minimale entre deux points appartenant à des groupes différents sera toujours inférieure à la distance maximale observée à l'intérieur de l'un de ces groupes, ce qui met en échec tout rassemblement des points selon leur proximité naturelle.

La condition de l'énoncé (d'ailleurs assez vague)

Chaque groupe doit évidemment être constitué en assemblant les points ayant la meilleure proximité.

n'est donc pas réalisable, et il paraît effectivement inutile de mettre en route un procédé de triangulation.

1°) Repérer les points les plus éloignés (que l'on appellera A et B) par un inventaire systématique des distances M_iM_j (avec 0 < i < j <= N) , et la distance ( D_max = AB ) qui les sépare .

2°) Entreprendre une partition du nuage par un faisceau d'hyperboles de foyers (A) et (B), en classant les (N - 2) points restant selon l'ordre croissant du paramètre ( h = AM_k - BM_k ) , nécessairement inclus dans le domaine ] -D_max ; D_max [ .
Une fois la liste établie, il suffit en effet:
a) de constituer le premier sous-ensemble (G_A) des (N_A) points correspondant aux (N_A) plus petites valeurs de (h), et incluant A ( h = -D_max );
b) de constituer le second sous-ensemble (G_B) des (N_B) points correspondant aux (N_B) plus grandes valeurs de (h), et incluant B ( h = D_max ) ;
c) d'inclure dans le dernier (G₃) tous les points restants.
Les valeurs de (N_A) et (N_B) seront choisies en fonction des conditions imposées aux 3 effectifs:
■ 20 <= N_A <= 40 ;
■ 20 <= N_B <= 40 ;
■ 20 <= 100 - N_A - N_B <= 40 .

[olibara]

Merci WiWaxia

Je vais aussi réflechir a cette suggestions

Je vous ferai part de mes resultat dès que j'aurai qq chose

[souviron34]

Si je puis me permettre de proposer une approche mathématiquement plus simple :

Comme le dit wiwaxia, tout commence par calculer les coordonnées max et min.

Mais, ce faisant, on peut les calculer simultanément sur 4 axes (conditions spéciales de réduction des points pour l'application d'une méthode de contours convexes avec l'heuristique de Akl-Toussaint **) :

• les x min, xmax, y min, ymax
• mais aussi les x+y et x-y min et max

Attention, par contre il peut se faire que certains points soient confondus (le point xmin peut aussi être le point ymin, ou ymax, ou x-y min....).

Mais une fois eliminé les points redondants, on a donc de 3 à 8 points determinant de 2 à 5 axes.

Il suffit alors de construire des histogrammes sur chacun des axes avec M bins, puis d'explorer ces 2 à 5 histogrammes pour connaître le plus "équitablement" réparti.



Et, si on veut raffiner, on peut explorer l'intervalle entre cet axe et les 2 les plus proches...



** : j'avais publié sur ArxiV un article là-dessus : http://arxiv.org/pdf/1304.2676.pdf

[wiwaxia]

Bonjour,

Je reviens à la question posée après de nombreux et longs détours, tant sont variées les réponses que l'on peut donner.

1°) Le choix spontané des deux points les plus éloignés m'a paru un peu léger, leur disposition pouvant être totalement différente de celle des 98 autres points: la partition qui en découle n'a de sens que si les deux centres (A) et (B) sont placés dans deux zones relativement denses mais convenablement éloignées, aux extrémités d'un nuage allongé.
Les hyperboles évoquées constituant un faisceau orthogonal à celui des ellipses de mêmes foyers, j'ai cherché le moyen de déterminer rapidement, par une méthode statistique, les caractéristiques (centre, axes, foyers) de l'ellipse que l'on peut associer à un nuage de points allongé, et de densité régulière.
https://fr.wikipedia.org/wiki/Covariance

La méthode de la droite des moindres carrés s'enlise dans des calculs d'une lourdeur outrancière, tandis que celle de la droite des moindres rectangles conduit sans difficultés aux résultats cherchés (les foyers A et B), parce que les coordonnées (x_i, y_i) y sont alors traitées d'une manière symétrique (ce qui est conforme à l'intuition).

Une telle démarche - c'est son défaut majeur - se révèle totalement inadaptée:
- dans le cas d'une distribution des points à contour circulaire ou carré (l'excentricité est alors quasi-nulle, et les foyers très proches: AB<< Sigma(x) et Sigma(y) ,dispersions de x et y); (*)
- et lorsque le nuage présente plus de deux zones de forte concentration.

(*) le retour aux points les plus éloignés est alors une échappatoire.

2°) Une autre méthode, totalement différente, est envisageable quelles que soient les anomalies de concentration présentes dans le nuage de points, mais au risque de perdre tout contrôle sur le nombre et la forme des sous-ensembles discernables.
On associe au nuage:
a) la somme des inverses carrés de toutes les distances présentes: A = S_0<i<j<=N(d_ij^-2) = S_{i=1 à N-1}S_{j=i+1 à N}(d_ij^-2) ,
b) la somme des carrés de toutes les distances présentes: B = S_0<i<j<=N(d_ij²) = S_{i=1 à N-1}S_{j=i+1 à N}(d_ij²) ;
ce qui permet ensuite de calculer pour chacun des points la fonction:
U_i = (A^-1)×S_{0<j<=N, j<>i}(d_ij^-2) - (B^-1)×S_{0<j<=N, j<>i}(d_ij²) .
La moyenne étendue au nuage de tous les termes ainsi définis est nulle, parce que l'on a:
S_{i=1 à n}(U_i) = (A^-1)×(2A) - (B^-1)×(2B) = 0 , chacun des couples (i, j) intervenant deux fois dans les sommations effectuées.

Deux raisons justifient le choix de l'exposant et de l'inverse:
a) la rapidité optimale du calcul, puisque (d_ij²) est le premier terme obtenu lors de la recherche de la distance euclidienne; (**)
b) une variation de (U_i) aussi rapide au voisinage les plus petites distances que des plus grandes, ce qui laisse espérer une répartition des points raisonnablement uniforme sur le domaine [U_min ; U_max], et facilitera l'attribution des couleurs. (***)
(**) argument peut-être contestable ...
(***) là, il faut sans doute faire des essais.

Une telle démarche, conçue pour des concentrations de points hétérogènes, présente un défaut prévisible: dans le cas d'une répartition uniforme, les points de couleurs différentes risquent d'apparaître très mélangés.

[souviron34]

Bonjour,

Salut

Deux raisons justifient le choix de l'exposant et de l'inverse:
a) la rapidité optimale du calcul, puisque (d_ij²) est le premier terme obtenu lors de la recherche de la distance euclidienne; (**)

J'ai comme un doute..

Car tu dis :

2°) Une autre méthode, totalement différente, est envisageable quelles que soient les anomalies de concentration présentes dans le nuage de points, mais au risque de perdre tout contrôle sur le nombre et la forme des sous-ensembles discernables.
On associe au nuage:
a) la somme des inverses carrés de toutes les distances présentes: ,
b) la somme des carrés de toutes les distances présentes: .

Ce qui fait un algo au minimum en O(N²)....

Optimalement, on devrait être proportionnel à un tri ([O(N logN), non ?? ...

[wiwaxia]

A propos de

la rapidité optimale du calcul, puisque (dij2) est le premier terme obtenu lors de la recherche de la distance euclidienne;

... J'ai comme un doute ... Car tu dis : ...

On associe au nuage:
a) la somme des inverses carrés de toutes les distances présentes: A = S0<i<j<=N(dij-2) = Si=1 à N-1Sj=i+1 à N(dij-2) ,
b) la somme des carrés de toutes les distances présentes: B = S0<i<j<=N(dij2) = Si=1 à N-1Sj=i+1 à N(dij2) ;

Ce qui fait un algo au minimum en O(N²)....

Optimalement, on devrait être proportionnel à un tri ([O(N logN), non ?? ...

Je m'en tenais à l'énoncé initial du problème (100 points, ce qui n'est pas insurmontable), et me préoccupais du nombre minimal d'opérations à effectuer: quitte à utiliser une puissance quelconque de (d_ij), autant s'en tenir à son carré, pour les raisons indiquées ... et à défaut d'une amélioration décisive du délai de réalisation du programme, c'est le calcul le plus simple.
Ce problème m'intéresse en raison de ses prolongements graphiques, et je regarderai l'évolution du temps de calcul en fonction de (N) - loin de moi l'idée de mettre en doute la proportionnalité en (N²) ! Je voudrais simplement voir jusqu'où il est possible d'aller dans un délai raisonnable.

Tu as eu raison de pointer la longueur de l'algorithme: il devient sans doute inutilisable au-delà de plusieurs milliers de points, et il ne me serait alors pas venu à l'esprit de l'envisager.

[sbeaulieu]

Bonjour,

Voici la représentation graphique d'une solution éventuelle.
- Créer une zone englobant tous les points.
- Insérer autant de cercle que de groupe.
- Rechercher les points inclus dans les cercles.
- créer un polygone avec les points les plus proches du cercle.
- Utiliser les sommets des polygones pour déterminer a quel groupe doit être associé les points orphelins.
Je pense que cet algorithme serait efficace pour certaines problématiques, le temps me manque mais c'est un sujet intéressant.

Cdt.

[olibara]

Merci a tous pour cette effervescence intellectuelle

Et effectivement le problème n'est pas trivial et la solution a choisir peut a mon avis etre affectée par la diposition de base des points

En pratique il s'agit d'un probléme d'affectation lié a un problème de TSP

L'idée c'est une collecte de n adresses avec c chauffeurs n <= 100; c=3
Sachant que physiquement un chauffeur peut faire entre 30 et 40 adresses sur une journée et que tous les points sont dans un perimetre qui peut etre couver par un chauffeur en une journée

L'idées est de distribuer efficacement les adresses par chauffeur pour repartir la charge et minimiser le Kilométrage total (la distance vol d'oiseau est une approche acceptable)

[tbc92]

Présenté ainsi, le besoin n'est plus du tout le même. Et on est maintenant dans un cadre très classique. C'est exactement le problème du voyageur de commerce.


Quand tu présentais cela comme des regroupements de points, on avait envie de bâtir des cercles , maintenant, on veut bâtir des lignes ...

Imagine les 99 points suivants :
x = 1 et y de 1 à 33
x = 5 et y de 1 à 33
x = 10 et y de 1 à 33

En raisonnant en proximité de groupe, on n'a pas envie de faire un groupe pour chaque ligne verticale, le point du bas étant très loin du point à l'autre extrémité de la ligne.
Mais en raisonnant 'Transport', nos 3 lignes sautent aux yeux.

[olibara]

@tbc92 je ne vois pas vraiment ce que tu veux dire

Mais ce qui est certain c'est que ce n'est pas un simple TSP (Travelling Salesman Problem)

Une simple résolution TSP permettrait de calculer le trajet optimum pour parcourir les 100 point en un seul circuit et j'ai d'ailleurs un algo codé en C# qui fait ca asser bien

Mais ici, ici il faut partitionner les 100 points en trois groupe pour calculer 3 circuit dont la somme serait optimale (je ne dis meme pas la plus optimale)

[anapurna]

salut

un truc qui ressemble fortement a ta recherche

ici

[tbc92]

Ou un autre sujet posté récemment ici, très comparable à ta demande :
http://www.developpez.net/forums/d15...s-d-ouverture/

[wiwaxia]

Bonjour,

La reformulation de la question change effectivement la nature du problème:

... L'idée c'est une collecte de n adresses avec c chauffeurs n <= 100; c=3
Sachant que physiquement un chauffeur peut faire entre 30 et 40 adresses sur une journée et que tous les points sont dans un périmetre qui peut être couvert par un chauffeur en une journée ...
L'idée est de distribuer efficacement les adresses par chauffeur pour répartir la charge et minimiser le kilométrage total ...
... il faut partitionner les 100 points en trois groupes pour calculer 3 circuits dont la somme serait optimale ...

Il s'agit désormais de déterminer 3 circuits fermés, de longueur totale minimale et partant de l'entrepôt, et non plus de regrouper les points autour de zones de forte densité - quoique leur proximité naturelle ne soit pas étrangère au nouvel énoncé; tu as noté que selon les cas, un type de solution peut apparaître plus ou moins approprié.

... effectivement le problème n'est pas trivial et la solution à choisir peut à mon avis être affectée par la disposition de base des points ...

Deux procédés paraissent envisageables.

A) Si les points recouvrent un domaine relativement allongé (ce qu'un graphique montre immédiatement), la méthode des hyperboles (qu'elles soient construites sur les points les plus éloignés, ou sur la droite des moindres rectangles) doit conduire, après un ajustement convenable, à des résultats satisfaisants.

Et en y réfléchissant (et compte tenu de ma propension pour les complications inutiles ) une simplification radicale s'impose: tout nuage de points à contour elliptique, de densité uniforme et s'inscrivant dans un rectangle de dimensions (L) et (h<L) peut être partagé parallèlement au petit axe en trois zones rectangulaires de largeurs respectives (0.37*L, 0.26*L, 0.37*L), et contenant chacune des nombres voisins de points (je vous épargne l'origine des valeurs numériques).

Les effectifs respectifs (N₁, N₂, N₃) sont modulables par déplacement des frontières précédentes (rien ne remplace un examen visuel du graphique !), et le procédé reste applicable au cas d'une distribution quasi-circulaire, inscrite dans un carré - quoique l'absence d'une direction privilégiée puisse devenir problématique).

La méthode de la droite des moindres rectangles fournit les directions orthogonales associées au nuage de points; pour les limites des rectangles circonscrits, revoir les remarques pertinentes de souviron34 (28/01/2016): (u) représentant l'inclinaison du grand axe par rapport à (x'x), repérer les points correspondant aux valeurs extrêmes des sommes S = y*cos(u) - x*sin(u) et T = y*sin(u) + x*cos(u) .
Une résolution graphique peut se révéler efficace.

B) Le procédé précédent repose toujours sur la notion de proximité mutuelle, et ne tient pas compte de la position de l'entrepôt M₀(x₀, y₀) , point de départ obligé de tous les circuits de livraison ... c'est pourtant bien la moindre des choses à considérer dans un problème de ce genre !

Soit donc désormais un repère (xM₀y) centré le lieu de l'entrepôt, à priori distinct des (N = 100) points de livraison répartis dans le plan. On partitionne celui-ci en 24 secteurs d'angle (w = 360°/24 = 15°) d'abord par une dichotomie rapide portant sur les signes des coordonnées (x et y >0 ou <0), puis ensuite par une comparaison des rapports (|y|/|x|) aux seuils remarquables (tan(15°), tan(30°), tan(45°), tan(60°) ou tan(75°)). Le dénombrement des points présents dans chaque domaine conduit à un histogramme sur lequel il est aisé de repérer les zones les plus denses, et de les séparer par des limites convenablement placées (au voisinage des secteurs les moins peuplés); un ajustement peut là encore conduire à des effectifs convenables (N₁, N₂, N₃) pour chacun des 3 livreurs.

Le défaut de ce procédé est de ne tenir aucun compte des distances, mais seulement de l'orientation géographique des points de livraison par rapport à l'origine. Les points les plus proches de cette dernière ne seront donc pas définitivement attribués à leur secteur d'origine, mais pourront servir de réserve d'ajustement.
Le cas le plus extrême est celui d'un nuage très étroit, et qui contiendrait l'origine (M₀); l'exploitation de l'histogramme, dont les secteurs seraient vides en quasi-totalité n'aurait plus de sens, et l'on devrait revenir au procédé (A). Il y d'ailleurs fort à parier que les points de livraison borderaient une autoroute ou un cours d'eau, ce qui dénature complètement l'énoncé.

■ Avec l'adaptation au monde réel surgit une difficulté jusque là inapparente (et pour cause) dans la recherche d'une solution optimale.
On peut évidemment se reporter à deux discussions récentes sur le thème du voyageur de commerce avec contraintes, au cours desquelles des intervenants ont apporté des réponses exhaustives.
Je pense toutefois qu'on pourrait s'en tenir aux méthodes précédentes (ou à l'une de leurs variantes) au prix de quelques restrictions supplémentaires, à reporter sur le tracé du nuage de points en utilisant des couleurs ou des symboles (carrés, croix, cercles ...) différents.
Il serait par exemple utile de distinguer:
a) les points très proches de l'entrepôt (M₀), et donc incorporables à n'importe quel sous-ensemble compte tenu de leur faible contribution à la distance totale parcourue;
b) les points rapidement accessibles par une éventuelle voie rapide, à aborder en priorité dans un circuit;
c) les points difficilement connectables en raison d'obstacles topologiques (fleuve, voie ferrée, autoroute, relief, lieu d'embouteillage fréquent ...), à ranger autant que possible dans des circuits différents - à moins qu'un circuit unique suffisamment long ne permette le contournement de l'obstacle.

Il ressort de tout ce qui précède que les algorithmes proposés ne décrivent le système que d'une façon très sommaire, parce que les données se limitent à la liste des coordonnées (x_k, y_k) des (N) points de livraison; on ne peut donc en tirer qu'une image 2D (nuage ou histogramme) assortie de quelques informations, mais dépourvue de valeur décisionnelle. C'est au programmeur qu'il revient de faire un choix conduisant à une solution.

[wiwaxia]

Il m'est venu une autre idée, dont je ne sais pas ce qu'elle vaut.

J'avais par curiosité recherché et trouvé des solutions au problème du voyageur de commerce, il y a longtemps, lorsque je découvrais la programmation; les boucles calculées en quelques minutes reliaient quelques centaines points aléatoirement répartis dans un rectangle, et j'en avais gardé le souvenir d'un défi intéressant, bien que difficile. Je m'étais par la suite désintéressé de la question, compte tenu du nombre délirant de solutions ((N - 1)!/2 = 4.67E155 pour N = 100) sur un domaine fini ]N*D_min ; N*D_max[ , donc des périmètres voisins ne différant en moyenne qu'à partir du 153^me chiffre: le problème était devenu pour moi numériquement inconsistant.

Je savais aussi que de nouveaux algorithmes performants avaient été mis au point, qui permettaient de trouver de bonnes solutions sur des ensembles beaucoup plus vastes; la recherche d'une boucle optimale sur un nuage de 20 à 40 points me paraissait donc aller de soi, c'est pourquoi je me suis concentré sur la partition du nuage.

Voici la question: ne pourrait-on pas inverser les deux étapes de la recherche des trois cycles en procédant comme suit:
a) Déterminer une (ou plusieurs) boucles de 100 points, de périmètre minimal (ou du moins relativement faible), et constituant une solution satisfaisante;
b) Rechercher les trois paires de points consécutifs les plus proches du lieu de l'entrepôt (M₀), dont la connexion à celui-ci entraîne un allongement minimal du parcours total, et qui restent compatibles avec les limites imposées aux trois effectifs (20<= N₁, N₂ et N₃ <= 40) ?

Il s'agirait alors de repérer dans le cycle des (N) points 3 couples (M_iM_i+1), (M_jM_j+1), (M_kM_k'), vérifiant:
■ 0 < i ; i + 19 < j ; j + 19 < k ;
■ k' = k + 1 si (k < N) ou k' = 1 si (k = N) ; k < Min(N + 1 , N + i - 19) [ calculs rapides, à contrôler ] ;
et auxquels correspondraient, par substitution des liens, les allongements respectifs:
L_i = M_iM₀ + M₀M_i+1 - M_iM_i+1 ;
L_j = M_jM₀ + M₀M_j+1 - M_jM_j+1 ;
L_k = M_kM₀ + M₀M_k' - M_kM_k' ;
et pour l'ensemble des 3 cycles, l'augmentation du parcours total: L = L_i + L_j + L_k .

Le nombre de triplets (i, j, k), proportionnel à (N³), est considérablement réduit par les conditions d'espacement qui leur sont imposées; de sorte que l'algorithme décrit, à priori assez lourd, doit pouvoir être exécuté sur un délai raisonnable, d'autant que le nombre (N) de points reste modéré.
L'existence d'une solution ne va pas de soi, dans les conditions de l'énoncé; le seul recours, en cas d'échec, est de diminuer la longueur minimale des cycles (à 18 ou 15, par exemple).