Algoritmo para combinar rangos de un segmento - ayuda para crear

 

Por favor, ayúdenme a crear un algoritmo que combine trozos (rangos) de un segmento en un solo segmento sin intersección de segmentos, con un posible hueco a rellenar posteriormente.

Inicialmente tenemos un array de números en un rango determinado, los números pueden repetirse, este array está dividido en segmentos por bordes. Los límites se generan por diferentes algoritmos, normalmente los límites no son uniformes, por lo que resulta que la matriz de números se corta por diferentes métodos y cada rango tiene un tamaño diferente. A continuación, se evalúa cada uno de esos segmentos según tres criterios, cada uno de los cuales tiene su propio límite, cuyo incumplimiento elimina un trozo de la gama. Como resultado, obtenemos una tabla con el siguiente contenido.

i - número de secuencia del rango;

S - límite de inicio de rango;

F - Límite final del rango;

%R - criterio #1;

%dP - criterio número 2;

%K_SCO - criterio número 3;

K_Svod - evaluación resumida de todos los criterios.

La figura siguiente muestra cómo se pueden colocar los trozos (segmentos) en el plano:

Los 3 colores de marcas de verificación junto a las piezas son soluciones potenciales al problema.

El algoritmo debe proporcionar diferentes combinaciones de soluciones al problema para que se cumpla la condición:

1. Los segmentos coinciden sin cruzar rangos (S>=A && F<B);

2. Es imposible añadir un segmento más a partir de los disponibles, es decir, una cierta completitud y densidad máxima a partir de las variantes elegidas y disponibles;

3. La secuencia de segmentos está ordenada, para eliminar las combinaciones similares;

4. se utiliza al menos una de las mejores barras, del30% superior segúnK_Svod- para reducir las combinaciones y mantener la prioridad de la mejor puntuación.

Lo ideal sería que la estimación de la calidad fuera maximizar la suma de todos los segmentos según K_Svod, pero puede que haya que corregirla un poco para estimar el espacio/espacio de relleno.

Tal vez he utilizado una terminología equivocada y mi problema ya se ha resuelto hace mucho tiempo - no juzgue - ilumíneme.

 
Aleksey Vyazmikin:


1) K_Svod - evaluación resumida de todos los criterios.

2) La figura siguiente muestra cómo se pueden colocar las piezas (segmentos) en el plano:

3) Los segmentos se emparejan sin intersecciones de rango (S>=A && F<B);

1) ¿qué es esto? ¿por qué x's?

2) mejor mostrar con una imagen lo que está bien y lo que está mal

3) ¿Qué es "A" y qué es "B"?

4) Haz también una "maqueta" de la tabla de datos y muestra lo que quieres ver como solución satisfactoria
 
Posiblemente se resuelva en términos de teoría de grafos. Los vértices de un grafo son segmentos, las flechas del grafo conectan cada vértice con todos los posibles vértices posteriores (los segmentos más cercanos permitidos). Cada vértice y flecha se marca con pesos y se define una regla por la que se cuenta el peso de cada camino. Se aplica algún algoritmo para encontrar el camino óptimo en el grafo. No estoy preparado para investigar la cuestión con más detalle)
 
mytarmailS:

1) ¿qué es? ¿por qué X?

2) mejor mostrar con una imagen lo que está bien y lo que está mal ?

3) ¿Qué es "A" y qué es "B"?

4) hacer también una "maqueta" de la tabla de datos y mostrar lo que se quiere ver como solución satisfactoria

1. es un derivado de las 3 evaluaciones, X del hecho de que no he decidido sobre los pesos todavía, no es esencial.

2. La solución correcta es rellenar el espacio con segmentos (una línea con probable espacio sin rellenar entre segmentos) -en la figura de arriba he marcado los colores para cada una de las 3 posibles soluciones. Es posible pensar en una heurística adicional, digamos que la suma del rango asignado de todos los segmentos es lo más grande posible, pero además de la suma el valor de K_Svod también es importante.

3) Se trata de un valor de números dentro del segmento, sería mejor escribir A1>=S1 && A1<F1 && F1<S2.

4. La solución sería un array con índices. O no he entendido la pregunta. Algoritmo, cómo hacerlo mejor, no lo sé.

 
Aleksey Nikolayev:
Probablemente se resuelva en términos de teoría de grafos. Los vértices de un grafo son segmentos, las flechas del grafo conectan cada vértice con todos los posibles subsiguientes (los segmentos admisibles más cercanos). Cada vértice y flecha se marca con pesos y se define una regla por la que se cuenta el peso de cada camino. Se aplica algún algoritmo para encontrar el camino óptimo en el grafo. No estoy preparado para investigar la cuestión con más detalle)

Gracias por la idea, creo que es posible empezar a construir la secuencia desde la parte superior de cada índice i y luego evaluar las combinaciones resultantes. Sólo necesitamos un criterio de selección o varios criterios para obtener diferentes combinaciones. O aleatorizar los criterios.... aún no está claro.

 
Aleksey Vyazmikin:

1. es un derivado de las 3 evaluaciones, la X es del hecho de que no he decidido los pesos todavía - no es esencial.

2. La solución correcta es rellenar el espacio con segmentos (una línea con probable espacio sin rellenar entre segmentos) - en la figura de arriba, he marcado los colores para cada una de las 3 posibles soluciones. Es posible pensar en una heurística adicional, digamos que la suma del rango asignado de todos los segmentos es lo más grande posible, pero además de la suma, el valor de K_Svod también es importante.

3) Se trata de un valor de números dentro del segmento, sería mejor escribir A1>=S1 && A1<F1 && F1<S2.

4. La solución sería un array con índices. O no he entendido la pregunta. El algoritmo, cómo hacerlo mejor, no lo sé.

Todavía no lo entiendo.

 
Aleksey Vyazmikin:

Gracias por la idea, creo que es posible empezar a construir la secuencia desde la parte superior de cada índice i y luego evaluar las combinaciones resultantes. Sólo necesitamos un criterio de selección o varios criterios para obtener diferentes combinaciones. O aleatorizar los criterios.... aún no está claro.

¿Y dónde están las garrapatas, tienen algún tipo de criterio de que el segmento pertenece a esa garrapata?
Básicamente, tienes tres ticks. Azul, rojo, verde.
Así que en este ejemplo, tres identificadores.
Si asignas estos identificadores de alguna manera, puedes concatenarlos en tres matrices principales.
Usando el identificador, obtenemos el tamaño del segmento resultante,
usamos el identificador para definir el array de recepción principal yaumentamos su capacidad en este tamaño,
usamos el identificador para insertar el segmento al final del array.
Entonces, necesitamos definir algún criterio de que el segmento pertenece a esta casilla (identificador).

 
mytarmailS:

Todavía no entiendo

Por favor, aclare lo que no entienda, intentaré explicarlo con otras palabras.

 
Roman:

Pero, ¿dónde están las garrapatas, tienen algún tipo de criterio de que el segmento pertenece a esa garrapata?
Básicamente, tienes tres ticks. Azul, rojo, verde.
Así que en este ejemplo, tres identificadores.
Si asignas estos identificadores de alguna manera, puedes concatenarlos en tres matrices principales.
Por identificador obtenemos el tamaño del segmento resultante,
por identificador definimos un array básico de recepción eincrementamos su capacidad por este tamaño,
por identificador insertamos el segmento al final del array.
Así que necesitamos definir algún criterio de que el segmento pertenece a esta casilla (identificador).

He dibujado los segmentos y luego he pensado en mostrar la opción de combinarlos: me he fijado en las combinaciones que no se solapan y que juntas ocupan una gran superficie. Tenga en cuenta que algunos de los segmentos tienen dos marcas, lo que significa que es posible tener el segmento en más de una combinación.

Es decir, no hay ningún identificador antes de que comience el tratamiento de los datos.
 
Aleksey Vyazmikin:

He dibujado los segmentos y luego he pensado en mostrar la opción de combinarlos: he mirado las combinaciones que no se cruzan y que juntas ocupan un área mayor. Tenga en cuenta que algunos de los segmentos tienen dos marcas, lo que significa que es posible tener el segmento en más de una combinación.

Es decir, no hay ningún identificador antes de que comience el tratamiento de los datos.

Tal vez, basándose en su algoritmo, cada segmento pueda ser identificado por algún criterio y se le asigne un identificador.
Y el hecho de que un segmento pueda estaren más de una combinación depende de si hay que añadirlo de nuevo a la matriz principal o no.
Utilice operadoresternarios o condicionales para jugar con la lógica.

 
Roman:

Tal vez, basándose en su algoritmo, cada segmento pueda ser identificado por algún criterio y se le asigne un identificador.
Y el hecho de que un segmento pueda estaren más de una combinación depende de si hay que añadirlo de nuevo a la matriz principal o no.
Utilice operadoresternarios o condicionales para jugar con la lógica.

Así que no hay ningún algoritmo para empezar :) Cada segmento se identifica con un número ordinal y tiene información sobre las coordenadas (eje X) y algún tipo de estimación de utilidad en estas coordenadas.

Hasta ahora sólo se me ocurre una idea: elegir el segmento más cercano al inicial. Tal vez de esta manera podemos elegir los 3 primeros más cercanos, dependiendo del número de segmentos el número de combinaciones crecerá.