Podar y buscar es un método para resolver problemas de optimización sugerido por Nimrod Megiddo en 1983. [1]
La idea básica del método es un procedimiento recursivo en el que en cada paso el tamaño de entrada se reduce ("poda") por un factor constante 0 < p <1 . Como tal, es una forma de algoritmo de disminución y conquista , donde en cada paso la disminución es por un factor constante. Sea n el tamaño de entrada, T ( n ) la complejidad temporal de todo el algoritmo de poda y búsqueda y S ( n ) la complejidad temporal del paso de poda. Entonces T ( n ) obedece a la siguiente relación de recurrencia :
Esto se asemeja a la recurrencia de la búsqueda binaria, pero tiene un término S ( n ) más grande que el término constante de la búsqueda binaria. En los algoritmos de poda y búsqueda, S (n) suele ser al menos lineal (ya que se debe procesar toda la entrada). Con este supuesto, la recurrencia tiene la solución T ( n ) = O ( S ( n )) . Esto se puede ver aplicando el teorema maestro para las recurrencias de divide y vencerás o observando que los tiempos de los subproblemas recursivos disminuyen en una serie geométrica .
En particular, el propio Megido utilizó este enfoque en su algoritmo de tiempo lineal para el problema de programación lineal cuando la dimensión es fija [2] y para el problema de esfera envolvente mínima para un conjunto de puntos en el espacio. [1]