Buscar funciones mínimas

Question

Bien, este es el trato. Tengo un montón de funciones lineales, a * x + b.

Mi objetivo es responder a la siguiente pregunta/consulta: ¿Cuál es la función mínima en x = q?

Por ejemplo: si tengo funciones f (x) = 3 * x + 2, g (x) = 5 * x - 6 y h (x) = 2 * x + 1, responderé por ejemplo:

• para x = 4, la función h

• para x = 2, la función g

• para x = 1, la función g

Mi idea es la siguiente:

1. Ordenar las funciones por el coeficiente de x, en orden decreciente.

2. Ordenar las consultas en orden creciente

3. deshacerse de las funciones paralelas, mantener los que tienen la más pequeña término constante (por ejemplo: si he f (x) = 2 * x + 4 y g (x) = 2 * x + 2, f (x) nunca será más pequeño que g (x), por lo que no necesito f (x)).

4. En este momento estoy en el intervalo de -inf a algún número real, lo llaman W1 y sé que en este intervalo, la función con el coeficiente lineal más alta es la más pequeña

5. Búsqueda W1 encontrando el x1 más pequeño f (x1) = g (x1) donde f es mi función actual y g itera a través de todas las demás funciones con un coeficiente lineal menor, w1 = x1

6. Repita mientras mi consulta esté en el intervalo (-inf, w1): muestra la función actual, luego pasa a la siguiente consulta.

7. Si todavía tengo consultas que necesitan respuesta, permita que la función actual sea la que interseca mi función actual actual en x = w1, y en lugar de -inf ponga w1, repita los mismos pasos.

Sin embargo, mi implementación o idea no es lo suficientemente rápida. ¿Hay algo que no haya notado que pueda acelerar mi programa?

Gracias de antemano.

Answer 1

¿no podría simplemente resolver sus intersecciones y almacenar la mayor función para cada intervalo en el dominio?

edit- para elaborar, si tuviera que resolver cualquier par de funciones para x, entonces x representa el valor donde una de esas dos funciones se vuelve mayor que la otra. Habrá intervalos definibles donde la función mínima es la misma para todos los valores en el intervalo.

Aquí hay un diagrama de sus 3 funciones de ejemplo.

Los intervalos (con la función mínima correspondiente) de este gráfico sería

(-∞, 7/3]  => 5x - 6 
(7/3, ∞]  => 2x + 1 

Ahora, en tiempo de ejecución, en lugar de "¿Cuál es la función de un mínimo en x = q" sólo tiene que hacer "¿A qué intervalo pertenece q?".

Y, si no me equivoco, si tiene N funciones lineales, tendría como máximo N-1 intervalos para almacenar. Y, existen estructuras de datos especializadas que puede usar para almacenar y buscar intervalos si realmente tiene muchas funciones para analizar.

Answer 2

Si entiendo correctamente, su solución es hacer un preprocesamiento de todas sus funciones para que el dominio de x se divida en rangos, y en cada uno de esos rangos, sabe cuál es la función mínima.

En realidad, hay dos fases: la "preparación" y la "consulta" (donde se le da un resultado específico x).

¿Cuál es su cuello de botella?

Naturalmente, para que la fase de "consulta" sea rápida, debe organizar sus rangos en una especie de matriz ordenada, de modo que pueda encontrar el rango que contiene la x dada por una búsqueda mediana (o similar) en un tiempo logarítmico . Si esto es lo que hiciste y aún así no es lo suficientemente rápido, considera las optimizaciones a nivel de código, porque desde el punto de vista algorítmico esta parece ser la solución más óptima.

Si su cuello de botella es la fase de "preparación", aquí hay oportunidades para optimizaciones. Según entiendo, encuentras intersecciones de todos los pares de tus funciones (después de deshacerte de las paralelas). Y esto no es realmente necesario.

Considere lo siguiente. Primero ordena todas las funciones por su coeficiente (los coeficientes más altos están al principio). Deshacerse de las funciones paralelas. Luego compila la matriz de rangos, mientras iteras a través de tus funciones.

Dado que la función actual tiene el coeficiente más bajo (entre los que ya se han analizado) - la función actual será la más pequeña ya que x va al infinito. De modo que su rango debería ser de algunos x0 hasta el infinito. Encuentra eso x0. Tome el último rango de la matriz (que pertenece a la función procesada previamente), y encuentre x0 - la intersección de esa función con la actual. La primera gama se reduce hasta x0. Si ese rango deja de ser válido (rango de inicio superior a x0) significa que esa función está totalmente oculta. En tal caso, elimine ese rango y repita el procedimiento.

Para hacer las cosas más claras que voy a escribir un pseudo-código:

rangeArr es un conjunto de pares F,X, mientras que F es la descripción de la función, y X es el inicio del rango de la función. El final del rango de funciones se considera el inicio del siguiente rango, y el final del último rango de funciones es + infinito.

for each F sorted by coefficient 
{ 
    double x0; 

    while (true) 
    { 
     if (rangeArr is empty) 
     { 
      x0 = -inf; 
      break; 
     } 

     FPrev = rangeArr.back().F; 
     xPrev = rangeArr.back().X; 

     x0 = IntersectionOf(F, FPrev); 

     if (x0 > xPrev) 
      break; 

     rangeArr.DeleteLastRange(); 
    } 

    rangeArr.InsertRange(F, x0); 
}