Discussion :

[van noctar]

Bonjour à tous,

Je sais que ce salon n'est peut-être pas le plus adapté pour ce type de question mais je n'ai pas trouvé ailleurs .

Voilà mon problème, j'ai besoin d'un algorithme performant car j'en ai trouvé quelques uns mais l'ordre de calcul minimum que j'ai trouvé au minimum est de O[(2^n)-1]. Bref c'est plutôt couteux sachant que j'ai 11 000 données à étudier.

Je vous explique la situation, j'ai un type de donnée de la sorte:

element:

nom1: valmin , valmax
nom2: valmin, valmax
....
nomN: valmin, valmax

Mon algorithme prend en entrée un ensemble d'élement ayant un ensemble de valeur avec valMin = valMax.

Par exemple:

e1:
a 1 1
b 2 2
c 2 2

e2:
a 2 2
b 4 4
c 5 5

e2:
a 3 3
b 3 3
c 6 6

Le but de mon algorithme est de définir les intervalles reliant ces types, dans cet exemple, le résultat obtenu serait:

e1:
a 1 1
b 2 2
c 2 2

e2:
a 2 2
b 4 4
c 5 5

e2:
a 3 3
b 3 3
c 6 6

t1:
a 1 3
b 2 4

t2 :
b 3 4
c 5 6



La jointure entre un element A et un element B se fait de cette facon:

admettons que nous ayons:

a1:
a 2 2
b 3 3
c 6 6

et

a2:
a 3 3
b 10 10
c 5 5

alors la jointure entre ces deux éléments sera:

t :
a 2 3
c 5 6
(pas de b car il n'y a pas de lien entre 3 et 10)

ça c'est simple à obtenir.

Le but de l'algorithme est de calculer un ensemble d'intervalles sans "trou".


Admettons que nous ayons :

e1:
a 1 1
b 2 2
c 2 2

e2:
a 3 3
b 3 3
c 6 6

Nous ne pouvons obtenir que

b 2 3

en revanche pour obtenir

a 1 3
b 2 3
c 2 6

il faut qu'il y ai au préalable (dans une liste temporaire, c'est comme ça que j'ai fait)

a 2 2 ou a 1 2 ou a 2 3 ou a 13
b 2 2 ou b 3 3 ou b 2 3
c 2 5 ou c 3 6 ou c 2 5 ou c 26

Bref c'est un peu compliqué, je ne sais pas si j'ai bien exprimé mon problème mais j'ai besoin d'aide car je n'arrive pas à avoir quelque chose de performant...

Merci beaucoup!

[pseudocode]

Si j'ai bien compris, tu as des données qu'on peut représenter ainsi

   1  2  3  4  5  6
-------------------- - -
a|e1 e2 e3  .  .  . 
b| . e1 e3 e2  .  .
c| . e1  .  . e2 e3

ce qui permet de construire un graphe d'accessibilité (via tes "jointures")

a1--a2--a3
|___    |
|   |   |
|   b2--b3--b4
|___        |__  
    |          |
    c2         c5--c6

et tu cherches le chemin le plus long (horizontalement) ?

[van noctar]

Si j'ai bien compris, tu as des données qu'on peut représenter ainsi

1 2 3 4 5 6
-------------------- - -
a|e1 e2 e3 . . .
b| . e1 e3 e2 . .
c| . e1 . . e2 e3
ce qui permet de construire un graphe d'accessibilité (via tes "jointures")

Pour toi les a,b,c sont les éléments et e1 e2 e3... sont l'ensemble des intervalles de ces éléments? C'est bien ça? Histoire qu'on soit d'accord lol!

En fait ce que je veux c'est un ensemble d'élément représentant tous les intervalles sans "trou" possibles .

e1 -->[a1 1 , b2 2, c 3 3 ]
e2 -->[a3 3 , b4 4, c 6 6 ]
e3 -->[a4 4 , b5 5, c 4 4 ]

résultats:

e1 -->[a1 1 , b2 2, c 3 3 ]
e2 -->[a3 3 , b4 4, c 6 6 ]
e3 -->[a4 4 , b5 5, c 4 4 ]
r1 --> [a3 4, b4 5]
r2 --> [c3 4]

Je ne sais pas si ça correspond à ce que tu disais, je n'ai pas très bien compris ton graphe

[van noctar]

J'ai compris ta structure de données, mais je ne sais pas si c'est bon, en effet, dans ton exemple on obtient:

a1--a2--a3
|___ |
| | |
| b2--b3--b4
|___ |__
| |
c2 c5--c6

t --> [a 1 3 ,b 2 4 ,c 5 6]

alors qu'on devrai obtenir ceci

t1 -->[a 1 3,b 2 4]
t2 --> [b 3 4, c 5 6]

[pseudocode]

J'ai compris ta structure de données, mais je ne sais pas si c'est bon, en effet, dans ton exemple on obtient:

t --> [a 1 3 ,b 2 4 ,c 5 6]

alors qu'on devrai obtenir ceci

t1 -->[a 1 3,b 2 4]
t2 --> [b 3 4, c 5 6]

Je ne comprend pas trop ta définition de ce qu'est une jointure valide.

J'avais cru comprendre qu'une jointure entre des éléments est l'ensemble des intervalles de taille >= 2 pour chaque composante (a,b,c) :

join(e1,e2) = { a[1:2] }
join(e1,e3) = { b[2:3] }
join(e2,e3) = { a[2:3] , b[3:4] , c[5:6] }
join(e1,e2,e3) = { a[1:3] , b[2:4] , c[5:6] }

Visiblement, ce n'est pas ca. Est-ce que tu pourrais nous expliquer la situation de départ qui t'as amené à ce problème d'intervalle/jointure ?

[van noctar]

Prenons par exemple juste un intervalle:

P(a b) et Q(a b)

une jointure s'effectue de la sorte:

Si( abs(P.a - Q.a) <= 1
|| abs(P.a - Q.b) <= 1
|| abs(P.b - Q.a) <= 1
|| abs(P.b - Q.b) <= 1
|| Q est inclu dans P )
alors jointure.
Sinon pas jointure.

Donc si on a un element A (composé bien sûr de n intervalles ) et un element B (idem), la jointure(A,B) = l'ensemble des jointures des intervalles de A et de B.

exemple:

A-->[a(1 1); b(2 2) ; c(3 3)]
B-->[a(3 3); b(3 3) ; c(2 2)]
Jointure(A,B)-->[ b(2 3) ; c(2 3)]

Autre exemple, admettons que l'on ai ceci:

A-->[a(1 3); b(2 4) ; c(3 7)]
B-->[a(3 3); b(6 6) ; c(2 2)]
Jointure(A,B)--> [ a(1 3); c(2 7) ]

J'espere que c'est plus clair...