En el diseño y análisis de algoritmos de optimización combinatoria , la búsqueda paramétrica es una técnica inventada por Nimrod Megiddo ( 1983 ) para transformar un algoritmo de decisión (¿este problema de optimización tiene una solución con una calidad mejor que algún umbral dado?) En un algoritmo de optimización ( encuentre la mejor solución). Se utiliza 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, como si se estuviera ejecutando con el valor de solución óptimo (desconocido) como su entrada. Se supone que este algoritmo de prueba se comporta de manera discontinua cuando, y para operar en su parámetro solo por simples comparaciones de con otros valores calculados, o probando el signo de funciones polinomiales de bajo grado de. Para simular el algoritmo, es necesario simular cada una de estas comparaciones o pruebas, aunque eldel algoritmo simulado se desconoce. 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 eso determina si está por encima, por debajo o igual al valor de solución óptimo .
Dado que el algoritmo de decisión en sí mismo se comporta necesariamente de manera discontinua en , el mismo algoritmo también se puede utilizar como algoritmo de prueba. Sin embargo, muchas aplicaciones utilizan otros algoritmos de prueba (a menudo, algoritmos de clasificación por 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 para reducir significativamente el número de instancias del algoritmo de decisión.
Algoritmo de prueba secuencial
En la forma más básica de la técnica de búsqueda paramétrica, tanto el algoritmo de prueba como los algoritmos de decisión son algoritmos secuenciales (no paralelos), posiblemente el mismo algoritmo entre sí. La técnica simula el algoritmo de prueba paso a paso, ya que se ejecutaría cuando se le diera el valor de solución óptimo (desconocido) como parámetro.. Siempre que la simulación alcance un paso en el que el algoritmo de prueba compare su parámetro a algún otro número , no puede realizar este paso haciendo una comparación numérica, ya que no sabe qué es. En cambio, llama al algoritmo de decisión con parámetroy utiliza el resultado del algoritmo de decisión para determinar el resultado de la comparación. De esta forma, el tiempo de la simulación termina igualando el producto de los tiempos de 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 de solución óptimo, no se puede simular con precisión a menos que uno de los valores de los parámetrospasado al algoritmo de decisión es en realidad igual al valor de solución óptimo. Cuando esto sucede, el algoritmo de decisión puede detectar la igualdad y guardar el valor de la solución óptima para una salida posterior. Si el algoritmo de prueba necesita conocer el signo de un polinomio en, esto puede simularse de nuevo 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, en caso contrario, en qué dos raíces se encuentra.
Un ejemplo considerado tanto por Megiddo (1983) como por van Oostrum y Veltkamp (2002) se 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 será lineal por partes en lugar de tener una velocidad 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, finalmente, ellas y su mediana estarán a la derecha del origen. El problema es calcular el tiempoen 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, se puede calcular la posición de cada partícula en el momento y cuente el número de partículas a cada lado del origen. Si hay más partículas a la izquierda que a la derecha, entonces, y si hay más partículas a la derecha que a la izquierda, entonces . Cada paso de este algoritmo de decisión compara el parámetro de entrada hasta el momento en que una de las partículas cruza el origen.
El uso de este algoritmo de decisión como algoritmo de prueba y como algoritmo de decisión de una búsqueda paramétrica conduce a un algoritmo para encontrar el tiempo óptimo. en tiempo total cuadrático. Para simular el algoritmo de decisión para el parámetro, la simulación debe determinar, para cada partícula, si su tiempo de cruce es antes o después , y por lo tanto si está a la izquierda oa la derecha del origen en el momento . Responder a esta pregunta para una sola partícula: comparar el tiempo de cruce de la partícula con el tiempo de cruce óptimo desconocido.- se puede realizar ejecutando el mismo algoritmo de decisión con el tiempo de cruce de la partícula como parámetro. Así, la simulación termina ejecutando el algoritmo de decisión en cada uno de los tiempos de cruce de partículas, uno de los cuales debe ser el tiempo de cruce óptimo. Ejecutar el algoritmo de decisión una vez toma un tiempo lineal, por lo que ejecutarlo por separado en cada tiempo de cruce requiere un tiempo cuadrático.
Algoritmo de prueba paralelo
Como ya observó Megiddo (1983) , la técnica de búsqueda paramétrica puede acelerarse sustancialmente reemplazando el algoritmo de prueba simulado por un algoritmo paralelo eficiente , por ejemplo en el modelo de máquina de acceso aleatorio en paralelo (PRAM) de cálculo paralelo, donde una colección de Los procesadores operan 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 procesadores y lleva tiempo (es decir, pasos en los que cada procesador realiza una sola operación), entonces cada uno de sus pasos se puede simular utilizando el algoritmo de decisión para determinar los resultados de como máximo comparaciones numéricas. Al encontrar un valor mediano o cercano a la mediana 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 de la decisión. algoritmo. Al dividir repetidamente 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 comparaciones numéricas utilizando solo llamadas al algoritmo de decisión. Por lo tanto, el tiempo total para la búsqueda paramétrica en este caso se convierte en (para la simulación en sí) más el tiempo para llamadas al algoritmo de decisión (para lotes de comparaciones, tomando llamadas por lote). A menudo, para un problema que se puede resolver de esta manera, el producto del procesador de tiempo 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 por solo un factor polilogarítmico.
En el caso del problema de ejemplo de encontrar el tiempo de cruce de la mediana de partículas en movimiento, el algoritmo de prueba secuencial puede ser reemplazado por un algoritmo de clasificación paralelo que clasifica las posiciones de las partículas en el momento dado por el parámetro del algoritmo, y luego usa el orden clasificado para determinar la partícula mediana y encontrar el signo de su posición. La mejor opción para este algoritmo (según su análisis teórico, si no en la práctica) es la red de clasificación de Ajtai , Komlós y Szemerédi ( 1983 ). Esto se puede interpretar como un algoritmo PRAM en el que el número de procesadores es proporcional a la longitud de entrada y el número de pasos paralelos es logarítmico. Por lo tanto, simular este algoritmo secuencialmente lleva tiempo. para la simulación en sí, junto con lotes de comparaciones, cada una de las cuales puede ser manejada por llamadas al algoritmo de decisión de tiempo lineal. Poner estos límites de tiempo juntos datiempo total para la búsqueda paramétrica. Este no es el momento óptimo para este problema; el mismo problema se puede resolver más rápidamente al observar 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 otras optimizaciones más complicadas. problemas, 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 utilizando 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 rápida (un algoritmo que divide repetidamente la entrada en dos subconjuntos y luego ordena de forma recursiva 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 se pueden realizar en paralelo entre sí. El algoritmo paramétrico resultante es más lento en el peor de los casos 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 conducirán a llamadas adicionales al algoritmo de decisión) y los valores de comparación probados por el algoritmo de prueba simulado son suficientemente uniformes distribuidos, entonces, a medida que el algoritmo progresa, el número de comparaciones no resueltas generadas en cada paso de tiempo será pequeño. Con base en este análisis heurístico, y en los resultados experimentales con una implementación del algoritmo, argumentan que un algoritmo de búsqueda paramétrica basado en clasificación rápida será más práctico de lo que sugeriría su análisis del peor de los casos.
Clasificación desincronizada
Cole (1987) optimizó aún más la técnica de búsqueda paramétrica para casos (como el ejemplo) en los que el algoritmo de prueba es un algoritmo de clasificación por comparación. Para la red de clasificación AKS y algunos otros algoritmos de clasificación que se pueden usar en su lugar, Cole observa que no es necesario mantener los procesadores simulados sincronizados entre sí: en cambio, uno puede permitir que algunos de ellos progresen más a través del algoritmo de clasificación. mientras que otros esperan a que se determinen los resultados de sus comparaciones. Basándose en este principio, Cole modifica la simulación del algoritmo de clasificación, de modo que mantiene una colección de comparaciones simuladas no resueltas que pueden no provenir todas del mismo paso de tiempo paralelo del algoritmo de prueba. Como en la versión paralela sincronizada de la búsqueda paramétrica, es posible resolver la mitad de estas comparaciones encontrando el valor de comparación de la mediana y llamando al algoritmo de decisión sobre este valor. Luego, en lugar de repetir este procedimiento de reducción a la mitad hasta que la colección de comparaciones no resueltas se vacíe, Cole permite que los procesadores que estaban esperando las comparaciones resueltas avancen a través de la simulación hasta llegar a otra comparación que debe resolverse. Usando este método, Cole muestra que un algoritmo de búsqueda paramétrico en el que el algoritmo de prueba está ordenando puede completarse usando solo un número logarítmico de llamadas al algoritmo de decisión, en lugar delllamadas realizadas por la versión original de Megido de búsqueda paramétrica. En lugar de utilizar la red de clasificación AKS, también es posible combinar esta técnica con un algoritmo de clasificación de fusión en paralelo de Cole (1988) , lo que da como resultado límites de tiempo con factores constantes más pequeños que, sin embargo, todavía no son lo suficientemente pequeños para ser prácticos. Se puede obtener una aceleración similar para cualquier problema que se pueda calcular en una red informática distribuida de grado acotado (como lo es la red de clasificación AKS), ya sea mediante la técnica de Cole o mediante una técnica relacionada de simulación de múltiples rutas de cálculo ( Fernández-Baca 2001 ) .
Goodrich y Pszona (2013) combinan la mejora teórica de Cole con las aceleraciones prácticas de van Oostrum y Veltkamp (2002) . En lugar de utilizar una ordenación rápida paralela, como hicieron van Oostrum y Veltkamp, utilizan boxsort, una variante de ordenación rápida desarrollada por Reischuk (1985) en la que el paso de partición divide la entrada de forma aleatoria ensubproblemas más pequeños en lugar de solo dos subproblemas. Al igual que en la técnica de Cole, utilizan una búsqueda paramétrica desincronizada, en la que se permite que cada hilo de ejecución separado del algoritmo de clasificación en paralelo simulado progrese hasta que necesite determinar el resultado de otra comparación, y en la que el número de comparaciones no resueltas se reduce a la mitad. encontrando el valor de comparación mediano y llamando al algoritmo de decisión con ese valor. Como muestran, el algoritmo de búsqueda paramétrica aleatoria resultante hace solo un número logarítmico de llamadas al algoritmo de decisión con alta probabilidad, coincidiendo con el análisis teórico de Cole. Una versión extendida de su artículo incluye resultados experimentales de una implementación del algoritmo, que muestran que el tiempo total de ejecución de este método en varios problemas de optimización geométrica natural es similar al de la implementación de búsqueda paramétrica mejor sincronizada (el método basado en clasificación rápida 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 que realiza al algoritmo de decisión es significativamente menor, por lo que este método obtendría mayores beneficios en aplicaciones de búsqueda paramétrica donde el algoritmo de decisión es más lento.
En el problema de 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 . En el caso de Goodrich y Pszona, el algoritmo es aleatorio y obtiene este límite de tiempo con alta probabilidad.
Comparación con la 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, uno mantiene un intervalo de números, que se sabe que contiene el valor de solución óptimo, y reduce repetidamente el intervalo llamando al algoritmo de decisión en su valor mediano y manteniendo solo el medio intervalo por encima o por debajo de la mediana, según el resultado. de la llamada. Aunque este método solo puede encontrar una aproximación numérica al valor de solución óptimo, lo hace en un número de llamadas al algoritmo de decisión proporcional al número de bits de precisión de precisión para esta aproximación, lo que da como resultado algoritmos polinomiales débiles .
En cambio, cuando es aplicable, la búsqueda paramétrica encuentra algoritmos fuertemente polinomiales, cuyo tiempo de ejecución es una función solo del tamaño de entrada y es 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 logarítmica. Debido a que son fuertemente polinomiales en lugar de débilmente, 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 sencilla 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 "mientras que un enfoque de búsqueda binaria simple a menudo se defiende 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
La búsqueda paramétrica se ha aplicado en el desarrollo de algoritmos eficientes para problemas de optimización, particularmente en geometría computacional ( Agarwal, Sharir & Toledo 1994 ). Incluyen lo siguiente:
- Un punto central de un punto establecido 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 dimensionales, la fracción óptima que se puede lograr es siempre al menos . Los algoritmos basados en búsquedas paramétricas para construir puntos centrales bidimensionales se mejoraron posteriormente 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.( Cole 1987 ).
- La búsqueda paramétrica se puede utilizar como base para una algoritmo de tiempo para el estimador de 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 valores atípicos que la regresión lineal simple ( Cole et al. 1989 ).
- En gráficos por computadora , el problema de disparo de rayos (determinar el primer objeto en una escena que se cruza con una línea de visión o haz de luz dada) se puede resolver combinando la búsqueda paramétrica con una estructura de datos para un problema más simple, probando si alguno de los determinado conjunto de obstáculos ocluye un rayo determinado ( Agarwal y Matoušek 1993 ).
- El mayor problema del palo consiste en encontrar el segmento de línea más largo que se encuentra completamente dentro de un polígono dado . Se puede solucionar a tiempo, por polígonos de lados y cualquier , utilizando un algoritmo basado en búsqueda paramétrica ( Agarwal, Sharir & Toledo 1994 ).
- El anillo que contiene un conjunto de puntos dado y tiene el ancho más pequeño posible (diferencia entre los radios interior y exterior) se puede utilizar como una medida de la redondez del conjunto de puntos. Nuevamente, este problema se puede resolver a tiempo., por polígonos de lados y cualquier , utilizando un algoritmo basado en búsqueda paramétrica ( Agarwal, Sharir & Toledo 1994 ).
- La distancia de Hausdorff entre traslados de dos polígonos, con la traslación elegida para minimizar la distancia, se puede encontrar mediante la búsqueda paramétrica en el tiempo., dónde y son los números de lados de los polígonos ( Agarwal, Sharir y Toledo 1994 ).
- La distancia de Fréchet entre dos cadenas poligonales se puede calcular utilizando una búsqueda paramétrica en el tiempo, dónde y son los números de segmentos de las curvas ( Alt y Godau 1995 ).
- Para puntos en el plano euclidiano, moviéndose a velocidades constantes, el tiempo en el 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 el tiempo. La búsqueda paramétrica también se puede utilizar para otros problemas similares de encontrar el momento en el que alguna medida de un conjunto de puntos móviles obtiene su valor mínimo, para medidas que incluyen el tamaño de la bola envolvente mínima o el peso del árbol de expansión máximo ( Fernández- Baca 2001 ).
Referencias
- Agarwal, Pankaj K .; Matoušek, Jiří (1993), "Ray shooting and paramétric search", SIAM Journal on Computing , 22 (4): 794–806, CiteSeerX 10.1.1.298.6047 , doi : 10.1137 / 0222051 , MR 1227762
- Agarwal, Pankaj K .; Sharir, Micha ; Toledo, Sivan (1994), "Aplicaciones de la búsqueda paramétrica en la optimización geométrica", Journal of Algorithms , 17 (3): 292–318, doi : 10.1006 / jagm.1994.1038 , MR 1300253 , S2CID 380722.
- Ajtai, M .; Komlós, J .; Szemerédi, E. (1983), "An O ( n log n ) sorting network", Actas del 15º Simposio ACM sobre Teoría de la Computación (STOC '83) , págs. 1–9, doi : 10.1145 / 800061.808726 , ISBN 0-89791-099-0, S2CID 15311122.
- Alt, Helmut; Godau, Michael (1995), "Calculando la distancia de Fréchet entre dos curvas poligonales" (PDF) , International Journal of Computational Geometry & Applications , 5 (1–2): 75–91, doi : 10.1142 / S0218195995000064 , MR 1331177.
- Cole, Richard (1987), "Disminuir la velocidad de las redes de clasificación para obtener algoritmos de clasificación más rápidos", Journal of the ACM , 34 (1): 200-208, doi : 10.1145 / 7531.7537 , MR 0882669 , S2CID 2301419.
- Cole, Richard (1988), "Parallel merge sort", SIAM Journal on Computing , 17 (4): 770–785, doi : 10.1137 / 0217049 , MR 0953293 , S2CID 2416667.
- Cole, Richard; Salowe, Jeffrey S .; Steiger, WL; Szemerédi, Endre (1989), "Un algoritmo de tiempo óptimo para la selección de pendientes", SIAM Journal on Computing , 18 (4): 792–810, doi : 10.1137 / 0218055 , MR 1004799.
- Fernández-Baca, D. (2001), "Sobre búsqueda paramétrica no lineal", Algorithmica , 30 (1): 1–11, doi : 10.1007 / s00453-001-0001-2 , MR 1816864 , S2CID 20320912.
- Goodrich, Michael T .; Pszona, Paweł (2013), "La técnica de búsqueda paramétrica de Cole se hizo práctica" (PDF) , Proc. 25a Conferencia Canadiense sobre Geometría Computacional (CCCG 2013) , arXiv : 1306.3000 , Bibcode : 2013arXiv1306.3000G.
- Megiddo, Nimrod (1983), "Aplicación de algoritmos de cálculo paralelo en el diseño de algoritmos seriales", Journal of the ACM , 30 (4): 852–865, doi : 10.1145 / 2157.322410 , MR 0819134 , S2CID 2212007.
- Reischuk, Rüdiger (1985), "Algoritmos paralelos probabilísticos para clasificación y selección", SIAM Journal on Computing , 14 (2): 396–409, doi : 10.1137 / 0214030 , MR 0784745.
- van Oostrum, René; Veltkamp, Remco C. (2002), "La búsqueda paramétrica hecha práctica", Actas del Decimoctavo Simposio Anual sobre Geometría Computacional (SoCG '02) , Nueva York, NY, EE. UU .: ACM, págs. 1-9, doi : 10.1145 / 513400.513401 , hdl : 1874/18869 , ISBN 1-58113-504-1, S2CID 1551019.