La palabra “ podar ” significa reducir algo quitando cosas que no son necesarias. Entonces, Prune-and-Search es un excelente paradigma algorítmico para resolver varios problemas de optimización. Este enfoque fue sugerido por primera vez por Nimrod Megiddo en 1983 . Este enfoque siempre consta de varias iteraciones. En cada iteración, descarta una fracción, digamos f, de los datos de entrada y luego invoca el mismo algoritmo recursivamente en los datos restantes para resolver el problema.
La idea principal de este enfoque es reducir el espacio de búsqueda mediante la poda de una fracción de los elementos de entrada y recurrir a los elementos de entrada válidos restantes . Después de algunas iteraciones, el tamaño de los datos de entrada será tan pequeño que podrá resolverse mediante el método de fuerza bruta en un tiempo constante c’.
Análisis de Complejidad de Tiempo para tales algoritmos:
Sea el tiempo requerido en cada iteración O(n^k) donde-
n = size of input data k is some constant.
Sea f = fracción de datos que se eliminan en cada iteración. Recursivamente, el enfoque anterior se puede escribir como-
T(n) = T((1-f)n) + O(n^k)
Tenemos,
T(n) <= T((1-f)n) + c*n^k para valores muy grandes de norte.
<= T((1-f)^2 * n) + c*n^k +c*((1-f)^k)*n^k
.
.
<= c’ + c*n^k + c*((1-f)^k)n^k + c*((1-f)^2k)n^k + ….. + c*((1 -f)^pk)n^k
= c’ + c*n^k(1 + (1-f)^k + (1-f)^2k + ….. + (1-f)^pk).
Dado que (1-f) < 1, como n tiende a un número muy grande
, por lo tanto, T(n) = O(n^k).
Muestra que la complejidad temporal de todo el proceso es del mismo orden que la complejidad temporal de podar y buscar en cada iteración. Este enfoque se puede utilizar para analizar los algoritmos de muchos problemas conocidos como la búsqueda binaria, encontrar el K-ésimo elemento más grande/más pequeño de una array no ordenada (el problema de selección), el problema de 1 centro (círculo envolvente más pequeño), resolver la programación lineal en dos variables, y así.
Ejemplos:
1. Búsqueda binaria:
como sabemos, esta técnica se aplica en una lista ordenada de datos para buscar el índice de un valor particular (digamos ‘ val ‘), en la lista dada. Para esto, vamos al elemento del medio y lo comparamos con val . Si el elemento del medio es igual a val entonces, devolvemos este elemento del medio. De lo contrario, podamos la mitad de los datos y se utiliza la misma técnica para los elementos restantes. Para una implementación detallada, vea esto .
Análisis de Complejidad de Tiempo:
En cada paso, ya que está comparando val solo con el elemento medio, entonces la complejidad para este paso será O(1) digamos c(cualquier constante). Y se elimina la mitad de la lista, por lo que T(n) = T(n/2) + O(1) si n>=2 De lo contrario , T(n) = O(1) = c .
En términos simples,
T(n) = T(n/2) + c
= T(n/4) + c + c
= T(n/8) + c + c + c
…..
= T(1) + c + … + c + c
= k por c donde k será una constante.
Dado que la mitad de la entrada se descarta en cada iteración, el valor de k será como máximo log(n) en el peor de los casos. Por lo tanto, la complejidad del caso más desfavorable de la búsqueda binaria será
T(n) = O(log(n)) .
2. El problema de selección:
Dada una lista desordenada de n elementos, la tarea es encontrar el K-ésimo elemento más pequeño de la lista. El primer enfoque muy básico es ordenar la lista dada en orden ascendente y elegir directamente el valor en el índice Kth. Por lo tanto, la clasificación tomará un tiempo O(n*log(n)) en general y O(1) para recuperar el valor del índice Kth. Por lo tanto, en general T(n) = O(n*log(n)) para este enfoque.
El segundo enfoque consiste en utilizar el método QuickSelect, es decir, la técnica de podar y buscar. La idea básica de este algoritmo de selección de poda y búsqueda es determinar una fracción que no contenga el elemento K-ésimo y descartar esa fracción de elementos de las próximas iteraciones. Sabemos que para tener unaAlgoritmo O(n) , debemos tener un método que sea capaz de eliminar una fracción de elementos en tiempo O(n) en cada iteración. Sea P un elemento de la lista que puede dividir la lista dada en dos partes, digamos S1 y S2 , tal que S1 contiene todos los elementos menores o iguales que P y S2 contiene todos los elementos mayores que P. Ahora podemos decir que
- Si |S1| == K , entonces S1[k] será el K-ésimo elemento más pequeño.
- Si |S1| > K , entonces el elemento K-ésimo debe estar presente en S1 . Así que descarte la segunda parte S2 y recurra a S1 con el mismo algoritmo.
- De lo contrario, el elemento K-ésimo debe estar en S2 . Así que descarte S1 y recurra a S2 para (K-|S1|)th elemento en S2 .
El punto clave aquí es cómo seleccionar P de tal manera que siempre podamos descartar una fracción de S, sin importar si estamos podando S1 o S2 . La respuesta es P debe ser la mediana de la lista S. Nuevamente, encontrar la mediana es el caso especial de este problema donde K=n/2 .
Pero la mediana se puede calcular de alguna otra manera más eficiente utilizando el siguiente algoritmo:
- Divida la lista en n/5 sublistas, cada una con un máximo de 5 elementos.
- Ahora podemos ordenar cada sublista y encontrar su mediana en tiempo constante.
- De nuevo, encuentre la mediana de todas las medianas recursivamente hasta que el tamaño sea como máximo 5. La mediana obtenida será un pivote perfecto para usar en el algoritmo de selección rápida. [Tenga en cuenta que la ordenación por inserción será una mejor opción para ordenar las sublistas más pequeñas de tamaño 5 .]
¿Por qué solo 5?
Dividir la lista en un tamaño de 5 supone una división en el peor de los casos de 70-30. Al menos la mitad de las medianas son mayores que la mediana de las medianas, por lo que la mitad de los n/5 bloques tienen al menos 3 elementos que dan una división de 3n/10, lo que implica que la otra partición es 7n/10 en el peor de los casos, es decir, T(n ) = T(n/5) + T(7n/10) + O(n). Dado que (n/5 + 7n/10) < 1, entonces T(n) = O(n) en el peor de los casos. Sea P la mediana de las medianas que se pueden representar como:
|1''1''1''1''1| 1 1 1 1 |2 2 2 2 2| 2 2 2 2 |3__3__3__3_|P|'3''3''3''3| 4 4 4 4 |4 4 4 4 4| 5 5 5 5 |5__5__5__5__5|
Como se muestra aquí, al menos un cuarto de los elementos de S son menores o iguales a P y al menos un cuarto de los elementos de S son mayores o iguales a P . Por lo tanto, si elegimos P de esta manera, siempre podemos eliminar al menos una cuarta parte de los elementos durante cada iteración. Por lo tanto, dividir S en sublistas de tamaño 5 será una forma eficiente de encontrar la mediana de las medianas. Ahora podemos enunciar el algoritmo como-
Algoritmo de poda y búsqueda para encontrar el K-ésimo elemento más pequeño
Entrada: Un conjunto S de n elementos y K.
Salida: El K-ésimo elemento más pequeño en S.
Enfoque:
Paso 1: Si |S| <= 5, aplica cualquier método de Fuerza Bruta.
Paso 2: Divida S en n/5 sublistas, cada una con un máximo de 5 elementos.
Paso 3: Ordene cada sublista ( la ordenación por inserción será mejor para aplicar).
Paso 4: Encuentre recursivamente P como la mediana de las medianas de cada sublista.
Paso 5: Divida S en S1 y S2 de manera que S1 contenga todos los elementos menores o iguales que P y S2 contenga todos los elementos mayores que P.
Paso 6: Ahora puede haber tres casos como
a) si |S1| == K, entonces S1[k] será el K-ésimo elemento más pequeño.
b) si |S1| > K, entonces el K-ésimo elemento debe estar presente en S1. Así que descarta la segunda parte s2 y repite en s1 con el mismo algoritmo.
c) De lo contrario, el K-ésimo elemento debe estar en S2. Así que deseche S1 y recurra a S2 para (K-|S1|)th elemento en S2.
Para ver el código y la implementación detallados, visite K’th Smallest/Largest Element in Unsorted Array | Conjunto 3 (Tiempo lineal en el peor de los casos)
Análisis de complejidad: dado que cada sublista contiene 5 elementos, clasificarlos llevará una cantidad constante de tiempo. Por lo tanto, los pasos 2, 3 y 5 se pueden realizar en un tiempo O(n), y el paso 4 necesita un tiempo T(n/5), ya que estamos usando el mismo algoritmo recursivamente para encontrar la mediana de n/5 medianas. Dado que estamos eliminando al menos n/4 elementos en cada iteración, quedan 3n/4 elementos después de cada iteración en el peor de los casos. Por lo tanto, T(n) = T(3n/4) + T(n/5) + O(n).
Sea T(n) = a0 + a1*n + a2*(n^2) + …. donde a1 != 0.
tenemos
T(3n/4) = a0 + (3/4)a1*n + (9/16)a2*(n^2) + ….
T(n/5) = a0 + (1/5)a1*n + (1/25)a2*(n^2) + ….
T((3n/4) + (n/5)) = T(19n/20) = a0 + (19/20)a1*n + (361/400)a2*(n^2) + ….
Así, T(3n/4) + T(n/5) <= a0 + T(19n/20).
Por lo tanto,
T(n) = T(3n/4) + T(n/5) + O(n)
<= T(19n/20) + cn.
Aplicando a esta desigualdad la fórmula inicialmente obtenida para el caso general,
obtendremos T(n) = O(n).
Por lo tanto, tenemos un algoritmo de tiempo lineal en el peor de los casos para resolver el problema de selección basado en la técnica de podar y buscar. Del mismo modo, podemos aplicar este tipo de estrategias para resolver Problemas de Programación Lineal con dos variables y el Círculo Más Pequeño .