Problème intervalles

[gio123]

Bonjour à tous !

J'ai un problème que je ne sais résoudre actuellement. J'imagine qu'une âme charitable pourra m'aiguiller vers une méthode ou une piste de réflexion.

Je dispose d'une liste d'intervalle, j'ai nommé les intervalles avec des lettres (colonne 1), j'ai inscris les deux bornes également (colonne 2 et 3).

Je cherche à trouver la combinaison de point minimale qui me permettrait de "couper" au moins une fois chaque intervalle.

Je vous joins le fichier excel pour que vous puissiez visualiser.

Merci d'avance.

Gio

Problème intervalles.xlsx
-----

[mécano41]

Bonjour,

Je ne suis pas sûr d'avoir compris "combinaison de points minimale"...Ci-joint avec une courbe qui passe par le milieu de tous les intervalles...mais je suppose que tu cherches autre chose...

Cordialement

[gio123]

Merci beaucoup pour votre réponse

Votre réponse s'approche de ce que je recherche, cependant j'aimerais trouver un nombre de droite minimal passant par ces intervalles. Les droites doivent être de forme Y = constante.

Encore merci !

[gg0]

Bonjour.

Si j'ai bien compris, ce que tu cherches est une série de nombres x_i telle que :
* Chacun des intervalles contient au moins un des x_i.
* Le nombre des x_i est minimal.

Il es facile d'inventer des algorithmes donnant la première condition; mais la deuxième est difficile à réaliser; et même, comment contrôler que la solution est correcte, qu'aucune autre série de valeurs plus courte ne convient ?
Il me semble que traiter cette deuxième partie est la priorité : Si on ne sait pas faire ça, il est peu probable qu'on sache prouver que la solution est la bonne.

Par contre, on peut facilement imaginer des algorithmes qui donnent une solution pas trop longue. Par exemple prendre des valeurs dans les premiers intervalles et à chaque nouvel intervalle, regarder si les valeurs déjà choisies ne sont pas dans ce nouvel intervalle. On peut l'améliorer en autorisant de modifier une valeur déjà choisie pour ne pas être obligé de rajouter un x_i.

Cordialement.

[A voir en vidéo sur Futura]

[minushabens]

j'ai l'impression qu'il suffit de chercher les points xi parmi les bornes des intervalles.

[Tryss2]

Moi je m’intéresserai aux intersections des intervalles.

Si on a n intervalles, pour toute partition de , on défini



Si , alors en prenant un x (quelconque) dans pour chaque , alors on a une combinaison qui convient, et elle est minimale si le cardinal de sigma est minimal parmi les partitions convenables.


Comme le fait remarquer minushabens, on pourra toujours choisir le x au bord d'un intervalle ( ou , avec m(I) la borne inférieure et M(I) la borne supérieure de l'intervalle )


Pour un algorithme, je commencerai par découper le problème en sous problèmes indépendants : les composantes connexes de forment des sous-problèmes indépendants.

[mécano41]

Bonjour,

J'ai repris le sujet. Si toutefois j'ai compris...voici une appli. EXCEL qui traite le problème en VBA (donc lecture sur EXCEL après validation des macros à l'ouverture, pas sur LibreOffice ni sur OpenOffice)

Chaque colonne de la feuille Résultats donne l'écart commun (2 premières lignes) et les noms de tous les écarts du tableau de donnés qui sont concernés par cet écart commun (lignes suivantes).

S'il n'y a qu'un nom d'écart dans la colonne, cela signifie qu'aucun autre écart n'est commun.

Toute modification d'une valeur dans les colonnes jaune entraîne la mise à jour du tableau des résultats.

Cordialement

[mécano41]

J'ai oublié de dire :

- on ne peut pas représenter des barres horizontales correspondant à l'écart commun sur le graphique car ce serait un fouillis inextricables
- pour voir le code : faire Alt+F11

J'ai aussi oublié d'effacer le Module1 dans le VBA (macro d'essai devenue inutile)

Cordialement