Algorithme pour combiner les plages d'un segment - aide à la création

 

Veuillez m'aider à créer un algorithme qui combine des morceaux (plages) d'un segment en un seul segment sans intersection de segments, avec un éventuel vide à combler ultérieurement.

Au départ, nous avons un tableau de nombres dans une certaine plage, les nombres peuvent être répétés, ce tableau est divisé en segments par des frontières. Les frontières sont générées par différents algorithmes, généralement les frontières ne sont pas uniformes, il s'avère donc que le tableau de nombres est découpé par différentes méthodes et que chaque plage a une taille différente. Ensuite, une évaluation de chacun de ces segments selon trois critères, chaque critère ayant sa propre limite, dont le non-respect élimine un morceau de la gamme. En conséquence, nous obtenons un tableau avec le contenu suivant.

i - numéro de séquence de la gamme ;

S - limite de début de plage ;

F - limite de fin de plage ;

%R - critère #1 ;

%dP - critère numéro 2 ;

%K_SCO - critère numéro 3 ;

K_Svod - évaluation sommaire de tous les critères.

La figure ci-dessous montre comment les chunks (segments) peuvent être placés dans le plan :

Les 3 couleurs de coches à côté des pièces sont des solutions potentielles au problème.

L'algorithme doit fournir différentes combinaisons de solutions au problème afin que la condition soit remplie :

1. les segments sont appariés sans croisement de plages (S>=A && F<B) ;

2. Il est impossible d'ajouter un segment de plus parmi ceux qui sont disponibles - c'est-à-dire qu'une certaine complétude et une densité maximale découlent des variantes choisies et disponibles ;

3. La séquence des segments est ordonnée - pour éliminer les combinaisons similaires ;

4. au moins une des meilleures barres est utilisée, parmi les30% supérieurs selonK_Svod- pour réduire les combinaisons et garder la priorité du meilleur score.

Idéalement, l'estimation de la qualité devrait être de maximiser la somme de tous les segments selon K_Svod, mais il peut être nécessaire de la corriger légèrement pour estimer le ou les espaces de remplissage.

Peut-être ai-je utilisé une mauvaise terminologie et mon problème a déjà été résolu il y a longtemps - ne jugez pas - éclairez-moi.

 
Aleksey Vyazmikin:


1) K_Svod - évaluation sommaire de tous les critères.

2) La figure ci-dessous montre comment les pièces (segments) peuvent être placées dans le plan :

3) Les segments sont appariés sans intersection de plages (S>=A && F<B) ;

1) qu'est-ce que c'est ? pourquoi des x ?

2) mieux vaut montrer par l'image ce qui est bien et ce qui est mal.

3) qu'est-ce que "A" et qu'est-ce que "B" ?

4) Faites également une "maquette" du tableau de données et montrez ce que vous voulez voir comme une solution satisfaisante.
 
Probablement résolu en termes de théorie des graphes. Les sommets d'un graphe sont des segments, les flèches du graphe relient chaque sommet à tous les sommets suivants possibles (les segments admissibles les plus proches). Chaque sommet et chaque flèche sont marqués d'un poids et une règle est définie pour compter le poids de chaque chemin. Un algorithme pour trouver le chemin optimal dans le graphe est appliqué. Je ne suis pas prêt à examiner la question plus en détail).
 
mytarmailS:

1) qu'est-ce que c'est ? pourquoi X ?

2) mieux vaut montrer par une image ce qui est bien et ce qui est mal ?

3) qu'est-ce que "A" et qu'est-ce que "B" ?

4) faites également une "maquette" du tableau de données et montrez ce que vous voulez voir comme solution satisfaisante.

1. C'est une dérivée des 3 évaluations, les X sont parce que je n'ai pas encore décidé des poids, ce n'est pas essentiel.

2. La solution correcte consiste à remplir l'espace avec des segments (une ligne avec un espace probable non rempli entre les segments) - dans la figure ci-dessus, j'ai coché les couleurs pour chacune des 3 solutions possibles. Il est possible de penser à des heuristiques supplémentaires, disons que la somme de la plage allouée de tous les segments est aussi grande que possible, mais en plus de la somme, la valeur K_Svod est également importante.

3) Il s'agit d'une valeur de chiffres à l'intérieur du segment, il serait préférable d'écrire A1>=S1 && A1<F1 && F1<S2.

4. La solution serait un tableau avec des indices. Ou je n'ai pas compris la question. Algorithme, comment le faire mieux, je ne sais pas.

 
Aleksey Nikolayev:
Probablement résolu en termes de théorie des graphes. Les sommets d'un graphe sont des segments, les flèches du graphe relient chaque sommet à tous les segments suivants possibles (les segments admissibles les plus proches). Chaque sommet et chaque flèche sont marqués d'un poids et une règle est définie pour compter le poids de chaque chemin. Un algorithme pour trouver le chemin optimal dans le graphe est appliqué. Je ne suis pas prêt à examiner la question plus en détail).

Merci pour l'idée, je pense qu'il est possible de commencer à construire la séquence à partir du haut de chaque indice i, puis d'évaluer les combinaisons résultantes. Il suffit d'un critère de sélection ou de plusieurs critères pour obtenir différentes combinaisons. Ou des critères aléatoires.... n'est pas encore clair.

 
Aleksey Vyazmikin:

1. c'est un dérivé des 3 évaluations, le X vient du fait que je n'ai pas encore décidé des pondérations - ce n'est pas essentiel.

2. La solution correcte est de remplir l'espace avec des segments (une ligne avec un espace probable non rempli entre les segments) - dans la figure ci-dessus, j'ai coché les couleurs pour chacune des 3 solutions possibles. Il est possible de penser à des heuristiques supplémentaires, disons que la somme de la plage allouée de tous les segments est aussi grande que possible, mais en plus de la somme, la valeur K_Svod est également importante.

3) Il s'agit d'une valeur de chiffres à l'intérieur du segment, il serait préférable d'écrire A1>=S1 && A1<F1 && F1<S2.

4. La solution serait un tableau avec des indices. Ou je n'ai pas compris la question. L'algorithme, comment le faire mieux, je ne sais pas.

Je ne comprends toujours pas.

 
Aleksey Vyazmikin:

Merci pour l'idée, je pense qu'il est possible de commencer à construire la séquence à partir du haut de chaque indice i, puis d'évaluer les combinaisons résultantes. Il suffit d'un critère de sélection ou de plusieurs critères pour obtenir différentes combinaisons. Ou des critères aléatoires.... n'est pas encore clair.

Et où sont les tiques, ont-elles une sorte de critère selon lequel le segment appartient à cette tique ?
En gros, vous avez trois tics. Bleu, rouge, vert.
Donc dans cet exemple, trois identifiants.
Si vous attribuez ces identifiants d'une manière ou d'une autre, vous pouvez les concaténer en trois tableaux principaux.
En utilisant l'identifiant, nous obtenons la taille du segment résultant,
utiliser l'identifiant pour définir le tableau de réception principal etaugmenter sa capacité de cette taille,
utiliser l'identifiant pour insérer le segment à la fin du tableau.
Nous devons donc définir d'une manière ou d'une autre un critère selon lequel le segment appartient à cette case (identifiant).

 
mytarmailS:

Je ne comprends toujours pas

Veuillez préciser ce que vous ne comprenez pas - je vais essayer d'expliquer avec d'autres mots.

 
Roman:

Mais où sont les tiques, ont-elles une sorte de critère selon lequel le segment appartient à cette tique ?
En gros, vous avez trois tics. Bleu, rouge, vert.
Donc dans cet exemple, trois identifiants.
Si vous attribuez ces identifiants d'une manière ou d'une autre, vous pouvez les concaténer en trois tableaux principaux.
Par identifiant, nous obtenons la taille du segment résultant,
par identifiant, nous définissons un tableau de réception de base etaugmentons sa capacité de cette taille,
par identifiant, nous insérons le segment à la fin du tableau.
Donc, nous devons définir un critère selon lequel le segment appartient à cette case (identifiant).

J'ai dessiné les segments, puis j'ai pensé montrer la possibilité de les combiner - j'ai examiné les combinaisons qui ne se chevauchent pas et qui, ensemble, occupent une grande surface. Notez que certains des segments ont deux ticks, ce qui signifie qu'il est possible d'avoir le segment dans plus d'une combinaison.

C'est-à-dire qu'il n'y a pas d'identifiant avant le début du traitement des données.
 
Aleksey Vyazmikin:

J'ai dessiné les segments, puis j'ai pensé à montrer la possibilité de les combiner - j'ai examiné les combinaisons qui ne se croisent pas et qui, ensemble, occupent une plus grande surface. Notez que certains des segments ont deux ticks, ce qui signifie qu'il est possible d'avoir le segment dans plus d'une combinaison.

C'est-à-dire qu'il n'y a pas d'identifiant avant le début du traitement des données.

Peut-être que sur la base de votre algorithme, chaque segment peut être identifié par un critère quelconque et se voir attribuer un identifiant.
Et le fait qu'un segment puisse êtredans plus d'une combinaison dépend de la volonté de l'ajouter à nouveau au tableau principal ou non.
Utilisez des opérateursternaires ou conditionnels pour jouer avec la logique.

 
Roman:

Peut-être que sur la base de votre algorithme, chaque segment peut être identifié par un critère quelconque et se voir attribuer un identifiant.
Et le fait qu'un segment puisse êtredans plus d'une combinaison dépend de la nécessité ou non de l'ajouter à nouveau au tableau principal.
Utilisez des opérateursternaires ou conditionnels pour jouer avec la logique.

Il n'y a donc pas d'algorithme pour commencer :) Chaque segment est identifié par un numéro ordinal et comporte des informations sur les coordonnées (axe X) et une sorte d'estimation de l'utilité à ces coordonnées.

Pour l'instant, une seule idée me vient à l'esprit : choisir le segment le plus proche du segment initial. Peut-être que de cette façon nous pouvons choisir les 3 premiers les plus proches, en fonction du nombre de segments le nombre de combinaisons augmentera.