Algorithme d'inclusion d'intervalles.

MisterM
MisterM
dans Logiciels pour les mathématiques
Bonjour,

J'ai un problème d'algorithmique sur lequel je commence à tourner en rond.

Je dispose de N intervalles fermés. Chaque intervalle est formé par 2 entiers [a,b] tel que a < b (ce pourrait être un intervalle de flottant, cela ne doit pas changer l'algorithme). La liste peut contenir deux intervalles identiques.

Je cherche à calculer le plus grand nombre d'intervalles que l'on peu inclure dans un autre.

(En fait ce problème est un exercice du site France-IOI)

Une solution naïve consiste à parcourir l'ensemble des intervalles, et de calculer pour chacun d'entre eux le nombre d'intervalles qu'ils contiennent (cela se fait avec deux boucles imbriquées). Ensuite il suffit de garder le maximum du nombre d'intervalles contenu dans chacun.

En pseudo-code cela donne quelque chose comme ca: 
Pour chaque Ij
 Pour chaque Ik != Ij
   Si Ik inclu dans Ij Alors
     Compteur(j) <- Compteur(j)+1;
   FinSi
  FinPour
FinPour
 
CompteurMax <- 0;
Pour i de 1 à N
 CompteurMax <- max( CompteurMax , Compteur(i) );
FinPour

Cet algorithme a une complexité en O(N²). Je cherche quelque chose en O(N*log(N)) mais je n'arrive pas à trouver et je commence à tourner en rond.

J'ai d'abord pensé à trier les intervalles par "a" croissant puis par "b" croissant. Cela permet de réduire la zone de recherche en restreignant les tests d'inclusion (par exemple, si ak > bj on peut arrêter la recherche). Mais dans les pires cas on reste toujours en O(N^2).

J'ai aussi pensé à faire de la dichotomie mais sans succès.

Ma question est donc la suivante: quelqu'un pourrait-il m'aider à trouver une solution efficace (< O(N²) ) à ce problème ?

Même si c'est seulement des pistes je suis preneur.

Merci.

Réponses

  • test1
    test1
    Une piste. Seul « compteurmax » importe. De ce point de vue, il n'est pas utile d'évaluer les compteurs de tous les intervalles : il suffit de considérer ceux des intervalles qui ne sont inclus dans aucun autre. Tu pourrais par exemple remplir une liste chaînée (ou un arbre binaire équilibré, pour une complexité moindre) satisfaisant à tout instant les conditions suivantes :
    1. les a sont deux à deux distincts ;
    2. les b sont deux à deux distincts ;
    3. a < a' si et seulement si b < b'.
    Justifications :
    1. pour tous b, b', [a, b] est inclus dans [a, b'] ou [a, b'] inclus dans [a, b] ;
    2. pour tous a, a', [a, b] est inclus dans [a', b] ou [a', b] inclus dans [a, b] ;
    3. - si a < a' et b >= b' alors [a', b'] est inclus dans [a, b] ;
    - si a >= a' et b < b' alors [a, b] est inclus dans [a', b'].

    Imaginons cette liste chaînée déjà partiellement remplie et considérons un nouvel intervalle [a, b]. Cet intervalle peut être inclus dans un intervalle [a', b'] déjà présent dans la liste si et seulement si a' <= a et b <= b'.
    - Si c'est le cas, on augmente de 1 tous les compteurs des intervalle [a', b'] tels que a' <= a et b <= b', puis on « oublie » [a, b].
    - Sinon on ajoute [a, b] à la liste, on initialise son compteur à 0, puis pour tout intervalle [a', b'] de la liste tel que a <= a' et b' <= b (éventuellement aucun) :
    * on augmente le compteur de [a, b] de `1 plus le compteur de [a', b'] ' ;
    * on supprime [a', b'] de la liste.
  • MisterM
    MisterM
    Bonsoir,
    D'abord merci pour cette réponse.
    Néanmoins en l'état cela ne fonctionnera pas.
    En effet, si on admet que deux intervalles A,B se trouve dans la liste chaînée.
    On considère un 3ième intervalle C, inclu dans A et dans B => on incrémente le compteur de ces deux intervalles.
    Maintenant on considère l'intervalle D qui inclu A et B. On rajoute D dans la liste chainée et son compteur est initialisé à celui de A + celui de B + 2 => on a compté C deux fois !!
  • test1
    test1
    Aïe, en effet. A contrario, il se pourrait que D ne contienne ni A, ni B mais contienne C, honteusement oublié : pas bon. Ça y est, je suis accroché :) Je garde le problème en tête ; si jamais tu trouves une solution, tu peux la poster ?
  • test1
    test1
    Seconde tentative : on construit simultanément une liste L1 d'intervalles inclus dans aucun autre (la même que précédemment) et une liste L2 d'intervalles inclus dans au moins un autre. Supposons ces listes déjà partiellement construites et considérons un nouvel intervalle [a, b]. Cet intervalle peut être inclus dans un intervalle [a', b'] de L1 si et seulement si a' <= a et b <= b'.
    - Si c'est le cas, on augmente de 1 les compteurs de tous les intervalle [a', b'] de L1 tels que a' <= a et b <= b', puis on ajoute [a, b] à L2.
    - Sinon on ajoute [a, b] à L1, on initialise son compteur à 0 puis :
    * pour tout intervalle [a', b'] de L2 tel que a <= a' et b' <= b, on incrémente le compteur de [a, b] ;
    * pour tout intervalle [a', b'] de L1 tel que a <= a' et b' <= b, on incrémente le compteur de [a, b], on supprime [a', b'] de L1 et on l'ajoute à L2.
  • MisterM
    MisterM
    Pas de problème, une fois que c'est résolu je posterais la solution.
    Celle que tu as proposé est pas mal. Avec la seconde liste, le calcul est juste.
    J'ai implanté cela mais l'algorithme est toujours trop lent (ou plutôt pas assez rapide!) pour France-IOI.
    En fait si on regarde le pire cas de la technique (lorsque tous les intervalles sont disjoints) on retombe sur une complexité en O(N²).
  • MisterM
    MisterM
    Pour montrer que je continue de chercher, je poste ici une autre solution que j'ai implanté mais qui est encore trop lente.
    Je commence par prendre chacune des extrémités de chaque intervalle et je les tri par ordre croissant.
    Cela me donne une liste L1 de taille 2*N du style: "I3 débute, I12 débute, I8 débute, I12 termine, ..."
    Je vais ensuite maintenir une liste L2 des intervalles débuté mais non terminé.
    Ainsi chaque fois qu'un intervalle va se terminer, je vais incrémenter les compteur de tous les intervalles qui ont débuté mais non terminés qui le contienne.
    Pour ce faire, je parcours la liste L1 et j'effectue les opérations suivante:
    Lorsqu'un intervalle Ik débute:
    On parcours la liste L2. Si Ik est inclu dans l'un des intervalles de L2, alors on ne fait rien. Sinon on ajoute Ik dans L2.

    Lorsqu'un intervalle Ik termine:
    On parcours la liste L2.
    Si Ik est inclu dans l'un des intervalles de L2, alors on incrémente le compteur de celui ci.
    Si Ik est dans L2, alors on le retire de la liste.
    Au moment du retrait, on sait alors combien d'intervalles sont inclu dans Ik.

    L'algorithme fonctionne, est un peu plus lent que celui que tu as proposé, mais il a le même inconvénient: le pire cas est en O(N²).
    En effet, si on prend les N intervalles suivant: Ik = [k, N+k] (N intervalles de taille N qui se chevauchent sans s'inclurent), l'algorithme conduit à une liste L2 qui contient tous les intervalles...
  • someone0
    someone0
    Une astuce d'optimisation :

    Soient A et B deux intervalles pris dans la liste des intervalles.
    Soient N(A) (resp. N(B)) le nombre d'intervalles inclus dans A (resp. B).

    On a trivialement : Si A est inclus dans B alors N(A) <= N(B)

    Ce qui signifie que "si A est inclus dans B alors A est inutile".
  • someone0
    someone0
    Ci-dessous une proposition.
    L'algo est décrit grosso-modo car je n'ai pas le temps de formaliser.

    1/ On créer un nouveau tableau "T" où l'on tri les intervalles par :
    - La valeur de début de l'intervalle par ordre croissant
    - En cas de même valeur de début : La taille de l'intervalle par ordre décroissant (le plus gros intervalles en premier)

    ==> O(N.ln(N))

    2/ On initialise 2 variables (VMax et VMaxCourant) à zéro et on PARCOURT le tableau dans l'ordre :
    - SI l'intervalle suivant est inclus dans l'intervalle courant
    - ALORS
    - On incremente VMaxCourant
    - VMax=MAX( VMax, VMaxCourant )
    - On supprime l'intervalle suivant du tableau
    - SINON
    - VMax=MAX( VMax, VMaxCourant )
    - VMaxCourant = 0
    - FIN SI

    ==> O(N)

    3/ La valeur cherchée est VMax

    Compléxité totale : O(N.ln(N))
  • MisterM
    MisterM
    Bonjour,
    Écrit comme ça l'algorithme ne fonctionne pas.
    Prenons par exemple les intervalles suivant: A=[0,8] B=[1,2] C=[3,10] D= [4, 5].
    On a B,D inclus dans A et D inclus dans C. Le résultat attendu est donc 2.
    Les intervalles sont déjà triés comme décris dans l'étape 1.
    Si on déroule l'algorithme on a:
    courant A, suivant B => VMaxCourant = 1, VMax=1
    courant A, suivant C => VMaxCourant=0, VMax=1
    courant C, suivant D => VMaxCourant = 1, VMax = 1

    => L'algorithme retourne 1 car on a jeté "A" lorsqu'il n'incluait pas "C" alors que "A" inclus "D" qui vient juste après !
  • Steven Neutral
    Steven Neutral
    Une remarque à 2 balles : Si Ik inclu dans Ij alors inutile de faire le test pour Ik.
  • MisterM
    MisterM
    En fait ce qui pose problème c'est pas ce qu'il faut faire quand il y a inclusion mais plutôt lorsqu'il n'y a pas inclusion.
    Avec les deux algorithmes qui fonctionnent on doit les conserver ce qui conduit à une complexité en O(N²).
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Bonjour,
    Je lis ce sujet depuis le début, mais j'avoue que j'ai pas cherché.
    Cependant, ça me fait vraiment penser au problème du plus court chemin.
    Il y a un algorithme connu pour ce problème, son auteur a un nom impossible : Dijkstra.
    C'est particulièrement efficace.
    Naturellement c'est le problème inverse.
  • MisterM
    MisterM
    Je ne vois pas comment formuler le problème pour se ramener à un cas d'application de Dijkstra.
    Tu pourrais préciser ?
    Merci.
  • test1
    test1
    Au cas où, une reformulation du problème (rien à voir avec Dijkstra ; je ne suis pas sûr qu'elle soit utile, mais sait-on jamais).

    Nous pouvons assimiler chaque intervalle [a, b] à l'intersection, dans un repère, de le l'axe des abscisses et du disque de centre ((b+a)/2, 0) et de rayon (b-a)/2.

    Le problème devient alors : étant donnés N disques (x, r) de centres alignés sur l'axe des abscisses (où x désigne l'abscisse du centre et r le rayon), déterminer le plus grand nombre de disques pouvant êtres inclus dans un autre.

    Intérêts éventuels de cette formulation (mais je ne sais pas quoi en faire) :
    - la possibilité de trier les intervalles par abscisse du centre ou rayon plutôt que par début ou fin ;
    - l'expression simplifiée (?) des conditions d'inclusion (si x <= x' alors (x, r) est inclus dans (x', r') ssi x'-x <= r'-r et (x', r') est inclus dans (x, r) ssi x'-x <= r-r').
  • Professeur Rectangle
    Professeur Rectangle
    Si on veut se ramener à un graphe, on peut considérer les intervalles comme des sommets, et dire qu'il y a une arrête de $I$ vers $J$ ssi $I\varsubsetneq J$.

    Le problème revient alors à calculer le plus long chemin dans un graphe acyclique (DAG).

    Cependant, je ne suis pas sûr que la vision "graphe" apporte une meilleure complexité.
  • christophe c
    christophe c
    @PR, attention, ce n'est pas le même problème. Dans son cas, il ne cherche pas le plus long chemin (avec ta traduction) mais le sommet ayant le plus de voisins

    @auteurdufil: le fait que ce soit des intervalles est important si tu veux satisfaire ton désir. Dans un graphe quelconque il parait vain de chercher le sommet avec le plus de voisins avec un algorithme en moins de $O(N^2)$. En effet, même dans le cas particulier où on veut savoir s'il existe une arête (ie trouver un sommet ayant au moins un voisin), l'algorithme devra lire au moins chaque couple de sommet et interroger s'ils sont voisins ou non.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • MisterM
    MisterM
    Bon j'ai finalement trouvé une solution en $O(N \log N)$
    Les $N$ intervalles $I_k = [a_k, b_k]$ sont stockés dans un tableau.
    - D'abord on trie le tableau par $a_k$ croissant et en cas d'égalité par $b_k$ décroissant.
    - On parcours ensuite ce tableau et on mémorise la position $p^1_k$ de chaque intervalle.
    - Puis, on trie de nouveau le tableau, mais cette fois-ci par $b_k$ décroissant, et en cas d'égalité, par $a_k$ croissant.
    - On parcours alors ce tableau et on mémorise la position $p^2_k$ de chaque intervalle.
    - Le nombre d'intervalles max inclus dans un autre est alors $\underset{k}{\operatorname{argmax}} ( N - p^1_k - p^2_k -1 )$ pour $k \in [1,N]$ (avec pour convention $p^i_k = 0$ pour la première position dans le tableau)

    Les 2 tris sont en $O(N \log N)$. Les parcours de tableau sont en $O(N)$.
  • test1
    test1
    Joli. Merci d'avoir posté ta solution.
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Bonjour,
    Je voudrais aussi donner une autre méthode.
    Dans une première boucle, éventuellement au moment du chargement,
    si le longueur de l'intervalle (=b-a) est plus grande que la longueur du plus grand intervalle déjà trouvé, je définis les 4 valeurs suivantes :
    Min_a, Max_b, MaxInter, et RandMax.
    A la fin du chargement (ou de la lecture), je connais le rang du plus rang intervalle, c'est à dire celui qui ne peut être contenu par aucun autre.
    Une seconde boucle permet de compter les intervalles qu'il contient.

    Le module comporte une première boucle de lecture avec choix du plus grand intervalle, et une seconde pour le comptage des intervalles inclus.
    Effectivement ma première idée de graphe n'était pas terrible.
  • bisam
    bisam
    Celle-ci n'est pas géniale non plus... Le plus grand intervalle peut très bien ne pas être celui qui contient le plus grand nombre d'autres intervalles, et même n'avoir aucun rapport avec celui-ci !

    Contre-exemple : [0, 10], [11,12], [11,13], [11,14]
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Bonsoir Bisam,
    Oui, t'as tout à fait raison, mais j'avais cru comprendre que dans l'énoncé, il s'agissait d'un grand nombre d'intervalles et que leur définition était aléatoire.
    Si les intervalles se limitent à un petit nombre, pourquoi faire un calcul que l'on cherche optimiser ?
    J'ajouterai simplement qu'avant l'informatique, on s'en sortait très bien. L'informatique a permis de résoudre des problèmes contenant un grand nombre de données, donc très longs en matière de calcul.
    Si on doit faire un programme pour démontrer que 1+2=3, on perd son temps.
  • Botni
    Botni
    Ce post est sans doute très ancien mais je le découvre aujourd'hui bloqué, comme MisterM, par le même exercice.
    Le premier tri est naturel.
    Le second ? d'une certaine manière le «symétrique » du premier.
    Les deux ensembles , raisonnable puisqu'il n'y a pas de raison de privilégier le début ou la fin d'un intervalle.
    Mais la spectaculaire formule qui résout le problème est, pour moi, bien mystérieuse ...

    Bravo et merci à MisterM d'avoir pris la peine de donner cette étonnante solution.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Français