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.

[tbc92]

Une exploration des combinaisons possibles semble une voie, mais pour éliminer au plus vite toutes les combinaisons non-valides, tu peux faire un pré-traitement.
Tu commences par recenser tous les couples de segments qui sont incompatibles.
Sur l'exemple donné, si tu as le segment (4,15) dans ton arbre, alors les segments (10,13),(11,13),(12,13) et plein d'autres deviennent interdits, car ça ferait un croisement.

[bm]

Avec 15 points :
15x15 = 225
225 -15=210
210/2=105

105 segments possibles

C'est cette réduction des relations incompatibles entre segments qui rend
la résolution logique mais terriblement longue !

Cela doit pouvoir aller plus vite avec des librairies ad hoc telle que pandas
de python , mais je débute avec le big data.

[picodev]

Tu peux effectivement partir sur une autre idée comme créer un graphe complet et cherche un arbre couvrant de poids minimum (algo kruskal ou prim) respectant la contrainte qu'aucune arête n'en croise une autre sur le graphique.

[bm]

algo kruskal :

Avec 15 noeuds et 14 arêtes, c'est le résultat final voulu pour un arbre binaire

Comment déclarer un graphe plus grand avec les 15 points et le poids (ou distance ) entre les points ?
Est ce du dessin à main levée pour démarrer un algo kruskal ?

Le K12 à 66 arêtes :

https://fr.wikipedia.org/wiki/Graphe_complet

Code python :

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
parent = dict()
rank = dict()
 
def make_set(vertice):
    parent[vertice] = vertice
    rank[vertice] = 0
 
def find(vertice):
    if parent[vertice] != vertice:
        parent[vertice] = find(parent[vertice])
    return parent[vertice]
 
def union(vertice1, vertice2):
    root1 = find(vertice1)
    root2 = find(vertice2)
    if root1 != root2:
        if rank[root1] > rank[root2]:
            parent[root2] = root1
	else:
	    parent[root1] = root2
	if rank[root1] == rank[root2]: rank[root2] += 1
 
def kruskal(graph):
    for vertice in graph['vertices']:
	make_set(vertice)
	minimum_spanning_tree = set()
	edges = list(graph['edges'])
	edges.sort()
	#print edges
    for edge in edges:
	weight, vertice1, vertice2 = edge
	if find(vertice1) != find(vertice2):
	    union(vertice1, vertice2)
	    minimum_spanning_tree.add(edge)
 
    return sorted(minimum_spanning_tree)
 
graph = {
'vertices': ['A', 'B', 'C', 'D', 'E', 'F', 'G'],
'edges': set([
(7, 'A', 'B'),
(5, 'A', 'D'),
(7, 'B', 'A'),
(8, 'B', 'C'),
(9, 'B', 'D'),
(7, 'B', 'E'),
(8, 'C', 'B'),
(5, 'C', 'E'),
(5, 'D', 'A'),
(9, 'D', 'B'),
(7, 'D', 'E'),
(6, 'D', 'F'),
(7, 'E', 'B'),
(5, 'E', 'C'),
(15, 'E', 'D'),
(8, 'E', 'F'),
(9, 'E', 'G'),
(6, 'F', 'D'),
(8, 'F', 'E'),
(11, 'F', 'G'),
(9, 'G', 'E'),
(11, 'G', 'F'),
])
}
 
print kruskal(graph)

[picodev]

algo kruskal :

Avec 15 noeuds et 14 arêtes, c'est le résultat final voulu pour un arbre binaire

Comment déclarer un graphe plus grand avec les 15 points et le poids (ou distance ) entre les points ?
Est ce du dessin à main levée pour démarrer un algo kruskal ?

Le K12 à 66 arêtes :

https://fr.wikipedia.org/wiki/Graphe_complet
[...]

Je ne comprends pas trop ce que tu veux faire ou ce que tu essayes de dire.
L'idée de base est de construire un graphe complet. Pour N=4 tu auras V=2⁴-1=15 nœuds. Tu vas donc créer le graphe complet K₁₅ qui contient 15 nœuds et E=15*14/2=105 arêtes. Les arêtes sont pondérées, leur poids est donnée par la distance des nœuds arrivé et départ. Le graphe est non dirigé.
En gros, l'algo de Kruskal sélectionne les arêtes par poids croissant et la garde si elle ne forme pas un cycle. Tu devras modifier l'algorithme pour qu'en plus l'arête considérée soit gardée si non seulement elle ne forme pas un cycle mais de plus si elle ne coupe pas une arête déjà retenue.
Un fois l'arbre couvrant de poids minimum trouvé tu devras t'assurer qu'il est bien un arbre binaire complet et si ce n'est pas le cas il va falloir continuer la recherche.
Une grosse adaptation quand même.
Je te recommande de d'abord bien comprendre l'algo avant même d'essayer de copier/coller un code de github que tu vas essayer de faire tomber en marche.

[bm]

Tu devras modifier l'algorithme pour qu'en plus l'arête considérée soit gardée si non seulement elle ne forme pas un cycle mais de plus si elle ne coupe pas une arête déjà retenue.

C'est ce que j'ai commencé par mettre au point.
Je vais tester avec N=2,3

[tbc92]

Pour déterminer si 2 segments se croisent, tu peux procéder ainsi.
1. Chercher une équation de la droite AB sous la forme ax+by+c= 0
2. Calculer ax+by+c pour ton point I et ton point J ; si les 2 nombres obtenus sont de même signe, c'est que les 2 points I et J sont dans le même demi-plan, donc le segment IJ ne coupe pas la doite AB. Si ces 2 nombres sont de signe diférents, il faut continuer. Aucun de ces 2 nombres ne peut être nul, car on nous a dit qu'il n'y avait pas 3 points alignés.
3. Recommencer, en inversant les roles de AB et IJ? On cherche donc une équation de la droite IJ sous la forme ax+by+xc = 0
4. Calculer ax+by+c pour A et pour B ... et si ces 2 nombres sont de signes opposés, c'est que nos 2 segments se coupent.

[bm]

@tbc92:

Passer par équation de droite est bien trop long
Ci-dessous un tirage aléatoire de 4 points A,B,C,D

(64, 31) (19, 89) (95, 7) (38, 56)
Intersection
------------------
(9, 97) (16, 31) (17, 35) (48, 59)
Not intersection
------------------
(10, 60) (61, 27) (61, 38) (75, 28)
Not intersection
------------------
(91, 81) (7, 58) (100, 75) (98, 41)
Not intersection
------------------
(63, 9) (81, 72) (90, 7) (28, 85)
Intersection **** ( graphe)
------------------
(48, 25) (29, 3) (95, 34) (62, 51)
Not intersection
------------------
(51, 55) (1, 23) (20, 1) (28, 79)
Intersection
------------------
(91, 95) (67, 93) (13, 91) (17, 8)
Not intersection
------------------
(68, 1) (72, 0) (57, 2) (35, 79)
Not intersection
------------------
(78, 16) (74, 86) (63, 66) (9, 79)
Not intersection
------------------
(32, 21) (26, 90) (74, 58) (36, 16)
Not intersection

[wiwaxia]

Bonjour,

@tbc92: Passer par équation de droite est bien trop long
Ci-dessous un tirage aléatoire de 4 points A,B,C,D

(64, 31) (19, 89) (95, 7) (38, 56)
Intersection
------------------
(9, 97) (16, 31) (17, 35) (48, 59)
Not intersection
...

C'est juste, mais tu n'indiques rien à propos de ta propre méthode ... à moins qu'il ne s'agisse d'un contrôle graphique, beaucoup trop lourd à mettre en oeuvre sur l'ensemble des contrôles à effectuer, et qui ne manquerait pas de caler sur des cas limites vicieux (I très proche de l'un des 4 autres points).

Il y a une alternative simple apparentée à ce que propose tbc92: la comparaison des signes de deux termes, produits scalaires de deux produits vectoriels:

p = (AB×AC)|(AB×AD) et q = (CD×CA)|(CD×CB)

lesquels sont positifs ou négatifs selon que l'intersection (I) se situe à l'intérieur ou à l'extérieur de l'un des deux segments considérés (AB), (CD).
On constate ainsi sur les trois exemples ci-dessous que l'on a:
(p₁ > 0) et (q₁ > 0) , (p₂ > 0) et (q₂ < 0) , (p₃ < 0) et (q₃ < 0) .

Le critère de non-intersection des segments est donc représenté par le booléen: t = ((p>0) OR (q>0)) .

Comme l'on travaille sur un nuage de points coplanaires, donc à priori confinés dans le plan (xOy), les produits vectoriels se réduisent au déterminant des vecteurs considérés; par exemple: (AB×AC) = Det(AB, AC) * u_z .
Les produits scalaires s'expriment alors simplement en fonction des déterminants correspondants;
ainsi: p = (Det(AB, AC) * u_z)|(Det(AB, AD) * u_z) = Det(AB, AC) * Det(AB, AD)
puisque (u_z|u_z) = ║u_z║² = 1 .

[bm]

Re:

C'est le cas I qui est vicieux:
En vecteur
AI = k.AB et CI=m.CD , mais abs(k)>1 ou abs(m)>1 doit rejeter cette solution non conforme

Les solutions conformes sont acceptées avec abs(k)<1 et abs(m)<1

[wiwaxia]

Bonjour,

C'est le cas I qui est vicieux:
En vecteur
AI = k.AB et CI=m.CD , mais abs(k)>1 ou abs(m)>1 doit rejeter cette solution non conforme

Les solutions conformes sont acceptées avec abs(k)<1 et abs(m)<1

Le cas (I) est licite puisque l'intersection des deux droites (AB) et (CD), coplanaires mais généralement non parallèles, se situe à l'extérieur des segments correspondants [AB] et [CD].
En reprenant tes conventions (en soi légitimes, mais qui allongent les calculs et soulèvent des difficultés dans le cas de droites parallèles):
AI = k*AB et CI = m*CD
on obtient ici: k₁ > 1 et m₁ > 1 ;
La permutation sur la même figure les extrémités des segments (A et B d'une part, C et D d'autre part) conduirait à: k'₁ < 0 et m'₁ < 0
(puisqu'alors AI et AB seraient de sens opposés, de même que CI et CD);
on voit au passage que les scalaires (k) et et (m) admettent pour seuils critiques (0) et (1), et non (±1) comme tu l'indiques implicitement:

... Les solutions conformes sont acceptées avec abs(k)<1 et abs(m)<1

Autre erreur, résultant sans doute d'un lapsus: le critère d'intersection de [AB] et [CD] (cas III) s'écrit, en maintenant la même notation:
(k IN ]0 ; 1[) AND (m IN ]0 ; 1[) ou ce qui revient au même: (k*(1 - k) > 0) AND (m*(1 - m) > 0) ;
et comme il s'agit précisément de ce qu'il faut exclure, le critère de non-intersection des arêtes en cause s'écrit:
(k*(1 - k) < 0) OR (m*(1 - m) < 0) .
Les cas limites (k*(1 - k) = 0) ou (m*(1 - m) = 0) sont heureusement exclus par la condition de non-alignement de l'énoncé:

http://orac.amt.edu.au/fario/16/problems_fr.pdf#page=6
Ils ont tous des positions distinctes, et trois signaux distincts ne sont jamais alignés.

Il ressort de tout ce qui précède que l'emploi des coefficient (k) et (m) requiert des calculs inutilement longs.

[bm]

(64, 31) (19, 89) (95, 7) (38, 56)
Intersection
------------------
(9, 97) (16, 31) (17, 35) (48, 59)
Not intersection
------------------

Méthode 1 : la mienne ( 4 fonctions et 80 lignes python )

Méthode 2 : de la critique et aucune programmation comparable

[picodev]

Un peu de réflexion ne ferait pas de mal à ce moment de la discussion je pense.
L'approche utilisée par du principe qu'on va déterminer lorsque le bsoin s'en fera sentir si oui ou non deux segments sont sécants. Bien qu'on puisse utiliser des techniques de mémoïsation pour éviter de répéter certains calculs, il pourrait être intéressant de calculer toutes les intersections pour obtenir une liste de segments sécants, ce qui dans le problème actuel revient à établir une liste d'arrêtes interdite pour chaque arrête. Il existe des algo performants pour ça → l'algo de Bentley–Ottmann ou son extension plus robuste proposée par Bartuschka, Mehlhorn et Naeher.

Références :
la page wikipedia
«Computing intersections in a set of line segments: the Bentley-Ottmann algorithm» Michiel Smid
une implémentation en python puisque tu sembles plus penser en python qu'en algo.
«A robust and efficient implementation of a sweep line algorithm for the straight line segment intersection problem.» U. Bartuschka, K. Mehlhorn and S. Naeher.

[bm]

En effet l'intersection de segment n'est pas le but.
Je commence avec un arbre simple et 7 points
Construit 4 branches et implémente un algo d'intersection entre branche

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
print '----------NUMPY----------'
 
#            _ d 
#      b __/     
#   a__/   \ _ e 
#      \     _ f 
#      c __/     
#          \ _ g 
#                
 
# calcul le chemin des 4 branches
# a,b,c,d,e,f,g = 0,1,2,3,4,5,6
# b1(a,b,b,d)
# b2(a,b,b,e) 
# b3(a,c,c,f)
# b4(a,c,c,g)

Ci-dessous pas d'intersection entre branches donc un arbre binaire résultant :

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
28
Liste de 7 points :
[(879, 311), (466, 62), (339, 435), (21, 975), (140, 481), (228, 907), (407, 956)]
-----------------------------------
(879, 311) (466, 62) (879, 311) (466, 62)
(879, 311) (466, 62) (466, 62) (140, 481)
(466, 62) (21, 975) (879, 311) (466, 62)
(466, 62) (21, 975) (466, 62) (140, 481)
(879, 311) (466, 62) (879, 311) (339, 435)
(879, 311) (466, 62) (339, 435) (228, 907)
(466, 62) (21, 975) (879, 311) (339, 435)
(466, 62) (21, 975) (339, 435) (228, 907)
(879, 311) (466, 62) (879, 311) (339, 435)
(879, 311) (466, 62) (339, 435) (407, 956)
(466, 62) (21, 975) (879, 311) (339, 435)
(466, 62) (21, 975) (339, 435) (407, 956)
(879, 311) (466, 62) (879, 311) (339, 435)
(879, 311) (466, 62) (339, 435) (228, 907)
(466, 62) (140, 481) (879, 311) (339, 435)
(466, 62) (140, 481) (339, 435) (228, 907)
(879, 311) (466, 62) (879, 311) (339, 435)
(879, 311) (466, 62) (339, 435) (407, 956)
(466, 62) (140, 481) (879, 311) (339, 435)
(466, 62) (140, 481) (339, 435) (407, 956)
(879, 311) (339, 435) (879, 311) (339, 435)
(879, 311) (339, 435) (339, 435) (407, 956)
(339, 435) (228, 907) (879, 311) (339, 435)
(339, 435) (228, 907) (339, 435) (407, 956)
Script terminated.

L'algo ne commence pas avec des théories fumantes qui sortent d'un chapeau
C'est le codage de l'augmentation croissante des branches ( avec le nb de points ) qui est
l'étape finale pour aller jusqu'à 2^10 -1 = 1023 points et 1022 segments

N = 10 -> 2^9=512 branches qui ne se croisent pas
et d'une longueur de 9 segments par branche
La réduction en segment est proportionnelle à 2^(2N-1)
Avant de garder 1022 segments binaires, il faudra en éliminer 524 288