Arbre binaire et nuage de points

[Abuche]

Bonjour,

Dans un nuage de points, qu'elles sont les méthodes de construction d'un arbre binaire ?
C'est des maths discrètes et algorithmiques des olympiades FARIO 2016 :

http://orac.amt.edu.au/fario/16/problems_fr.pdf ( problème 3 )

Avec N=10 et 1023 points pour un arbre, je suppose qu'il y a au moins le double de points
parce que la répartition des points influence la résolution.

Jusqu'à N=5 , la programmation avec python prend quelques minutes:



@+



--------------------------------------

C'est l'arbre binaire qui modélise le feu de forêt , et la frappe de la météorite plus grosse que
la balle de ping pong.

[fatal_error]

hello,

spanning tree en anglais, et en francais arbre couvrant de poids minimal (https://fr.wikipedia.org/wiki/Arbre_cou ... ds_minimal)
en particulier https://fr.wikipedia.org/wiki/Algorithme_de_Kruskal est assez simple de compréhension

une résolution de l'énoncé du pb 3 est qqch de l'ordre de :
1) je cree mon graphe avec mes noeuds numérotés.
2) je calcule la longueur de chacune des aretes
3) j'applique kruskal avec:
creerEnsemble(v) == function(v){

Code: Tout sélectionner

var E = function(v){//v est le noeud du graph représenté par son numéro
 this.min = v;
 this.union = function(u){
  this.min = u<this.min?u:this.min;
 }
 this.find = function(u){
  return this.min == u;
 }
}

return new E(v);
}

maintenant,
comme N == 10 au plus, tu peux construire un graphe NxN (représenté par matrice symétrique), ca fait pas bcp de multiplications, ca devrait etre immédiat.

je ne comprends pas le calcul du score,

[Abuche]

N=10 , cela fait 1023 points et 512 branches pour finir un arbre

La répartition des points n'a pas d'importance avec N=4 mais le devient avec N=10
Je construit et déconstruit les branches sur un ensemble de points plus grand que 1023
Le problème est de choisir les points pour que aucune branche ne coupe une autre

Algorithme_de_Kruskal : tous les algo dispose à priori de points bien placés qui sous entende
que le graphe existe - après un tirage de points aléatoire, il y a de grande différence et des
constructions impossible ..

Pour le score, il doit y avoir des fichiers de points, plus ou moins grand:
fic1 : combien de candidats arrivent avec N=3,4,5 ( à partir de 6 c'est impossible )
fic2 : idem ( N=6,7 )
fic3 : idem ( N=8,9
fic4 : idem ( N=10)

J'utilise python et numpy pour des tirages aléatoires

[Doraki]

fatal error on demande de mettre un arbre binaire complet, qui de plus doit être "planaire" (ses arêtes ne se croisent pas). Kruskal donne un arbre quelconque.

De plus ils ne demandent pas de construire la solution la moins chère (par contre une meilleure solution donnera un meilleur score)

[Abuche]

Un arbre binaire quelconque est optimisé en distance, pour une croissance la plus longue possible en nombre de segments.

Aller jusqu'à N=8,9,10 , c'est déjà avec un algo qui fait des bons choix, et passe par des segments les plus courts possibles. Tout est lié avec un arbre binaire.



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

[fatal_error]

oui doraki merci pour precision jai meme ps percuté que arbre binaire ca comprenait binaire... pour le coup une idée mais trop empirique et pas assez reflechie als dodo