Búsqueda paramétrica
Se usa con frecuencia para resolver problemas de optimización en geometría computacional .
, como si se estuviera ejecutando con el valor de solución óptimo (desconocido)
está por encima, por debajo o es igual al valor óptimo de la solución
En cambio, llama al algoritmo de decisión con parámetro
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.
, 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.
y contar el número de partículas en cada lado del origen.
al tiempo que una de las partículas cruza el origen.
Por lo tanto, el tiempo total para la búsqueda paramétrica en este caso se convierte en
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.
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.
Esto puede interpretarse como un algoritmo PRAM en el que el número
Por lo tanto, simular este algoritmo secuencialmente lleva un tiempo
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.
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.
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.
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.
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.
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.
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
sub-problemas más chicos en lugar de solo dos subproblemas.
El método de bisección (búsqueda binaria) también se puede utilizar para transformar la decisión en optimización.
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.
