Discussion :

[bm]

bonjour,

Je cherche une méthode ou plusieurs pour décomposer un nuage de points en arbre binaire.
C'est un exo d'une olympiade Fario 2016 :



J'ai vu beaucoup de généralités sur des arbres.
Pour extraire des data et construire des arbres, c'est très pauvre dans ce domaine.

@+

[Flodelarab]

Bonjour

On dirait un codage de Huffman.

Tu prends les 2 plus petites distances, puis les 2 nouvelles plus petites, puis les 2 nouvelles plus petites, puis les 2 nouvelles plus petites, puis les 2 nouvelles plus petites, puis les 2 nouvelles plus petites...

[bm]

Huffman, pas facile de coder ..

Je vais partir d'un arbre fixe et placer les points de manière aléatoire.
C'est la non intersection du segment N ,avec les N-1 précédents, qui validera la position de ce point.

Valider la non intersection de [AB] avec [CD] demande déjà pas mal de paramètres de position

[picodev]

Bonjour,
tu sais donner au moins un lien vers le sujet à défaut de le copier est une bonne chose.

À la base j'ai vu ton schéma et je me suis dit «tient, une sorte d'arbre k-d», puis je me suis dit cherchons quand même l'énoncé pour voir de quoi il s'agit.

J'ai trouvé ça ce sujet.

Alors par exemple, l'information que l'arbre doit être complet est une information importante … celle d'avoir à minimiser la longueur total de fil l'est aussi … que les fils ne se coupent pas (pas de 9-14 avec un 8-13) … et j'en passe comme N≤10.

[bm]

C'est un exo d'une olympiade Fario 2016 :

http://orac.amt.edu.au/fario/

[picodev]

Bon, nous parlons donc bien du même sujet.

Je peux te donner les orientations qui me viennent directement en tête face à ce genre de problème. En première approche je me dis qu'un arbre binaire complet est aisément représenté sous forme de tableau →

• racine à l'indice 1
• fils gauche en 2*i où i est l'indice du père
• fils droit en 2*i+1, i étant l'indice du père

Je place la racine en 1 pour simplifier un tout petit peu les calculs, mais on peut tout aussi bien prendre pour convention indice de la racine en 0.

Un nœud contient comme informations (algo en pseudo c) :

Code :

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

1
2
3
4
5
6
7
struct node {
  int id; // l'id du nœud
  int x; // abscisse
  int y; // ordonnée
}
 
struct node tree[1<<N];

Le problème est symétrique → en échangeant les fils gauche et fils droit on ne change en rien le candidat à la solution.

Le problème consiste donc à pouvoir construire des arbres respectant les contraintes et de cette suite d'arbres garder celui qui minimise les longueurs de fils.

Il faut donc se balader dans les différentes permutations possibles → danger d'explosion combinatoire.
On peut le faire de différentes manières. Soit on considère le tableau dans son entier, on génère des permutations, on vérifie ensuite que les contraintes ne sont pas violées (approche top bottom). Si une contrainte est violée à un niveau de l'arbre on pourra peut être sauter relativement tôt une bonne partie des permutations (pas assuré). Par exemple, en choisissant comme racine 1, fg 2 et fd 3 on va sauter toutes les permutations commençant par 12 car deux est isolé et il n'y a aucun autre nœud que l'on peut rattacher à 2 sans violer de contraintes.
Soit on commence par créer les combinaisons par étages en commençant par le bas et en construisant récursivment l'arbre vers le haut. C'est juste une autre façon de parcourir les permutations. Une idée à tester.
Le problème avec ce genre d'approche est l'explosion combinatoire l'espace de recherche peut être suffisamment grand pour dépasser le temps imparti.

Comme tu n'est pas obligé de trouver une meilleure solution, tu peux essayer des algos d'approximations.