Discussion :

[picodev]

[...]
L'algo ne commence pas avec des théories fumantes qui sortent d'un chapeau

Tu as raison, l'algorithmique ne sort jamais d'un chapeau si on comprend ce qu'on fait et pourquoi on le fait. Si tu n'as pas de notions de base en algo tu ne pourras jamais construire de programmes efficaces. Si tu n'as pas une culture minimum en algo tu ne pourras pas construire de programmes efficients.
Les notions de base s'acquièrent en lisant et en faisant et refaisant les exos classiques jusqu'à devenir intime avec les objets manipulés et les manipulations basiques. La culture ensuite, ma foi, elle s'acquiert en étant curieux et en lisant, puis en comprenant la démarche.
L'expérience n'apporte pas grand chose de plus que la capacité à faire de bons choix plus tôt possible en connaissant les possibilités pour résoudre un problème donné avec les contraintes particulières.

Pour en revenir à ton problème, on peut le décrire ainsi →

• on a un ensemble V de nœuds
  chaque nœud possède au moins une propriété : ses coordonnées dans un plan
  le nombre de nœuds est une puissance de 2 moins 1;
• un arête reliant deux nœuds aura un poids définit par W(u,v)=distance_euclienne(u.coordonnées, v.coordonnées);
• tu dois construire un arbre binaire complet utilisant tous les nœuds dont la somme des poids des arêtes doit être minimisée qui a la propriété supplémentaire que sa représentation graphique soit planaire.

Avec un peu de réflexion (et très rapidement) on peut penser à plusieurs approches :

• diviser pour régner/programmation dynamique → peut-on raisonner en fonction de problèmes identiques de tailles inférieures ? est-ce que résoudre ce problème revient à résoudre deux problèmes de taille 2^n-1-1 ? Les cas n<3 étant triviaux.
• graphe → ça sent fort l'arbre couvrant avec des contraintes supplémentaires (planéarité, de type binaire complet), peut-on chercher du côté de chez Prim ou Kruskal ?
• graphe → de la même manière ça sent aussi le dessin planaire d'un graphe, peut-on utiliser les algos Tarjan Hopcroft de reconnaissance ? doit-on par exemple essayer de construire un arbre binaire complet en reliant les feuilles (y compris par des arcs courbes) pour avoir un graphe triangulaire ?
• graphe, algo géométriques → cette dernière remarque m'amène à la triangulation de Delaunay. Si tu construis un graphe triangulaire et que tu cherchais un arbre couvrant ? sans doute une autre piste à explorer …
• idée à la con → si tu construis un arbre couvrant minimum, que se passe-t-il si tu en détermines les centres (le ou les nœuds qui sont équidistants des extrémités) ? Aurais-tu de bons candidats de racines pour commencer la construction de ta solution ?
• la liste n'est pas exhaustive loin de là … à toi d'imaginer d'autres approches

Les pistes sont nombreuses, les contraintes fortes, surtout en compétition où tu as une limite aux temps de refléxion et d'implémentations sans compter les limites matérielles (1s de temps cpu, 256MB de mémoire, …).

Néanmoins c'est un très bon exercice qui va te permettre d'aborder de nombreux concepts avec lesquels tu n'es sans doute pas familier mais tu vas découvrir un monde assez magnifiques
D'autant plus qu'on ne te demandes pas un algo efficient mais juste un minimum efficace …

[bm]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#                  __ h
#            _ d _/    
#                 \__ i
#      b __/       __ j
#      /   \ _ e _/    
#  a __           \__ k
#                  __ l
#      \     _ f _/    
#      c __/      \__ m
#                  __ n
#          \ _ g _/    
#                 \__ o
#                      
#
# Avec une numérotation :
# a,b,c,d,e,f,g = 0,1,2,3,4,5,6
# h,i,j,k,l,m,n,o = 7,8,9,10,11,12,13,14
#
# Cela donne 8 branches pour N=4 :
# 0,1,3,7
# 0,1,3,8
# 0,1,4,9
# 0,1,4,10
# 0,2,5,11
# 0,2,5,12
# 0,2,6,13
# 0,2,6,14

Comment généraliser le codage des branches à l'ordre N pour passer à l'ordre N+1 ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
N=3
0,1,3
0,1,4
0,2,5
0,2,6

Indice : La transposition de matrice

N=10
La ligne 444 -> 0 2 6 13 28 58 118 237 476 954
N=20
La ligne 444 444 -> 0 2 6 13 28 58 117 235 472 945 1891 3783 7567 15135 30271 60544 121090 242181 484364 968730

[bm]

Ordonner les segments sécants et non sécants ne m'a pas plus avancé.



Avec des cas particuliers pour N=3,4

Des distributions de points sont compatibles, d'autres ne le sont pas :



En voilà un qui va au bout sans intersection :






(12 minutes de calcul )



(29 secondes de calcul - N=5 peut aboutir )

[bm]

Décomposition en plusieurs nuages à partir de N=5

[bm]

C'est le nombre de points qui rend possible , l'existence d'un arbre optimum.



N=8 , et faudra beaucoup plus de points pour obtenir un binaire sans intersection

[picodev]

Pourquoi n'essayes-tu pas de partir d'une triangulation ?

[bm]

Pourquoi n'essayes-tu pas de partir d'une triangulation ?

L'arbre est construit de gauche à droite.
Ce qu'il faut trouver c'est une grille de point de densité variable.



L'algo "tout terrain" n'existe pas.
Il y avait 7 nains pour plaire à Blanche Neige.

[picodev]

Peux-tu expliquer un peu mieux ? Je ne comprends pas le sens de ta remarque.
Avec une triangulation tu n'as plus le problèmes d'arêtes qui se coupent, même si cela ne te donne pas forcément la meilleure solution.

[bm]

Ci-dessus 1 point va en chercher 2 ( les plus proches en distance ).
C'est déjà une optimisation ou triangulation.

Un grille régulière, du style feuille de classeur à petit carreaux, ne donnera aucun
arbre binaire.

C'est un dallage spécifique, qui donnera un tracé ( sans faille ) pour un arbre binaire.

[picodev]

Ci-dessus 1 point va en chercher 2 ( les plus proches en distance ).
C'est déjà une optimisation ou triangulation.

Ce n'est pas une triangulation … je te laisse lire cette partie de l'article de wikipedia sur l'application de la triangulation de Delaunay aux arbres couvrants de poids minimum dans le cas euclidien
Cela te mettra peut-être la puce à l'oreille.

Un grille régulière, du style feuille de classeur à petit carreaux, ne donnera aucun
arbre binaire.

C'est un dallage spécifique, qui donnera un tracé ( sans faille ) pour un arbre binaire.

Je te renvoie à nouveau vers le lien donné ci-dessus.

[bm]

Wikipédia vulgarise des connaissances sous forme de compte rendu vague et décevant.

Les algo ne se montent pas comme des chevaux dressés par l'écurie Wikipédia.

[picodev]

Tsss ... je ne voulais que te redonner une piste pour te sortir de l'impasse tu sais. Ensuite c'est toi qui vois.
Bon courage

[tbc92]

Pour moi, ça me fait penser au dessin 'classique' de poumons.
Et du coup, voici une solution.

Tous mes points sont dans le rectangle : 0<x <1 ; 0<y<1 et disons qu'on a 255 points pour la facilité des notations.
Pour l'explication, j'ajoute un point R ( x= 0.5, y=1) ( le haut de la trachée si je me souviens de mes cours d'anatomie)
Je choisis un point parmi mes 255 points. Je peux prendre un point au hasard, et l'algorithme marchera, je peux aussi prendre le point le plus proche du centre de gravité des 255 points, pour avoir un dessin qui ressemble au dessin de poumons, et je peux aussi prendre le point le plus proche possible de mon point R, si je veux avoir un arbre de longueur totale relativement courte.
Soit A ce point, ce sera la racine de mon arbre.
Pour les 254 points M restants, je calcule l'angle (AR,AM) , et je trie mes points selon cet angle. Les 127 premiers points détermineront un demi-arbre (le poumon gauche) et les 127 autres détermineront l'autre demi arbre.

Et en répétant l'opération de façon récursive sur chaque partition, on obtient un arbre binaire, sans croisement, mais sans assurance d'avoir trouvé la longueur la plus courte.

Pour détailler un peu, à l'étape 2, on a notre point A. Dans le demi-arbre de gauche, on cherche le point B le plus proche de A. Pour tous les points M de ce demi-arbre, on calcule l'angle (BA,BM), on trie les points selon cet angle ... ... etc, etc, et idem sur l'autre demi-arbre.


L'algorithme marche pour des arbres binaires, mais aussi pour des arbres 'ternaires' ou 'quaternaires' ou de tout ordre.

[bm]

on obtient un arbre binaire, sans croisement

tbc92 :
Rester en dessous de l'objectif n'est pas une défaite.
Concernant ta méthode, ajoute une image du tracé de cet arbre.

dailymotion.com/video/x4m27mc_italie-un-camion-fait-demi-tour-au-milieu-de-l-autoroute_auto

La ligne ci-dessus se voit avec firefox , mais pas avec chrome.

[tbc92]

Je ne vais pas pouvoir travailler plus sur cet algorithme avant demain soir, voire mercredi ; donc pas de dessin à venir d'ici là.
En fait, je pense qu'il y a une petite erreur. Je dis qu'on peut choisir un fils 'au hasard' dans chaque demi-arbre, et qu'il convient de choisir le fils le plus proche du père. J'ai un doute sur ce point. Si chaque demi-arbre a 255 ou 127 ou 63 points, pas de problème, ça va marcher.
Idem, si on est au dernier niveau, ça va marcher.
Mais si chaque demi-arbre a 7 , voire 15 points, ce n'est pas garanti. La solution qui marchera à coup sûr, c'est de réutiliser l'idée du balayage circulaire. Les points M sont classés selon l'angle (AR,AM), et il faut prendre comme fils le point médian (celui qui arrive au milieu quand on classe sur l'angle croissant) .

Ca va rallonger la longueur moyenne de chaque branche, mais c'est le prix à payer pour avoir un algorithme simple.

[wiwaxia]

Bonjour,

Je planche depuis plusieurs jours sur ce sujet intéressant, et crois avoir trouvé une démarche permettant d'accéder facilement à une série de solutions:
1) Localiser l'isobarycentre (G) du nuage;
2) Repérer les 3 points les plus proches;
3) Classer les 15 - 3 = 12 points restants selon l'ordre croissant de l'angle polaire t = (u_x , GM_k) ;
4) Appliquer les 4 triplets de points consécutifs ainsi obtenus (1, 2, ,3), (4, 5, 6) ... (10, 11, 12) aux extrémités du graphe (arêtes rouges):
(4, 8, 9), (5, 10,11), (6, 12,13), (7, 14,15) qui, de cette façon, ne se recouperont pas.
D'autres découpages sont possibles, en partant d'un autre point, par ex:
(2, 3, 4) ... (11, 12, 1) ou (3, 4, 5) ... (12, 1, 2)
5) Placer les 3 points initialement mis à part aux sommets encore disponibles de l'arbre (1, 2, 3); vérifier l'absence d'intersections (ici peu probables).


À chaque groupe de 4 triplets correspondent théoriquement 3⁴*6 = 486 arbres différents, abstraction faite des éventuelles intersections des arêtes; il devrait subsister un bon paquet de graphes planaires.

Il est par ailleurs bien possible que l'on puisse isoler au départ des points autres que ceux précédemment définis, pourvu qu'ils ne soient pas trop éloignés de (G).

PS: Je découvre en postant ce message que tbc92 a exprimé une idée assez proche:

La solution qui marchera à coup sûr, c'est de réutiliser l'idée du balayage circulaire. Les points M sont classés selon l'angle (AR,AM), et il faut prendre comme fils le point médian (celui qui arrive au milieu quand on classe sur l'angle croissant) .

PS2: Je me suis demandé depuis si la méthode ne pourrait pas être étendue à n'importe quel point du nuage, et deux de ses plus proches voisins, le taux de réponses conformes (sans chevauchement des arêtes) étant d'autant plus faible que les 3 points choisis sont plus éloignés de (G). La longueur totale serait vraisemblablement plus élevée qu'auparavant.

[bm]

Quelque soit la méthode il faut un nuage de points assez gros.
Les langages de programmation sont équivalents.

Avec 2048 points ( total du nuage et N=10 ), c'est le grand côté de l'arbre qui diverge :



Pour un arbre N5, il faut 3 ordres de points en plus ( N8=255 )





La fin de l'arbre ( feuille ) consomme plus de points.

[tbc92]

Avec la méthode exposée plus haut, voici un résultat :



Au moment de la génération des points ( 127 ici), je ne vérifie pas la clause ' jamais 3 points alignés' D'où parfois une certaine ambiguïté sur certains segments.
Pour chaque niveau, je fais un 'balayage circulaire' pour constituer des groupes.
Sauf pour le dernier niveau. Quand j'ai un groupe de 3 points que je dois attacher à un point père Z, je prends le point P le plus proche de Z, qui va être rattaché à Z, puis les 2 autres seront rattachés à P.

Le trait bleu vertical ne devrait pas apparaître si on s'en tient à l'énoncé de départ, mais je l'ai laissé pour la clarté de l'algorithme.
Pour déterminer le point A, je classe les 127 points selon x croissant, et je prends celui qui arrive au rang 64. On a donc 2 demi-arbres : les 63 points de gauche, et les 63 points de droite.
Le point R est à la verticale de A.

Pour chaque point P du demi-plan de gauche, je calcule l'angle (AR, AP) et je trie selon cet angle Je fais en sorte de mesurer les angles entre 0 et 360°. Le point N arrive donc en premier, ( angle = 5° environ) et le point M arrive en dernier (angle = 179°), et celui qui arrive au milieu sera choisi comme fils de A. La demi-droite AB ( prolongée en rouge sur le dessin) sépare notre demi-arbre en 2 groupes de 31 points chacun.
Et ainsi de suite.

Pour l'étape suivante, pour effectuer le balayage circulaire, je vais prendre comme droite de référence la droite BA et non plus la droite AR...

Edit : J'aurais voulu enlever la 2ème image ...mais je n'y arrive pas.

[bm]

Edit : J'aurais voulu enlever la 2ème image ...mais je n'y arrive pas.

Supprimer image :
Option supplémentaire / Gérer image

[wiwaxia]

Multiplier le nombre de points constitue une fuite en avant stérile, en raison de la croissance incontrôlable des possibilités de connexion; le nombre d'arbres binaires constructibles sur 15 points est déjà si élevé (15!/2⁷ , soit env. 1.02E¹⁰ - en triant tous les doublets équivalents du type <i, j>/<j, i>) qu'il laisse peu d'espoir de trouver des graphes planaires par une énumération méthodique ou un tirage aléatoire - à moins d'user de restrictions drastiques.
Et c'est de toutes façons sortir du sujet, qui impose 15 points de positions déterminées.

La méthode décrite précédemment a fourni les résultats suivants:
1°) la liste des distances (GM_k):



2°) la liste des points partiellement ordonnés selon l'ordre croissant de leur angle polaire:



3°) les graphes planaires envisageables à partir de cette sélection:

a) série (1): aucun graphe planaire envisageable, en raison des 4 points d'intersection des triangles (1, 2, 3) et (4, 5, 6) - notation abrégée. Ce critère d'élimination inattendu pourrait être inclus dans une recherche plus générale, basée sur la décomposition du nuage de points en 5 triangles.



b) série (2): solutions à foison - il suffit de se baisser pour les ramasser; il y a ainsi 3⁴ arbres planaires du type de celui représenté, par déplacement de l'avant-dernier sommet, dans chaque triangle; d'autres séries sont encore envisageables - mais pas toutes.



c) série (3): les contraintes sont ici plus sévères, mais il existe encore des solutions, ainsi celle ci-dessous.



Cherchez, et vous trouverez.

D'autant qu'en ce qui concerne le choix des 3 premiers points, rien n'interdit de partir d'un triangle quelconque pourvu qu'il ne contienne aucun autre point du nuage (ils sont assez faciles à trouver - il y en a 228).