Búsqueda paramétrica

En el diseño y análisis de algoritmos para la optimización combinatoria, la búsqueda paramétrica es una técnica inventada por Nimrod Meguido (1983) para transformar un algoritmo de decisión («¿tiene este problema de optimización una solución con calidad mejor que algún umbral dado?») en un algoritmo de optimización («encontrar la mejor solución»). Se usa con frecuencia para resolver problemas de optimización en geometría computacional .

Técnica

La idea básica de la búsqueda paramétrica es simular un algoritmo de prueba que toma como entrada un parámetro numérico $X$, como si se estuviera ejecutando con el valor de solución óptimo (desconocido) $X^{*}$ como su entrada. Se supone que este algoritmo de prueba se comporta de manera discontinua cuando $X=X^{*}$ y opera en su parámetro $X$ solo por simples comparaciones de $X$ con otros valores calculados o probando el signo de funciones polinómicas de bajo grado de $X$. Para simular el algoritmo, cada una de estas comparaciones o pruebas debe simularse, aunque el valor $X$ del algoritmo simulado es desconocido. Para simular cada comparación, la búsqueda paramétrica aplica un segundo algoritmo, un algoritmo de decisión, que toma como entrada otro parámetro numérico $Y$ y determina si $Y$ está por encima, por debajo o es igual al valor óptimo de la solución $X^{*}$.

Dado que el algoritmo de decisión en sí se comporta necesariamente de forma discontinua en $X^{*}$, el mismo algoritmo también puede usarse como algoritmo de prueba. Sin embargo, muchas aplicaciones usan otros algoritmos de prueba (a menudo, algoritmos de ordenamiento por de comparación). Las versiones avanzadas de la técnica de búsqueda paramétrica utilizan un algoritmo paralelo como algoritmo de prueba y agrupan las comparaciones que deben simularse en lotes, a fin de reducir significativamente el número de instancias del algoritmo de decisión.

Algoritmo de prueba secuencial

La técnica de búsqueda paramétrica en su forma más básica, tanto el algoritmo de prueba como los algoritmos los de decisión son algoritmos secuenciales (no paralelos). La técnica simula el algoritmo de prueba paso a paso ya que se ejecutará cuando se le dé el valor de solución óptimo (desconocido) como parámetro $X$. Cada vez que la simulación alcanza un paso en el que el algoritmo de prueba compara su parámetro $X$ a algún otro número $Y$, no puede realizarlo haciendo una comparación numérica ya que no sabe cuál es el valor de $X$. En cambio, llama al algoritmo de decisión con parámetro $Y$ y utiliza el resultado del algoritmo de decisión para determinar el resultado de la comparación. De esta manera, el tiempo para la simulación termina igualando el producto de los tiempos para los algoritmos de prueba y decisión. Debido a que se supone que el algoritmo de prueba se comporta de manera discontinua en el valor óptimo de la solución, no puede ser simulado con precisión a menos que uno de los valores de los parámetros $Y$ pasado al algoritmo de decisión sea en realidad igual al valor óptimo de la solución. Cuando esto sucede, el algoritmo de decisión puede detectar la igualdad y guardar el valor óptimo de la solución para una salida posterior. Si el algoritmo de prueba necesita conocer el signo de un polinomio en $X$, esto se puede simular nuevamente pasando las raíces del polinomio al algoritmo de decisión para determinar si el valor de la solución desconocida es una de estas raíces o, si no, entre qué dos raíces se encuentra.

Un ejemplo considerado tanto por Megiddo (1983) como por van Oostrum y Veltkamp (2002) refiere a un sistema de un número impar de partículas, todas moviéndose hacia la derecha a diferentes velocidades constantes a lo largo de la misma línea. La mediana de las partículas, también tendrá un movimiento hacia la derecha pero uno con velocidad lineal por partes en lugar de tener una constante porque diferentes partículas serán la mediana en diferentes momentos. Inicialmente, las partículas y su mediana están a la izquierda del origen de la línea, y eventualmente, ellas y su mediana estarán a la derecha del origen. El problema es calcular el tiempo $t_{0}$ en el que la mediana se encuentra exactamente en el origen. Un algoritmo de decisión de tiempo lineal es fácil de definir: para cualquier momento $t$, uno puede calcular la posición de cada partícula en el tiempo $t$ y contar el número de partículas en cada lado del origen. Si hay más partículas a la izquierda que a la derecha, entonces $t<t_{0}$, y si hay más partículas a la derecha que a la izquierda, entonces $t>t_{0}$ . Cada paso de este algoritmo de decisión compara el parámetro de entrada $t$ al tiempo que una de las partículas cruza el origen.

El uso de este algoritmo de decisión como algoritmo de prueba y de decisión de una búsqueda paramétrica conduce a encontrar el tiempo óptimo $t_{0}$ en tiempo cuadrático total. Para simular el algoritmo de decisión para el parámetro $t_{0}$ la simulación debe determinar, para cada partícula, si su tiempo de cruce es antes o después de $t_{0}$ y, por lo tanto, si está a la izquierda o a la derecha del origen en el momento $t_{0}$ . Esta cuestión - comparar el tiempo de cruce de la partícula con el tiempo de cruce óptimo desconocido $t_{0}$ - se puede resolver usando el mismo algoritmo de decisión con el tiempo de cruce de la partícula como parámetro. Por lo tanto, la simulación termina ejecutando el algoritmo de decisión en cada uno de los tiempos de cruce de partículas, uno de esos tiempos debe ser el de cruce óptimo. Ejecutar el algoritmo de decisión una vez lleva tiempo lineal, por lo que ejecutarlo por separado en cada tiempo de cruce lleva tiempo cuadrático.

Algoritmo de prueba en paralelo

Como ya observó Megiddo (1983), la técnica de búsqueda paramétrica puede acelerarse sustancialmente mediante la sustitución del algoritmo de prueba simulado por un algoritmo paralelo eficiente, por ejemplo, en el modelo de cómputo paralelo de máquina de acceso aleatorio paralelo (PRAM), donde una colección de procesadores funcionan en sincronía en una memoria compartida y todos realizan la misma secuencia de operaciones en diferentes direcciones de memoria. Si el algoritmo de prueba es un algoritmo PRAM utiliza $P$ procesadores y lleva tiempo $T$ (es decir, $T$ pasos en los que cada procesador realiza una sola operación) entonces cada uno de sus pasos puede simularse utilizando el algoritmo de decisión para determinar los resultados de a lo sumo $P$ comparaciones numéricas. Al encontrar el valor de la mediana (o uno cercano) en el conjunto de comparaciones que deben evaluarse y pasar este valor único al algoritmo de decisión es posible eliminar la mitad o casi la mitad de las comparaciones con solo una llamada al algoritmo de decisión. Reduciendo a la mitad el conjunto de comparaciones requeridas por la simulación de esta manera, hasta que no quede ninguna, es posible simular los resultados de $P$ comparaciones numéricas usando solo $O(\log P)$ llamadas al algoritmo de decisión. Por lo tanto, el tiempo total para la búsqueda paramétrica en este caso se convierte en $O(PT)$ (para la simulación en sí) más el tiempo para $O(T\log P)$ llamadas al algoritmo de decisión (para $T$ lotes de comparaciones, tomando $O(\log P)$ llamadas por lote). A menudo, para un problema que se puede resolver de esta manera, el tiempo de procesamiento del algoritmo PRAM es comparable al tiempo para un algoritmo de decisión secuencial, y el tiempo paralelo es polilogarítmico, lo que lleva a un tiempo total para la búsqueda paramétrica que es más lento que el algoritmo de decisión pero solo por un factor polilogarítmico.

En el caso del problema de ejemplo de encontrar el tiempo de cruce de la mediana de $n$partículas en movimiento, el algoritmo de prueba secuencial puede ser reemplazado por un algoritmo de ordenamiento paralelo que ordene las posiciones de las partículas en el momento dado por el parámetro del algoritmo y luego use un índice del resultado ordenado para determinar la partícula mediana y encontrar el signo de su posición. La mejor opción para este algoritmo (de acuerdo con su análisis teórico, si no en la práctica) es la red de ordenamiento de Ajtai, Komlós y Szemerédi. Esto puede interpretarse como un algoritmo PRAM en el que el número $P$ de procesadores es proporcional a la longitud de entrada $n$ y el número de pasos paralelos es logarítmico. Por lo tanto, simular este algoritmo secuencialmente lleva un tiempo $O(n\log n)$ para la simulación en sí junto con $O(\log n)$ lotes de comparaciones, cada uno de los cuales puede ser manejado por $O(\log n)$ llamadas al algoritmo de decisión de tiempo lineal. Poner estos límites de tiempo juntos da un tiempo total de $O(n\log ^{2}n)$ para la búsqueda paramétrica. Este no es el tiempo óptimo para este problema: este problema se puede resolver más rápidamente observando que el tiempo de cruce de la mediana es igual a la mediana de los tiempos de cruce de las partículas, pero la misma técnica se puede aplicar a otros problemas optimización más complicados y en muchos casos proporciona el algoritmo fuertemente polinomial más rápido conocido para estos problemas.

Debido a los grandes factores constantes que surgen en el análisis de la red de clasificación AKS, la búsqueda paramétrica usando esta red como algoritmo de prueba no es práctica. En cambio,van Oostrum y Veltkamp (2002) sugieren utilizar una forma paralela de clasificación quick sort (un algoritmo que divide repetidamente la entrada en dos subconjuntos y luego ordena recursivamente cada subconjunto). En este algoritmo, el paso de partición es masivamente paralelo (cada elemento de entrada debe compararse con un elemento pivote elegido) y las dos llamadas recursivas pueden realizarse en paralelo entre sí. El algoritmo paramétrico resultante es más lento usando un análisis del peor caso que un algoritmo basado en la red de clasificación AKS. Sin embargo, van Oostrum y Veltkamp argumentan que si se guardan los resultados de los algoritmos de decisión anteriores (de modo que solo las comparaciones no resueltas por estos resultados conduzcan a llamadas adicionales al algoritmo de decisión) y los valores de comparación probados por el algoritmo de prueba simulado son lo suficientemente uniforme-distribuidos, entonces, a medida que el algoritmo progresa, el número de comparaciones no resueltas generadas en cada paso de tiempo será pequeño. Basados en este análisis heurístico y en resultados experimentales con una implementación del algoritmo argumentan que un algoritmo de búsqueda paramétrica basado en quicksort será más práctico de lo que sugeriría el análisis del peor de los casos.

Ordenación desincronizada

Cole (1987) mejoró la optimización de la búsqueda paramétrica para casos (tales como el del ejemplo) en los cuales el algoritmo de prueba es un algoritmo de ordenamiento por comparación. Para la red de ordenamiento AKS y algunos otros algoritmos de ordenamiento que pueden ser usados en su lugar, Cole observa que no es necesario mantener a los procesadores simulados sincronizados entre sí: en su lugar, uno puede permitirles seguir al algoritmo de ordenamiento mientras los otros esperan los resultados de las comparaciones.

Basado en este principio, Cole modifica la simulación del algoritmo de ordenamiento de manera que mantenga una colección de comparaciones simuladas sin resultados (es posible que no toda esta colección venga del mismo paso de procesamiento paralelo del algoritmo de prueba). Como en la versión sincronizada paralela, es posible resolver la mitad de las comparaciones encontrando el valor de comparación de la mediana y llamando al algoritmo de decisión con ese valor. Entonces, en lugar de repetir el procedimiento de dividir la colección de comparaciones no resueltas a la mitad hasta que esté vacía, Cole permite a los procesadores esperar las comparaciones resueltas para avazar a través de la simulación hasta que alcancen alguna otra comparación que deba ser resuelta. Usando este método, Cole muestra que un algoritmo de búsqueda paramétrica en el que el algoritmo de prueba es de ordenamiento, puede ser completado usando un número logarítmico de llamadas al algoritmo de decisión, en lugar de las $O(\log ^{2}n)$ llamadas hechas en la búsqueda paramétrica de la versión original de Megiddo. En lugar de usar una red de ordenamiento AKS, también es posible combinar esta técnica con el algoritmo merge sort paralelo de Cole (1988), que resulta en tiempos limitados por factores constantes más pequeños, sin embargo, sin ser lo suficientemente pequeños como para ser prácticos. Un aceleramiento similar puede obtenerse para cualquier problema que pueda ser computado en una red de computación distribuida con un grado limitado (como la red de ordenamiento AKS) ya sea usando la técnica de Cole o una técnica relacionada de simulación de varias rutas de computación.​ Goodrich y Pszona (2013) combina la mejora teórica de Cole con los aceleramientos prácticos de van Oostrum y Veltkamp (2002). En lugar de usar quicksort paralelo, como van Oostrum y Veltkamp, usan boxsort, una variante de quicksort desarrollada por Reischuk (1985) en la cual se divide la entrada aleatoriamente en $O({\sqrt {n}})$ sub-problemas más chicos en lugar de solo dos subproblemas. Como en la técnica de Cole, usan una búsqueda paramétrica desincronizada, en la cual cada hilo de ejecución del algoritmo paralelo de ordenamiento simulado puede avanzar hasta que necesite determinar el resultado de otra comparación, y además, el número de comparaciones no resueltas se divide encontrando el valor de la comparación mediana y llamando al algoritmo de decisión con ese valor. De esta manera, mostraron que el algoritmo de búsqueda paramétrica aleatorizado hace solo un número logarítimo de llamadas al algoritmo de decisión con alta probabilidad, coincidiendo con el análisis teórico de Cole. Una versión extendida de este paper incluye resultados experimentales de una implementación del algoritmo que muestra que el tiempo de ejecución total de este método en varios problemas de optimización sobre geometría natural es similar al de la mejor implementación de búsqueda paramétrica sincronizada (el método basado en quicksort de van Oostrum y Veltkamp): un poco más rápido en algunos problemas y un poco más lento en otros. Sin embargo, el número de llamadas hechas al algoritmo de decisión es significativamente menor, de manera que este método podría implicar grandes ganancias en aplicaciones de búsqueda paramétrica donde el algoritmo de decisión es el más lento.

Sobre el problema del ejemplo de encontrar la mediana del tiempo de cruce de un punto, tanto el algoritmo de Cole como el algoritmo de Goodrich y Pszona obtienen el tiempo de ejecución $O(n\log n)$. En el caso de Goodrich y Pszona, el algoritmo es aleatorio y obtiene este límite de tiempo con alta probabilidad.

Comparación con búsqueda binaria

El método de bisección (búsqueda binaria) también se puede utilizar para transformar la decisión en optimización. En este método, se mantiene un intervalo de números, que se sabe que contiene el valor óptimo de la solución y se reduce repetidamente el intervalo llamando al algoritmo de decisión con su valor medio y manteniendo solo el medio intervalo por encima o por debajo de la mediana, dependiendo del resultado de la llamada. Aunque este método solo puede encontrar una aproximación numérica al valor óptimo de la solución, lo hace en un número de llamadas al algoritmo de decisión que es proporcional al número de bits de precisión para esta aproximación lo que resulta en algoritmos débilmente polinómicos .

En cambio, cuando corresponde, la búsqueda paramétrica encuentra algoritmos fuertemente polinómicos, cuyo tiempo de ejecución es una función solo del tamaño de entrada e independiente de la precisión numérica. Sin embargo, la búsqueda paramétrica conduce a un aumento en la complejidad del tiempo (en comparación con el algoritmo de decisión) que puede ser mayor que el logarítmico. Debido a que son polinomios fuertes en lugar de débiles, los algoritmos basados en la búsqueda paramétrica son más satisfactorios desde un punto de vista teórico. En la práctica, la búsqueda binaria es rápida y, a menudo, mucho más simple de implementar, por lo que se necesitan esfuerzos de ingeniería de algoritmos para que la búsqueda paramétrica sea práctica. Sin embargo,van Oostrum y Veltkamp (2002) escriben que "si bien un enfoque de búsqueda binaria simple a menudo se recomienda como un reemplazo práctico para la búsqueda paramétrica, nuestro algoritmo [de búsqueda paramétrica] lo supera" en las comparaciones experimentales que realizaron.

Aplicaciones

El estimador de Theil-Sen comparación con la regresión lineal simple

La búsqueda paramétrica se ha aplicado en el desarrollo de algoritmos eficientes para problemas de optimización, particularmente en geometría computacional.​ Algunos ejemplos:

• El punto central de un conjunto de puntos en un espacio euclidiano es un punto tal que cualquier medio espacio que contenga el punto central también contiene una fracción constante de los puntos de entrada. Para espacios $d$-dimensionales, la fracción óptima que se puede lograr es siempre al menos $1/(d+1)$. Los algoritmos basados en búsqueda paramétrica para construir puntos centrales bidimensionales se mejoraron luego a tiempo lineal utilizando otras técnicas algorítmicas. Sin embargo, esta mejora no se extiende a dimensiones superiores. En tres dimensiones, la búsqueda paramétrica se puede utilizar para encontrar puntos centrales en el tiempo $O(n^{2}\log ^{4}n)$ ​ .
• La búsqueda paramétrica se puede utilizar como base para un algoritmo de tiempo $O(n\log n)$ para el estimador Theil-Sen, un método en estadísticas robustas para ajustar una línea a un conjunto de puntos que es mucho menos sensible a los valores atípicos que la regresión lineal simple.​
• En los gráficos por computadora, el problema del disparo de rayos (determinar el primer objeto en una escena que se cruza con una línea de visión o haz de luz) puede resolverse combinando la búsqueda paramétrica con una estructura de datos para un problema más simple, probando si un conjunto dado de obstáculos ocluye un rayo dado ​.
• El problema del palo más grande implica encontrar el segmento de línea más largo que se encuentra completamente dentro de un polígono dado. Se puede resolver en tiempo $O(n^{8/5+\epsilon })$ polígonos de $n$-lados y cualquier $\epsilon >0$, utilizando un algoritmo basado en la búsqueda paramétrica ​ .
• El anillo que contiene un conjunto de puntos dado y tiene el ancho más pequeño posible (diferencia entre los radios interno y externo) se puede usar como una medida de la redondez del conjunto de puntos. De nuevo, este problema puede resolverse en tiempo $O(n^{8/5+\epsilon })$, para polígonos de $n$-lados y cualquier $\epsilon >0$, utilizando un algoritmo basado en la búsqueda paramétrica.​
• La distancia de Hausdorff entre las traslaciones de dos polígonos, con una traslación elegida para minimizar la distancia, se puede encontrar usando la búsqueda paramétrica en tiempo $O((mn)^{2}\log ^{3}mn)$, dónde $m$ y $n$ son los números de lados de los polígonos ​ .
• La distancia de Fréchet entre dos cadenas poligonales se puede calcular usando la búsqueda paramétrica en el tiempo $O(mn\log mn)$, dónde $m$ y $n$ son los números de segmentos de las curvas.​
• Para $n$ puntos en el plano euclidiano moviéndose a velocidades constantes, el tiempo en que los puntos obtienen el diámetro más pequeño (y el diámetro en ese momento) se puede encontrar usando una variación de la técnica de Cole en tiempo $O(n\log ^{2}n)$. La búsqueda paramétrica también se puede utilizar para otros problemas similares al de encontrar el momento en que alguna medida de un conjunto de puntos móviles obtiene su valor mínimo, por ejemplo, para medidas que incluyen el tamaño de la círculo mínimo o la altura de un árbol de expansión máxima.​

Bibliografía

• Agarwal, Pankaj K.; Matoušek, Jiří (1993). «Ray shooting and parametric search». SIAM Journal on Computing (en inglés) 22 (4): 794-806. doi:10.1137/0222051. 
• Agarwal, Pankaj K.; Sharir, Micha; Toledo, Sivan (1994). «Applications of parametric searching in geometric optimization». Journal of Algorithms (en inglés) 17 (3): 292-318. doi:10.1006/jagm.1994.1038. 
• Ajtai, M.; Komlós, J.; Szemerédi, E. (1983). «An O(n log n) sorting network». Proceedings of the 15th ACM Symposium on Theory of Computing (STOC '83) (en inglés). pp. 1-9. ISBN 0-89791-099-0. doi:10.1145/800061.808726. 
• Alt, Helmut; Godau, Michael (1995). «Computing the Fréchet distance between two polygonal curves». International Journal of Computational Geometry & Applications (en inglés) 5 (1-2). pp. 75-91. doi:10.1142/S0218195995000064. 
• Cole, Richard (1987). «Slowing down sorting networks to obtain faster sorting algorithms». Journal of the ACM (en inglés) 34 (1): 200-208. doi:10.1145/7531.7537. 
• Cole, Richard (1988). «Parallel merge sort». SIAM Journal on Computing (en inglés) 17 (4). pp. 770-785. doi:10.1137/0217049. 
• Cole, Richard; Salowe, Jeffrey S.; Steiger, W. L.; Szemerédi, Endre (1989). «An optimal-time algorithm for slope selection». SIAM Journal on Computing (en inglés) 18 (4): 792-810. doi:10.1137/0218055. 
• Fernández-Baca, D. (2001). «On nonlinear parametric search». Algorithmica (en inglés) 30 (1): 1-11. doi:10.1007/s00453-001-0001-2. 
• Goodrich, Michael T.; Pszona, Paweł (2013). «Cole's parametric search technique made practical». Proc. 25th Canadian Conference on Computational Geometry (CCCG 2013) (en inglés). Bibcode:2013arXiv1306.3000G. 
• Megiddo, Nimrod (1983). «Applying parallel computation algorithms in the design of serial algorithms». Journal of the ACM (en inglés) 30 (4): 852-865. doi:10.1145/2157.322410. 
• Reischuk, Rüdiger (1985). «Probabilistic parallel algorithms for sorting and selection». SIAM Journal on Computing (en inglés) 14 (2): 396-409. doi:10.1137/0214030. 
• van Oostrum, René; Veltkamp, Remco C. (2002). «Parametric search made practical». Proceedings of the Eighteenth Annual Symposium on Computational Geometry (SoCG '02) (en inglés). Nueva York: ACM. pp. 1-9. ISBN 1-58113-504-1. doi:10.1145/513400.513401. 

Enlaces externos

• Datos: Q25305511